— 以下全文皆以升序为例，代码并非最优化的方法

冒泡排序

冒泡排序属于程序猿必懂基础排序算法之一，相信科班出身的大家都懂，这里介绍该排序的2种优雅写法。

  • 最坏时间复杂度：O(n)

  • 最优时间复杂度：O(n)

  • 平均时间复杂度：O(n)

  • 稳定性：稳定

原理

  • 最左端的2位数字比较大小（左-右分别从第0位置至第n-1位置）

  • 如果第0位置的数 大于 第1位置的数，则交换位置的数；否则不变

  • 第1位置的数（注意：经过第二步，第1位置的数为左端2个数中的最大数） 与 第2位置的数计较，规则如上

  • 则最大数最后右移至第n位置，重复以上3步，最终完成排序

单看原理可能有些小伙伴不太明白，接下来结合实例演示一遍

栗子

有一组数集合：{4，2，5，1，3}，升序排序

  • 比较4和2的大小，4>2，则交换位置；数集合变为：{2，4，5，1，3}

  • 比较4和5的大小，4<5，则没有变化；数集合变为：{2，4，5，1，3}

  • 比较5和1的大小，5>1，则交换位置；数集合变为：{2，4，1，5，3}

  • 比较5和3的大小，5>3，则交换位置；数集合变为：{2，4，1，3，5}

第一轮遍历完成，最大数5移动到第n-1位置；下面第二轮，数集合：{2，4，1，3，5}

  • 比较2和4的大小，2<4，则没有变化；数集合变为：{2，4，1，3，5}

  • 比较4和1的大小，4>1，则交换位置；数集合变为：{2，1，4，3，5}

  • 比较4和3的大小，4>3，则交换位置；数集合变为：{2，1，3，4，5}

  • 比较4和5的大小，4<5，则没有变化；数集合变为：{2，1，3，4，5} （这次比较没有意义的）

第二轮遍历完成，倒数第二大数4移动至第n-2位置；下面第三轮，数集合为：{2，1，3，4，5}

  • 比较2和1的大小，2>1，则交换位置；数集合变为：{1，2，3，4，5}

  • 比较2和3的大小，2<3，则没有变化；数集合变为：{1，2，3，4，5}

  • 比较3和4的大小，3<4，则没有变化；数集合变为：{1，2，3，4，5} （这次比较没有意义的）

  • 比较4和5的大小，4<5，则没有变化；数集合变为：{1，2，3，4，5} （这次比较没有意义的）

第三轮遍历完成，相信聪明的小伙伴们已经看出来，排序已经完成，但计算机不知道，它需要再遍历1轮。

由上面例子可以看出，实际上第二轮遍历最后一次是不需要的（经过第一轮，第n-1位置的数一定是最大的），并且如果某轮遍历没有任何交换位置发生，则证明排序已完成。

代码实例

  1. function swap(i, j, arr){
  2.     var temp = arr[i];
  3.     arr[i] = arr[j];
  4.     arr[j] = temp;
  5. }
  7. /**
  8.  * 方法一：往一边冒泡
  9.  */
  10. function bubbleSort1(arr){
  11.     for(var i = 0; i < arr.length - 1; i++){
  12.         var bool = true;
  13.         for(var j = 0; j < arr.length - 1 - i; j++){
  14.             if(arr[j] > arr[j + 1]){
  15.                 swap(j, j + 1, arr);
  16.                 bool = false;
  17.             }
  18.         }
  19.         if(bool){
  20.             return arr;
  21.         }
  22.     }
  23.     return arr;
  24. }
  26. var arr = [4, 2, 5, 1, 3];
  27. console.log(bubbleSort1(arr));
  29. /**
  30.  * 方法二：同时往两边冒泡
  31.  */
  32. function bubbleSort2(arr){
  33.     var left = 0;
  34.     var rigth = arr.length - 1;
  35.     while(left < rigth){
  36.         for(var i = left; i < rigth; i++){
  37.             if(arr[i] > arr[i + 1]){
  38.                 swap(i, i + 1, arr);
  39.             }
  40.         }
  41.         rigth--;
  42.         for(var i = rigth; i > left; i--){
  43.             if(arr[i] < arr[i - 1]){
  44.                 swap(i, i-1, arr);
  45.             }
  46.         }
  47.         left++;
  48.     }
  49.     return arr;
  50. }
  52. console.log(bubbleSort2(arr));

选择排序

选择排序是种简单直观的排序方法，同样属于程序猿必懂基础排序算法之一。

  • 最坏时间复杂度：O(n)

  • 最优时间复杂度：O(n)

  • 平均时间复杂度：O(n)

  • 稳定性：不稳定

原理

  • 选取第1位数（最左边数）作为最小值min

  • 遍历对比最小值min与每个数，当某数小于最小值min，则将值赋予最小值min

  • 遍历完成，将最小值min对应的数取出，插入未排序序列的起始

  • 重复以上3步（注意：第二轮应选未排序序列的第1位数作为 最小值min），将值插入已排序序列的尾部

单看原理可能有些小伙伴不太明白，接下来结合实例演示一遍

栗子

有一组数集合：{4，2，5，1，3}，升序排序

  • 取4为最小值min

  • 4>2，将2赋予最小值min；2<5（不用管）；2>1，将1赋予最小值min；1<3（不用管）

  • 遍历完成，将最小值min=1取出来，插入未排序序列的起始（即交换1和4的位置）

第一轮遍历完成，数集合为：{1，2，5，4，3}

  • 1为已排序序列，取2为最小值min

  • 2<5,（不用管），2<4（不用管），2<3（不用管）

  • 遍历完成，将最小值min=2取出来，插入已排序序列的尾部（2已在该位置）

第二轮遍历完成，数集合为：{1，2，5，4，3}

  • 1，2为已排序序列，取5为最小值min

  • 5>4，将4赋予最小值min；4>3，将3赋予最小值min；

  • 遍历完成，将最小值min=3取出来，插入已排序序列的尾部（即交换5和3的位置）

第三轮遍历完成，数集合为：{1，2，3，4，5}

当第三轮结束排序已完成，计算机仍需要执行2次。当n较小时，选择排序会快过冒泡排序（交换所消耗CPU的时间比比较消耗CPU的时间多）。

代码实例

  1. function swap(i, j, arr){
  2.     var temp = arr[i];
  3.     arr[i] = arr[j];
  4.     arr[j] = temp;
  5. }
  7. /**
  8.  * 选择排序
  9.  */
  10. function selectionSort(arr){
  11.     if(!arr || arr.length <= 1) {
  12.         return arr;
  13.     }
  14.     for(var i = 0; i < arr.length - 1; i++){
  15.         var min = i;
  16.         for(var j = i + 1; j < arr.length; j++){
  17.             if(arr[min] > arr[j]){
  18.                 min = j;
  19.             }
  20.         }
  21.         if(min != i){
  22.             swap(i, min, arr);
  23.         }
  24.     }
  25.     return arr;
  26. }
  28. var arr = [4, 2, 5, 1, 3];
  29. console.log(selectionSort(arr));

插入排序

插入排序是种简单直观的排序方法，面试常问算法之一。

  • 最坏时间复杂度：O(n)

  • 最优时间复杂度：O(n)

  • 平均时间复杂度：O(n)

  • 稳定性：稳定

原理

  • 取第一个元素默认为已排序序列

  • 取下个元素向已排序序列向后扫描，找到已排序序列中小于该元素的位置，向该位置后插入该元素

  • 重复步骤2

单看原理可能有些小伙伴不太明白，接下来结合实例演示一遍

栗子

有一组数集合：{4，2，5，1，3}，升序排序

  • 取4作为已排序序列

  • 2<4，将2取出插入第0位置

第一轮遍历完成，数集合为：{2，4，5，1，3}

  • 取2，4作为已排序序列

  • 5>4，将5取出插入第2位置（不变）

第二轮遍历完成，数集合为：{2，4，5，1，3}

  • 取2，4，5作为已排序序列

  • 1<5，继续向后比；1<4，继续向后比；1<2，将1取出插入第0位置

第三轮遍历完成，数集合为：{1，2，4，5，3}

后续1轮遍历不做演示，大家自行推导。该排序逻辑清晰简单，向已排序序列对应位置插入新元素就行。

代码实例

  1. /**
  2.  * 插入排序
  3.  */
  4. function insertSort(arr){
  5.      for(var i = 1; i < arr.length; i++){
  6.          var temp = arr[i];
  7.         // 数组后移，让出对应位置插入新元素值
  8.          for(var j = i - 1; j >= 0 && arr[j] > temp; j--){
  9.              arr[j + 1] = arr[j];
  10.          }
  11.          arr[j + 1] = temp;
  12.      }
  13.      return arr;
  14. }
  16. var arr = [4, 2, 5, 1, 3];
  17. console.log(insertSort(arr));

快速排序

快速排序又称划分交换排序，简称快排，是冒泡排序的改进版。据说JavaScript的数组内置函数Sort，当n>10时，用的就是快速排序。

  • 最坏时间复杂度：O(n)

  • 最优时间复杂度：O(排序题 - 图1)

  • 平均时间复杂度：O(排序题 - 图2)

  • 稳定性：不稳定

原理

  • 选第一个元素作为基准值

  • 将数集大于基准值的数放在基准值右边，小于基准值的数放在基准值左边，形成2个数集

  • 递归将2个数集重复以上2步

单看原理可能有些小伙伴不太明白，接下来结合实例演示一遍

栗子

  • 选4作为基准值

  • 遍历数集，将大于4放在右边数集，小于4放在左边数集，结果为 {2，1，3} + 基准值4 + {5}

    • 数集{2，1，3}选2作为基准值

    • 遍历数集，将大于2放在右边数集，小于2放在左边数集，结果为 {1} + 基准值2 + {3}

      • 数集{1}只有一个数，作为有序数集

      • 数集{3}只有一个数，作为有序数集

    • 数集{5}只有一个数，作为有序数集

  • 组合完成数集合：{1，2，3，4，5}

快速排序的实现思想很简单，但是代码实现并不简单，主要应用递归。

代码实例

  1. /**
  2.  * 快速排序（代码参照维基百科）
  3.  */
  4. function quickSort(arr) {
  5.     var len = arr.length;
  6.     if (len < 2){
  7.         return arr;
  8.     }
  9.     var privotKey = arr[0], left = [], right = [];
  10.     for (var i = 1; i < len; i++) {
  11.         arr[i] >= privotKey && right.push(arr[i])
  12.         arr[i] < privotKey && left.push(arr[i])
  13.     }
  14.     return quickSort(left).concat(privotKey, quickSort(right));
  15. }
  17. var arr = [4, 2, 5, 1, 3];
  18. console.log(quickSort(arr));

希尔排序

希尔排序又称递减增量排序，是插入排序的的改进版。

  • 最坏时间复杂度：O(排序题 - 图3)（最好步长）

  • 最优时间复杂度：O(n)

  • 平均时间复杂度：O(随步长变化)

  • 稳定性：不稳定

原理（阅读前置条件——插入排序）

  • 设置一个步长序列

  • 取步长序列第一个元素将数集合分为改 （数集数量/元素值）个集合，对每个集合分别用插入排序进行排序

  • 取步长序列下一个元素进行第二步

  • 重复以上2步至步长为1结束

单看原理可能有些小伙伴不太明白，接下来结合实例演示一遍（其实我也看不懂自己写了啥）

栗子

有一组数集合：{4，2，5，1，3}，升序排序

  • 设置步长序列为 集合数量/2的商取整（即{n>>1}）

  • 根据步长2（5>>1），得出数集{4，5，3}和数集{2，1}

  • 分别对2个数集使用插入排序，得数集{3，4，5}和数集{1，2}

第一轮完成，数集合为：{3，1，4，2，5}

  • 根据步长1（2>>1），得出数集{3，1，4，2，5}

  • 对该数集使用插入排序，得出数集{1，2，3，4，5}

步长的选择是该排序的重要部分，只要步长最终为1（即为插入排序），则可以保证一定排序。

代码实例

  1. /**
  2.  * shell排序（代码参照维基百科）
  3.  */
  4. function shellSort(arr) {
  5.     var gap, i, j, temp;
  6.     for (gap = arr.length >> 1; gap > 0; gap >>= 1){
  7.         for (i = gap; i < arr.length; i++) {
  8.             temp = arr[i];
  9.             for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap){
  10.                 arr[j + gap] = arr[j];
  11.             }
  12.             arr[j + gap] = temp;
  13.         }
  14.     }
  15.     return arr;
  16. };

归并排序

归并排序是创建在归并操作上的排序算法，采用分治法，向下分层采用递归分治处理。

  • 最坏时间复杂度：O(排序题 - 图4)

  • 最优时间复杂度：O(排序题 - 图5)

  • 平均时间复杂度：O(排序题 - 图6)

  • 稳定性：稳定

原理

  • 将数集合分为2份

  • 如果2个数集合有序（数集合数为1），则进入步骤3；如果数集无序，则继续重复步骤1

  • 对比左右2个有序序列第一个元素中的最小值，将其取出放在新序列

  • 重复步骤3，如果一方序列值为空，则返回新序列+左有序序列+右有序序列

  • 重复步骤2-4

单看原理可能有些小伙伴不太明白，接下来结合实例演示一遍（其实我也看不懂自己写了啥）

栗子

有一组数集合：{4，2，5，1，3}，升序排序

  • 将数集合分为{4，2}和{5，1，3}

    • 数集{4，2}分为{4}和{2}

      • {4}和{2}都为有序序列

      • 取2为新序列，因为{2}取出2之后序列值为空；返回新序列+左有序序列+右有序序列（即{2}+{4}+{}）

      • 数集为{2，4}

    • 数集{5，1，3}分为{5}和{1，3}

      • {5}为有序序列

      • {1，3}分为{1}和{3}

        • {1}和{3}都为有序序列

        • 取1为新序列，因为{1}取出1之后序列值为空；返回{1}+{}+{3}

        • 数集为{1，3}

      • 取1为新序列，取3加入新序列，因为{1，3}取出1，3之后序列值为空；返回{1，3}+{5}+{}

      • 数集为{1，3，5}

    • 取1为新序列，取2加入新序列，取3加入新序列，取4加入新序列，因为{2，4}取出2，4之后序列值为空；返回{1，2，3，4}+{}+{5}

    • 数集为{1，2，3，4，5}

代码实例

  1. /**
  2.  * 归并排序（代码参照维基百科）
  3.  */
  4. function mergeSort(arr) {
  5.     var merge = function(left, right) {
  6.         var final = [];
  7.         while (left.length && right.length){
  8.             final.push(left[0] <= right[0] ? left.shift() : right.shift());
  9.         }
  10.         return final.concat(left.concat(right));
  11.     };
  12.     if (arr.length < 2){
  13.         return arr;
  14.     }
  15.     var mid = arr.length / 2;
  16.     return merge(mergeSort(arr.slice(0, parseInt(mid))), mergeSort(arr.slice(parseInt(mid))));
  17. };
  19. var arr = [4, 2, 5, 1, 3];
  20. console.log(mergeSort(arr));