冒泡排序

((arr) => {
    for(let i=0;i<arr.length;i++){
        for(let j=i+1;j<arr.length;j++){
            if(arr[j]<arr[i]){//从左往右升序排列
                //交换位置
                let tmp=arr[i];
                arr[i]=arr[j];
                arr[j] = tmp;
            }
        }
    }
    console.log(arr);
})([1, 5, 4, 2, 9, 7, 8]);//>>[1,2,4,5,7,8,9]

因为嵌套两个for循环，所以冒泡排序的时间复杂度为 O(N2)。

选择排序

假设数组A里面有N个项，选择排序是这样的：数组A第i个项记作 A(i)，第(i+1)~(N-1)项中的最小(最大的情况也是相似的逻辑）值记作 A(m)，然后比较它俩大小，如果 A(m) < A(i)，交换位置……直到把整个数组处理一遍。代码如下：

((arr) => {
    let N = arr.length;
    for(let i=0;i<N;i++){
        let min=arr[i+1],minIndex=i+1;//记录第(i+1)~(N-1)项中的最小值以及对应的索引
        for(let j=i+1;j<N;j++){
            if(arr[j]<min){//从左往右升序排列
                minIndex=j;
                min = arr[j];
            }            
        }
        if (arr[minIndex] < arr[i]) {
            //交换位置
            let tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    console.log(arr);
})([1, 5, 4, 2, 9, 7, 8]);//>>[1,2,4,5,7,8,9]

可以看出选择排序也是一外一内两个for循环，因此时间复杂度也是 O(N2) 。但是选择排序与冒泡排序差别地方在于：

• 选择排序的位置交换是在第二个for循环之外，第一个for循环之内，因此选择排序交换位置最多N次，而冒泡排序最多可能 N2次。所以大多数情况下，选择排序比冒泡排序效率好一些。

插入排序

插入排序我们打扑克时跟手中牌排序的思路一样，刚开始左手上一堆乱序的牌，我们把牌往手的右边挪一挪，把手的左边空出一点位置来，然后在右手乱牌中抽一张出来，插入到左边，再抽一张出来，插入到左边……每次插入都插入到左边合适的位置，时刻保持左边的牌是有序的，直到右边的牌抽完，则排序完毕。

代码实现如下：

((arr) => {
	let length = arr.length;
  for(let i = 1; i < length; i++) {
    let temp = arr[i];
    let j = i;
    for(; j > 0; j--) {
      if(temp >= arr[j-1]) {
        break;      // 当前考察的数大于前一个数，证明有序，退出循环
      }
      arr[j] = arr[j-1]; // 将前一个数复制到后一个数上
    }
    arr[j] = temp;  // 找到考察的数应处于的位置
  }
  console.log(arr)
})([2,5,10,7,10,32,90,9,11,1,0,10]);//>>[0, 1, 2, 5, 7, 9, 10, 10, 10, 11, 32, 90]

从代码里我们可以看出，如果找到了合适的位置，就不会再进行比较了，就好比右手里抽出的一张牌本身就比我左手里的牌都小，那么我只需要直接放在左手靠边位置就行了，不用一张一张去移动牌腾出位置插入到中间。

所以说，最好情况的时间复杂度是 O(N) ，最坏情况的时间复杂度是 O(N2) ，然而时间复杂度这个指标看的是最坏的情况，而不是最好的情况，所以插入排序的时间复杂度也是 O(N2) 。

快速排序

快速排序其实是分治法，将待排序数组里的项和基准数对比，比基准数大的放在一边，小的放另一边，然后再对左右两边的子数组重复使用这个思路，直到整个数组排序完毕。

((arr) => {
   /**
   * @param    left    数组的最左侧项的索引
   * @param    right    数组的最右侧项的索引
   */
   function quicksort(left, right) {
      let i/*左指针索引*/, j/*右指针索引*/, temp/*基准数*/;
      if (left > right)
         return;
      temp = arr[left];//取数组第一个项为基准数
      i = left;
      j = right;
      while (i != j) { //若左右两个指针没碰头        
         while (arr[j] >= temp && i < j)//顺序很重要，要先从右边开始找，直到找到比temp小的为止
            j--;
         while (arr[i] <= temp && i < j)//再找左边的，直到找到比temp大的数为止
            i++;
         if (i < j)//交换这两个数在数组中的位置，让小的在左边，大的在右边
         {
            let t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
         }
      }
      //然后将基准数与小的数换位，将小的数放在最左边，基准数放中间
      arr[left] = arr[i];
      arr[i] = temp;
      
      quicksort(left, i - 1);//递归。继续处理左边的，这里是一个递归的过程
      quicksort(i + 1, right);//递归。继续处理右边的 ，这里是一个递归的过程
   }

   quicksort(0, arr.length - 1);
   console.log(arr);
})([1, 5, 4, 2, 9, 7, 8]);//>> [1, 2, 4, 5, 7, 8, 9]

时间复杂度最好的情况是 O(NlogN)O(NlogN)O(NlogN)，最差的情况是O(N2)。算法分析：

• 当分区选取的基准元素为待排序元素中的最大或最小值时，为最差的情况，时间复杂度和直接插入排序的一样，移动次数达到最大值 Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2) ； 此时时间复杂为 O(N2) ；
• 当分区选取的基准元素为待排序元素中的"中值"，为最好的情况，时间复杂度为O(NlogN)。

Tags：前端算法

微信扫一扫：分享

微信里点“发现”，扫一下

二维码便可将本文分享至朋友圈。