2024-12-15 日报 Day17

今日的鸡汤

且以青春赴山海,
青舟无惧万重山。

今日学习内容

1、《JavaScript数据结构与算法》 P170-174

今日笔记

1、排序和搜索算法

• 排序算法

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 归并排序
  • 快速排序
  • 堆排序
  • 计数排序
  • 桶排序
  • 基数排序

• 搜索算法

  • 顺序搜索
  • 二分搜索
  • 插值搜索
  • 斐波那契搜索
  • 二叉树搜索
  • 散列算法
    2、排序算法: 排序算法是一种算法，用于将一组元素按照一定的顺序排列。在开始排序算法之前，先创建一个数组来表示待排序和搜索的数据结构。

    function ArrayList(){
        var array = [];
        this.insert = function(item){
            array.push(item);
        };
        this.toString = function(){
            return array.join();
        };
    }

    2、冒泡排序
    冒泡排序是排序算法中最简单的但是从运行时间的角度来看，冒泡排序是最差的一个。
    冒泡排序算法的原理如下:

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

   this.bubbleSort = function(){
       var length = array.length;
       for(var i=0; i<length; i++){
           for(var j=0; j<length-1; j++){
               if(array[j] > array[j+1]){
                   swap(j, j+1);
               }
           }
       }
   };
   var swap = function(index1, index2){
       var aux = array[index1];
       array[index1] = array[index2];
       array[index2] = aux;
   };

   冒泡排序的时间复杂度是O(n2)。
   3、选择排序
   选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放在第一位，接着找到第二小的值并将其放在第二位，以此类推。

   this.selectionSort = function(){
       var length = array.length,
           indexMin;
       for(var i=0; i<length-1; i++){
           indexMin = i;
           for(var j=i; j<length; j++){
               if(array[indexMin] > array[j]){
                   indexMin = j;
               }
           }
           if(i !== indexMin){
               swap(i, indexMin);
           }
       }
   };

   选择排序同样也是一个复杂度为O(n2)的算法。