1️⃣ 排序算法概述

排序不是比较大小
排序的本质是比较和交换
任何一种排序算法都没有优劣之分, 只有是否适合的场景
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

1️⃣ 冒泡排序（ Bubble Sort ）

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。
作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

2️⃣ 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2️⃣ 动图演示

849589-20171015223238449-2146169197.gif

2️⃣ 代码实现

3️⃣ 方法一

  1. function bubbleSort(arr) {
  2.     var len = arr.length;
  3.     for (var i = 0; i < len - 1; i++) {
  4.         for (var j = 0; j < len - 1 - i; j++) {
  5.             if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
  6.                 var temp = arr[j+1];        // 元素交换
  7.                 arr[j+1] = arr[j];
  8.                 arr[j] = temp;
  9.             }
  10.         }
  11.     }
  12.     return arr;
  13. }

3️⃣ 方法二

  1. var arr = [2, 3, 4, 6, 8, 7, 9, 5, 1];
  3. // 比较之后需要得出是否需要交换
  4. function compare(a, b) {
  5.   // 控制是正序还是倒序
  6.   if (a > b) return true;
  7.   else return false;
  8. }
  10. // 将数组中的 a b 位置里的值进行交换
  11. function exchange(arr, a, b) {
  12.   var temp = arr[a];
  13.   arr[a] = arr[b];
  14.   arr[b] = temp;
  15. }
  17. // 这个 sort 可以是冒泡排序也可以是选择排序也可以是其他的排序
  18. function sort(arr) {
  19.   for (let i = 0; i < arr.length; i++) {
  20.     for (let j = 0; j < arr.length - 1 - i; j++) {
  21.       if (compare(arr[j], arr[j + 1])) {
  22.         exchange(arr, j, j + 1)
  23.       }
  24.     }
  25.   }
  26. }
  28. sort(arr);
  29. console.log(arr); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

1️⃣ 选择排序（ Selection Sort ）

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

2️⃣ 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

2️⃣ 动图演示

2.gif

2️⃣ 代码实现

3️⃣ 方法一

  1. function selectionSort(arr) {
  2.     var len = arr.length;
  3.     var minIndex, temp;
  4.     for (var i = 0; i < len - 1; i++) {
  5.         minIndex = i;
  6.         for (var j = i + 1; j < len; j++) {
  7.             if (arr[j] < arr[minIndex]) {     // 寻找最小的数
  8.                 minIndex = j;                 // 将最小数的索引保存
  9.             }
  10.         }
  11.         temp = arr[i];
  12.         arr[i] = arr[minIndex];
  13.         arr[minIndex] = temp;
  14.     }
  15.     return arr;
  16. }

3️⃣ 方法二

  1. var arr = [2, 3, 4, 6, 8, 7, 9, 5, 1];
  3. // 比较之后需要得出是否需要交换
  4. function compare(a, b) {
  5.   // 控制是正序还是倒序
  6.   if (a > b) return true;
  7.   else return false;
  8. }
  10. // 将数组中的 a b 位置里的值进行交换
  11. function exchange(arr, a, b) {
  12.   var temp = arr[a];
  13.   arr[a] = arr[b];
  14.   arr[b] = temp;
  15. }
  17. // 选择排序 内层循环每一圈选出一个最大的然后放在后边
  18. function sort(arr) {
  19.   for (let i = 0; i < arr.length; i++) {
  20.     var maxIndex = 0;
  21.     for (let j = 0; j < arr.length - i; j++) {
  22.       if (compare(arr[maxIndex], arr[j])) {
  23.         maxIndex = j;
  24.       }
  25.     }
  26.     exchange(arr, maxIndex, arr.length - 1 - i)
  27.   }
  28. }
  29. sort(arr);
  30. console.log(arr); // [ 9, 8, 7, 6, 5, 4, 3, 2, 1 ]

1️⃣ 插入排序（ Insertion Sort ）

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

2️⃣ 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2️⃣ 动图演示

3.gif

2️⃣ 代码实现

  1. let arr = [1, 3, 5, 7, 9, 2, 4, 6, 8]
  3. function insertionSort(arr) {
  4.   var len = arr.length; // 9
  5.   var preIndex, current;
  6.   for (var i = 1; i < len; i++) {
  7.     preIndex = i - 1; // 每次要循环的长度就是已经排序过的长度
  8.     current = arr[i]; // 保存需要插入的项
  9.     console.log(preIndex, current);
  10.     while (preIndex >= 0 && arr[preIndex] > current) { // 将要插入的项和所有排序过的项对比
  11.       arr[preIndex + 1] = arr[preIndex]; // 遇到排序过的项大于将要插入的项，则将排序项后移
  12.       preIndex--; // 循环的出口
  13.     }
  14.     arr[preIndex + 1] = current; // 对比循环，将要排序的项插入到指定的位置
  15.   }
  16.   return arr;
  17. }
  18. console.log(insertionSort(arr)); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

1️⃣ 希尔排序（ Shell Sort ）

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  1.   1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  2.   1. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

2️⃣ 算法步骤

2️⃣ 动图演示

4.gif

2️⃣ 代码实现

1️⃣ 归并排序（ Merge Sort ）

2️⃣ 算法步骤

2️⃣ 动图演示

5.gif

2️⃣ 代码实现

1️⃣ 快速排序（ Quick Sort ）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2️⃣ 算法步骤

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。
具体算法描述如下：

  • 从数列中挑出一个元素，称为 “基准”（pivot）；
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

    2️⃣ 动图演示

    6.gif

    2️⃣ 代码实现

    3️⃣ 方法一

    ```javascript var arr = [1, 3, 5, 7, 9, 2, 4, 6, 8];

function quickSort(arr) { if (arr == null || arr == undefined || arr.length == 0) return []; // 选择一个参照 var leader = arr[0]; // 小的站左边 大的站右边 var left = []; var right = []; for (let i = 1; i < arr.length; i++) { if (arr[i] < leader) left.push(arr[i]); else right.push(arr[i]); } // 在排序后继续调用方法对两边的数据进行再次排序, 直到左右两边为空 left = quickSort(left) right = quickSort(right) left.push(leader) return left.concat(right); } console.log(quickSort(arr));

  1. <a name="xjOlD"></a>
  2. ### 3️⃣ 方法二
  3. ```javascript
  4. function quickSort(arr, left, right) {
  5.     varlen = arr.length,
  6.         partitionIndex,
  7.         left =typeofleft !='number'? 0 : left,
  8.         right =typeofright !='number'? len - 1 : right;
  10.     if(left < right) {
  11.         partitionIndex = partition(arr, left, right);
  12.         quickSort(arr, left, partitionIndex-1);
  13.         quickSort(arr, partitionIndex+1, right);
  14.     }
  15.     returnarr;
  16. }
  18. function partition(arr, left ,right) {    // 分区操作
  19.     varpivot = left,                     // 设定基准值（pivot）
  20.         index = pivot + 1;
  21.     for(vari = index; i <= right; i++) {
  22.         if(arr[i] < arr[pivot]) {
  23.             swap(arr, i, index);
  24.             index++;
  25.         }       
  26.     }
  27.     swap(arr, pivot, index - 1);
  28.     returnindex-1;
  29. }
  31. function swap(arr, i, j) {
  32.     vartemp = arr[i];
  33.     arr[i] = arr[j];
  34.     arr[j] = temp;
  35. }

1️⃣ 堆排序（ Heap Sort ）

2️⃣ 算法步骤

2️⃣ 动图演示

7.1.gif
7.2.gif

2️⃣ 代码实现

1️⃣ 计数排序（ Counting Sort ）

2️⃣ 算法步骤

2️⃣ 动图演示

8.gif

2️⃣ 代码实现

1️⃣ 桶排序（ Bucket Sort ）

2️⃣ 算法步骤

2️⃣ 动图演示

2️⃣ 代码实现

1️⃣ 基数排序（ Radix Sort ）

2️⃣ 算法步骤

2️⃣ 动图演示

10.gif

2️⃣ 代码实现

1️⃣ 简单快速排序

var arr = [2, 4, 3, 6, 8, 7, 9, 5, 1];

function quickSort(arr) {
  if (arr == null || arr == undefined || arr.length == 0) return [];
  // 选择一个参照
  var leader = arr[0];
  // 小的站左边 大的站右边
  var left = [];
  var right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < leader) left.push(arr[i]);
    else right.push(arr[i]);
  }
  // 再次筛选排序 直到剩下一个数为止
  left = quickSort(left)
  right = quickSort(right)
  left.push(leader)
  return left.concat(right);
}
console.log(quickSort(arr));

1️⃣ 标准快速排序