前言

排序算法评价标准

时间复杂度

• 一个算法语句总的执行次数是关于问题规模N的某个函数，记为f(N)，N称为问题的规模。语句总的执行次数记为T(N)，当N不断变化时，T(N)也在变化，算法执行次数的增长速率和f(N)的增长速率相同。
• 则有T(N) = O(f(N))，这称作算法的渐进时间复杂度，简称时间复杂度。

1. 最坏时间复杂度

最坏情况下的时间复杂度称最坏时间复杂度，一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

2. 平均时间复杂度

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间，设每种情况的出现的概率为pi,平均时间复杂度则为sum(pi*f(n)) 。

3. 最好时间复杂度

最理想情况下的时间复杂度称最好时间复杂度。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

稳定性

稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序,这是我们不愿意看到的。

我们在使用排序算法或者选择排序算法时,更希望这个次序不会改变,更加稳定,所以排序算法的稳定性,是一个特别重要的参数衡量指标依据。

内排序、外排序

• 内排序：所有排序操作都在内存中完成，适用于数据规模不是特别大的情况；
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

各排序算法总结

图片名词解释：

• n: 数据规模
• k:“桶”的个数
• In-place: 占用常数内存，不占用额外内存
• Out-place: 占用额外内存

一、冒泡排序（Bubble Sort）

算法描述

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个相邻元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法思路

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到数组有序，排序完成。

算法实现

let bubbleSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
};

算法分析

• 平均时间复杂度: T(n) = O(n²)
• 最坏时间复杂度: T(n) = O(n²)：当输入的数据是反序时
• 最好时间复杂度: T(n) = O(n)：当输入的数据已经有序时，只需遍历一遍用于确认数据已有序。
• 空间复杂度: O(1)
• 稳定性: 稳定

算法改进思路

• 改进思路一：设置一标志flag，当一趟遍历过程中发生元素交换时改变flag值，而某趟当flag值没有改变，则代表数组已经有序，无需再继续排序。
• 改进思路二： 设置一标志性变量pos，用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
• 改进思路三：传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

算法动图演示

二、简单选择排序（insertion Sort）

算法描述
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法思路
具体算法描述如下：
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1…n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
算法实现
let selectSort = arr => {
for (let i = 0; i < arr.length; i++) {
Let min = arr[i]; // 初始化最小值为第一个元素
let index = i; // 最小值下标
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < min) { // 发现更小的数则交换位置
min = arr[j];
index = j;
}
}
// 将当前趟最小值移动至其最终位置
let temp = arr[i];
arr[i] = min;
arr[index] = temp;
}
};
算法分析
选择排序是时间复杂度表现最稳定的排序算法之一，无论什么数据进去都是O(n²) 的时间复杂度……所以用到它的时候，数据规模越小越好。这也是一般人想到最多的简单算法，简单粗暴。
平均时间复杂度: T(n) = O(n²)
最坏时间复杂度: T(n) = O(n²)
最好时间复杂度: T(n) = O(n²)
空间复杂度: O(1)
稳定性: 不稳定

算法改进思路
性能表现实在太稳定了，一般改进思路可以从空间换时间角度切入，减少比较次数。

算法动图演示
选择排序.gif

三、插入排序
算法描述
插入排序（insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

如果你会打扑克牌，你在抓牌整理牌时，已经无意识地用到了插入排序。

算法思路
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
算法实现
let insertSort = arr => {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j–;
}
arr[j + 1] = key;
}
return arr;
};
算法分析
平均时间复杂度: T(n) = O(n²)
最坏时间复杂度: T(n) = O(n²)：输入数组按降序排列（完全逆序）
最好时间复杂度: T(n) = O(n)：输入数组按升序排列（基本有序）
空间复杂度: O(1)
稳定性：稳定

算法改进思路
改进思路一：查找插入位置时使用二分查找的方式，减少比较次数。
算法动图演示
插入排序.gif

四、希尔排序
算法描述
1959年Shell发明； 第一个突破O(n²)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

算法思路
该方法实质上是一种分组插入方法，希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
   算法实现
   let shellSort = function (arr) {
   let len = arr.length, temp, gap = 1;
   // 动态定义间隔序列
   while (gap < len / 5) {
   gap = gap * 5 + 1;
   }
   for (gap; gap > 0; gap = Math.floor(gap / 5)) {
   for (let i = gap; i < len; i++) {
   temp = arr[i];
   for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
   arr[j + gap] = arr[j];
   }
   arr[j + gap] = temp;
   }
   }
   return arr;
   }
   算法分析
   平均时间复杂度：T(n) = O(n^1.5)
   最坏时间复杂度：T(n) = O(nlog²n）
   空间复杂度: O(1)
   稳定性: 不稳定，由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
   算法改进思路
   Shell排序的执行时间依赖于增量序列，好的增量序列的共同特征：
   ① 最后一个增量必须为1；
   ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
   有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。

但是Shell排序的时间性能显然优于直接插入排序，希尔排序的时间性能优于直接插入排序的原因：

当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
当n值较小时，n 和 n² 的差别也较小，即直接插入排序的最好时间复杂度 O(n) 和最坏时间复杂度 O(n²) 差别不大。
在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进。

使用建议：
不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n²)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法

算法演示
希尔排序.jpg

五、归并排序
算法描述
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log^n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法思路
归并排序算法思想：分而治之：

分解：把长度为n 的待排序列分解成 两个长度为n/2 的序列
治理：对每个子序列分别调用归并排序，进行递归操作。当子序列长度为1 时，序列本身有序，停止递归
合并：合并每个排序好的子序列
算法实现
let merge = (left, right) => {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
}
return result;
}

//采用自上而下的递归方法
let mergeSort = arr => {
let len = arr.length;
if (len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
算法分析
平均情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
最佳情况：T(n) = O(n)
空间复杂度: O(n)，归并排序需要一个与原数组相同长度的数组做辅助来排序
稳定性: 稳定
算法改进思路
对小规模子数组使用插入排序。用不同的方法处理小规模数组能改进大多递归算法的性能，在小数组上上，插入排序可能比并归排序更快。
测试数组是否有序。根据归并排序的特点，每次归并的两个小数组都是有序的，当 a[mid] <= a[mid + 1]时我们可以跳过merge方法，这样并不影响排序的递归调用。
不将元素复制到辅助数组。我们可以节省将数组复制到辅助数组的时间，这需要一些技巧。先克隆原数组到辅助数组，然后在之后的递归交换输入数组和辅助数组的角色（通过看代码更容易理解）
算法动图演示

六、快速排序
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据最快的排序算法之一了。

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

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

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

let quickSort = (array, left, right) => {
if (Array.isArray(array) && typeof left === ‘number’ && typeof right === ‘number’) {
if (left < right) {
let x = array[right], i = left - 1, temp;
for (let j = left; j <= right; j++) {
if (array[j] <= x) {
i++;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
}
return array;
} else {
return ‘array is not an Array or left or right is not a number!’;
}
}
方法二

let quickSort2 = arr => {
if (arr.length < 2) {
return arr;
}
let pivotindex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotindex, 1)[0];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort2(left).concat([pivot], quickSort2(right));
};
算法分析
最佳情况：T(n) = O(nlogn)，快速排序最优的情况就是每一次取到的元素都刚好平分整个数组
最差情况：T(n) = O(n²)，最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
平均情况：T(n) = O(nlogn)
稳定性：不稳定
算法改进思路
改进思路：改进选取枢轴的方法

选取随机数作为枢轴。但是随机数的生成本身是一种代价，根本减少不了算法其余部分的平均运行时间。
使用左端，右端和中心的中值做为枢轴元。经验得知，选取左端，右端，中心元素的中值会减少了快排大约 14%的比较。
每次选取数据集中的中位数做枢轴。选取中位数的可以在 O(n)时间内完成。（证明见《算法导论（第二版）》） P111 第九章中位数和顺序统计学：在平均情况下，任何顺序统计量（特别是中位数）都可以在线性时间内得到。
其他改进思路：

快速排序在处理小规模数据时的表现不好。这个时候可以改用插入排序。当数据规模小于一定程度时，改用插入排序。具体小到何种规模时，采用插入排序，这个理论上还不解，一些文章中说是 5 到 25 之间。SGI STL 中的快速排序采用的值是 10。
对于一个每个元素都完全相同的一个序列来讲，快速排序也会退化到 O(n²)。要将这种情况避免到，可以这样做：在分区的时候，将序列分为 3 堆，一堆小于中轴元素，一堆等于中轴元素，一堆大于中轴元素，下次递归调用快速排序的时候，只需对小于和大于中轴元素的两堆数据进行排序，中间等于中轴元素的一堆已经放好
算法动图演示
快速排序.gif

七、堆排序
堆排序可以说是一种利用堆的概念来排序的选择排序。

算法描述
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法思路
具体算法描述如下：

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
算法实现
/方法说明：堆排序
@param array 待排序数组/
function heapSort(array) {
console.time(‘堆排序耗时’);
if (Object.prototype.toString.call(array).slice(8, -1) === ‘Array’) {
//建堆
var heapSize = array.length, temp;
for (var I = Math.floor(heapSize / 2) - 1; I >= 0; I—) {
heapify(array, I, heapSize);
}

    //堆排序
    for (var j = heapSize - 1; j >= 1; j—) {
        temp = array[0];
        array[0] = array[j];
        array[j] = temp;
        heapify(array, 0, —heapSize);
    }
    console.timeEnd('堆排序耗时');
    return array;
} else {
    return 'array is not an Array!';
}

}
/方法说明：维护堆的性质
@param arr 数组
@param x 数组下标
@param len 堆大小/
function heapify(arr, x, len) {
if (Object.prototype.toString.call(arr).slice(8, -1) === ‘Array’ && typeof x === ‘number’) {
var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != x) {
temp = arr[x];
arr[x] = arr[largest];
arr[largest] = temp;
heapify(arr, largest, len);
}
} else {
return ‘arr is not an Array or x is not a number!’;
}
}
算法分析
调堆：O(h)
建堆：O(n)
循环调堆：O(nlogn)
总运行时间T(n) = O(nlogn) + O(n) = O(nlogn)。对于堆排序的最好情况与最坏情况的运行时间，因为最坏与最好的输入都只是影响建堆的运行时间O(1)或者O(n)，而在总体时间中占重要比例的是循环调堆的过程，即O(nlogn) + O(1) =O(nlogn) + O(n) = O(nlogn)。因此最好或者最坏情况下，堆排序的运行时间都是O(nlogn)。而且堆排序还是 原地算法（in-place algorithm） 。

平均情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
最佳情况：T(n) = O(nlogn)
空间复杂度：O(1)
稳定性：不稳定
算法动图演示
堆排序.gif

小结
文章最后再对七大经典排序算法性能分析做一次小结，加深记忆。

稳定的排序：冒泡排序，插入排序，归并排序
不稳定的排序：选择排序，堆排序，快速排序，希尔排序

平均时间复杂度T(n) = O(nlogn)：希尔排序，归并排序，快速排序，堆排序
平均时间复杂度T(n) = O(n²)：冒泡排序，简单选择排序，插入排序

最好时间复杂度T(n) = O(n)：冒泡排序，插入排序
最好时间复杂度T(n) = O(nlogn)：归并排序，快速排序，堆排序
最好时间复杂度T(n) = O(n²)：简单选择排序

最坏时间复杂度T(n) = O(nlogn)：归并排序，堆排序
最坏时间复杂度T(n) = O(n²)：冒泡排序，简单选择排序，插入排序，快速排序

空间复杂度O(1)：冒泡排序，简单选择排序，插入排序，希尔排序，堆排序
空间复杂度O(n)：归并排序
空间复杂度O(nlogn)：快速排序