排序算法总结
冒泡排序
冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。
代码实现：
function bubbleSort(arr) {
if (!Array.isArray(arr) || arr.length <= 1) return;
let lastIndex = arr.length - 1;
while (lastIndex > 0) { // 当最后一个交换的元素为第一个时，说明后面全部排序完毕
let flag = true, k = lastIndex;
for (let j = 0; j < k; j++) {
if (arr[j] > arr[j + 1]) {
flag = false;
lastIndex = j; // 设置最后一次交换元素的位置
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
if (flag) break;
}
}
冒泡排序有两种优化方式。
-
一种是外层循环的优化，我们可以记录当前循环中是否发生了交换，如果没有发生交换，则说明该序列已经为有序序列了。
因此我们不需要再执行之后的外层循环，此时可以直接结束。 -
一种是内层循环的优化，我们可以记录当前循环中最后一次元素交换的位置，该位置以后的序列都是已排好的序列，因此下
一轮循环中无需再去比较。
优化后的冒泡排序，当排序序列为已排序序列时，为最好的时间复杂度为 O(n)。
冒泡排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，是稳定排序。
选择排序
选择排序的基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止。
在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。其实
我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量 min，每一次比较
仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。
代码实现：
function selectSort(array) {
let length = array.length;
// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
if (!Array.isArray(array) || length <= 1) return;
for (let i = 0; i < length - 1; i++) {
let minIndex = i; // 设置当前循环最小元素索引
for (let j = i + 1; j < length; j++) {
// 如果当前元素比最小元素索引，则更新最小元素索引
if (array[minIndex] > array[j]) {
minIndex = j;
}
}
// 交换最小元素到当前位置
// [array[i], array[minIndex]] = [array[minIndex], array[i]];
swap(array, i, minIndex);
}
return array;
}
// 交换数组中两个元素的位置
function swap(array, left, right) {
var temp = array[left];
array[left] = array[right];
array[right] = temp;
}
选择排序不管初始序列是否有序，时间复杂度都为 O(n²)。
选择排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，不是稳定排序。
插入排序
直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
插入排序核心--扑克牌思想： 就想着自己在打扑克牌，接起来一张，放哪里无所谓，再接起来一张，比第一张小，放左边，
继续接，可能是中间数，就插在中间....依次
代码实现：
function insertSort(array) {
let length = array.length;
// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
if (!Array.isArray(array) || length <= 1) return;
// 循环从 1 开始，0 位置为默认的已排序的序列
for (let i = 1; i < length; i++) {
let temp = array[i]; // 保存当前需要排序的元素
let j = i;
// 在当前已排序序列中比较，如果比需要排序的元素大，就依次往后移动位置
while (j -1 >= 0 && array[j - 1] > temp) {
array[j] = array[j - 1];
j--;
}
// 将找到的位置插入元素
array[j] = temp;
}
return array;
}
当排序序列为已排序序列时，为最好的时间复杂度 O(n)。
插入排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，是稳定排序。
希尔排序
希尔排序的基本思想是把数组按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元
素越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。
代码实现：
function hillSort(array) {
let length = array.length;
// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
if (!Array.isArray(array) || length <= 1) return;
// 第一层确定增量的大小，每次增量的大小减半
for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
// 对每个分组使用插入排序，相当于将插入排序的1换成了 n
for (let i = gap; i < length; i++) {
let temp = array[i];
let j = i;
while (j - gap >= 0 && array[j - gap] > temp) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
return array;
}
希尔排序是利用了插入排序对于已排序序列排序效果最好的特点，在一开始序列为无序序列时，将序列分为多个小的分组进行
基数排序，由于排序基数小，每次基数排序的效果较好，然后在逐步增大增量，将分组的大小增大，由于每一次都是基于上一
次排序后的结果，所以每一次都可以看做是一个基本排序的序列，所以能够最大化插入排序的优点。
简单来说就是，由于开始时每组只有很少整数，所以排序很快。之后每组含有的整数越来越多，但是由于这些数也越来越有序，
所以排序速度也很快。
希尔排序的时间复杂度根据选择的增量序列不同而不同，但总的来说时间复杂度是小于 O(n^2) 的。
插入排序是一个稳定排序，但是在希尔排序中，由于相同的元素可能在不同的分组中，所以可能会造成相同元素位置的变化，
所以希尔排序是一个不稳定的排序。
希尔排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n^s) ，空间复杂度为 O(1) ，不是稳定排序。
归并排序
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。递归的将数组两两分开直到只包含一个元素，然后
将数组排序合并，最终合并为排序好的数组。
代码实现：
function mergeSort(array) {
let length = array.length;
// 如果不是数组或者数组长度小于等于0，直接返回，不需要排序
if (!Array.isArray(array) || length === 0) return;
if (length === 1) {
return array;
}
let mid = parseInt(length >> 1), // 找到中间索引值
left = array.slice(0, mid), // 截取左半部分
right = array.slice(mid, length); // 截取右半部分
return merge(mergeSort(left), mergeSort(right)); // 递归分解后，进行排序合并
}
function merge(leftArray, rightArray) {
let result = [],
leftLength = leftArray.length,
rightLength = rightArray.length,
il = 0,
ir = 0;
// 左右两个数组的元素依次比较，将较小的元素加入结果数组中，直到其中一个数组的元素全部加入完则停止
while (il < leftLength && ir < rightLength) {
if (leftArray[il] < rightArray[ir]) {
result.push(leftArray[il++]);
} else {
result.push(rightArray[ir++]);
}
}
// 如果是左边数组还有剩余，则把剩余的元素全部加入到结果数组中。
while (il < leftLength) {
result.push(leftArray[il++]);
}
// 如果是右边数组还有剩余，则把剩余的元素全部加入到结果数组中。
while (ir < rightLength) {
result.push(rightArray[ir++]);
}
return result;
}
归并排序将整个排序序列看成一个二叉树进行分解，首先将树分解到每一个子节点，树的每一层都是一个归并排序的过程，每
一层归并的时间复杂度为 O(n)，因为整个树的高度为 lgn，所以归并排序的时间复杂度不管在什么情况下都为O(nlogn)。
归并排序的空间复杂度取决于递归的深度和用于归并时的临时数组，所以递归的深度为 logn，临时数组的大小为 n，所以归
并排序的空间复杂度为 O(n)。
归并排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(n) ，是稳定排序。
快速排序
快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据
都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码实现：
function quickSort(array, start, end) {
let length = array.length;
// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
if (!Array.isArray(array) || length <= 1 || start >= end) return;
let index = partition(array, start, end); // 将数组划分为两部分，并返回右部分的第一个元素的索引值
quickSort(array, start, index - 1); // 递归排序左半部分
quickSort(array, index + 1, end); // 递归排序右半部分
}
function partition(array, start, end) {
let pivot = array[start]; // 取第一个值为枢纽值，获取枢纽值的大小
// 当 start 等于 end 指针时结束循环
while (start < end) {
// 当 end 指针指向的值大等于枢纽值时，end 指针向前移动
while (array[end] >= pivot && start < end) {
end--;
}
// 将比枢纽值小的值交换到 start 位置
array[start] = array[end];
// 移动 start 值，当 start 指针指向的值小于枢纽值时，start 指针向后移动
while (array[start] < pivot && start < end) {
start++;
}
// 将比枢纽值大的值交换到 end 位置，进入下一次循环
array[end] = array[start];
}
// 将枢纽值交换到中间点
array[start] = pivot;
// 返回中间索引值
return start;
}
这一种方法是填空法，首先将第一个位置的数作为枢纽值，然后 end 指针向前移动，当遇到比枢纽值小的值或者 end 值
等于 start 值的时候停止，然后将这个值填入 start 的位置，然后 start 指针向后移动，当遇到比枢纽值大的值或者
start 值等于 end 值的时候停止，然后将这个值填入 end 的位置。反复循环这个过程，直到 start 的值等于 end 的
值为止。将一开始保留的枢纽值填入这个位置，此时枢纽值左边的值都比枢纽值小，枢纽值右边的值都比枢纽值大。然后在递
归左右两边的的序列。
当每次换分的结果为含 ⌊n/2⌋和 ⌈n/2⌉−1 个元素时，最好情况发生，此时递归的次数为 logn，然后每次划分的时间复杂
度为 O(n)，所以最优的时间复杂度为 O(nlogn)。一般来说只要每次换分都是常比例的划分，时间复杂度都为 O(nlogn)。
当每次换分的结果为 n-1 和 0 个元素时，最坏情况发生。划分操作的时间复杂度为 O(n)，递归的次数为 n-1，所以最坏
的时间复杂度为 O(n²)。所以当排序序列有序的时候，快速排序有可能被转换为冒泡排序。
快速排序的空间复杂度取决于递归的深度，所以最好的时候为 O(logn)，最坏的时候为 O(n)。
快速排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(logn) ，不是稳定排序。
参考资料：
关于快速排序的四种写法
堆排序
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行
交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，
便能得到一个有序序列了。
function heapSort(array) {
let length = array.length;
// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
if (!Array.isArray(array) || length <= 1) return;
buildMaxHeap(array); // 将传入的数组建立为大顶堆
// 每次循环，将最大的元素与末尾元素交换，然后剩下的元素重新构建为大顶堆
for (let i = length - 1; i > 0; i--) {
swap(array, 0, i);
adjustMaxHeap(array, 0, i); // 将剩下的元素重新构建为大顶堆
}
return array;
}
function adjustMaxHeap(array, index, heapSize) {
let iMax,
iLeft,
iRight;
while (true) {
iMax = index; // 保存最大值的索引
iLeft = 2 * index + 1; // 获取左子元素的索引
iRight = 2 * index + 2; // 获取右子元素的索引
// 如果左子元素存在，且左子元素大于最大值，则更新最大值索引
if (iLeft < heapSize && array[iMax] < array[iLeft]) {
iMax = iLeft;
}
// 如果右子元素存在，且右子元素大于最大值，则更新最大值索引
if (iRight < heapSize && array[iMax] < array[iRight]) {
iMax = iRight;
}
// 如果最大元素被更新了，则交换位置，使父节点大于它的子节点，同时将索引值跟新为被替换的值，继续检查它的子树
if (iMax !== index) {
swap(array, index, iMax);
index = iMax;
} else {
// 如果未被更新，说明该子树满足大顶堆的要求，退出循环
break;
}
}
}
// 构建大顶堆
function buildMaxHeap(array) {
let length = array.length,
iParent = parseInt(length >> 1) - 1; // 获取最后一个非叶子点的元素
for (let i = iParent; i >= 0; i--) {
adjustMaxHeap(array, i, length); // 循环调整每一个子树，使其满足大顶堆的要求
}
}
// 交换数组中两个元素的位置
function swap(array, i, j) {
let temp = array[i];
array[i] = array[j];
array[j] = temp;
}
建立堆的时间复杂度为 O(n)，排序循环的次数为 n-1，每次调整堆的时间复杂度为 O(logn)，因此堆排序的时间复杂度在
不管什么情况下都是 O(nlogn)。
堆排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(1) ，不是稳定排序。
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。排序过程：将
所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样
从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
代码实现：
function radixSort(array) {
let length = array.length;
// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
if (!Array.isArray(array) || length <= 1) return;
let bucket = [],
max = array[0],
loop;
// 确定排序数组中的最大值
for (let i = 1; i < length; i++) {
if (array[i] > max) {
max = array[i];
}
}
// 确定最大值的位数
loop = (max + '').length;
// 初始化桶
for (let i = 0; i < 10; i++) {
bucket[i] = [];
}
for (let i = 0; i < loop; i++) {
for (let j = 0; j < length; j++) {
let str = array[j] + '';
if (str.length >= i + 1) {
let k = parseInt(str[str.length - 1 - i]); // 获取当前位的值，作为插入的索引
bucket[k].push(array[j]);
} else {
// 处理位数不够的情况，高位默认为 0
bucket[0].push(array[j]);
}
}
array.splice(0, length); // 清空旧的数组
// 使用桶重新初始化数组
for (let i = 0; i < 10; i++) {
let t = bucket[i].length;
for (let j = 0; j < t; j++) {
array.push(bucket[i][j]);
}
bucket[i] = [];
}
}
return array;
}
基数排序的平均时间复杂度为 O(nk)，k 为最大元素的长度，最坏时间复杂度为 O(nk)，空间复杂度为 O(n) ，是稳定
排序。
快速排序相对于其他排序效率更高的原因
上面一共提到了8种排序的方法，在实际使用中，应用最广泛的是快速排序。快速排序相对于其他排序算法的优势在于在相同
数据量的情况下，它的运算效率最高，并且它额外所需空间最小。
我们首先从时间复杂度来判断，由于前面几种方法的时间复杂度平均情况下基本趋向于 O(n²)，因此只从时间复杂度上来看
的话，显然归并排序、堆排序和快速排序的时间复杂度最小。但是既然这几种方法的时间复杂度基本一致，并且快速排序在最
坏情况下时间的复杂度还会变为 O(n²)，那么为什么它的效率反而更高呢？
首先在对大数据量排序的时候，由于归并排序的空间复杂度为 O(n)，因此归并排序在这种情况下会需要过多的额外内存，因
此归并排序首先就被排除掉了。
接下来就剩下了堆排序和快速排序的比较。我认为堆排序相对于快速排序的效率不高的原因有两个方面。
第一个方面是对于比较操作的有效性来说。对于快速排序来说，每一次元素的比较都会确定该元素在数组中的位置，也就是在
枢纽值的左边或者右边，快速排序的每一次比较操作都是有意义的结果。而对于堆排序来说，在每一次重新调整堆的时候，我
们在迭代时，已经知道上层的节点值一定比下层的节点值大，因此当我们每次为了打乱堆结构而将最后一个元素与堆顶元素互
换时，互换后的元素一定是比下层元素小的，因此我们知道比较结果却还要在堆结构调整时去进行再一次的比较，这样的比较
是没有意义的，以此在堆排序中会产生大量的没有意义的比较操作。
第二个方面是对于缓存局部性原理的利用上来考虑的，我认为这应该是造成堆排序的效率不如快速排序的主要原因。在计算机
中利用了多级缓存的机制，来解决 cpu 计算速度与存储器数据读取速度间差距过大的问题。缓存的原理主要是基于局部性原
理，局部性原理简单来说就是，当前被访问过的数据，很有可能在一段时间内被再次访问，这被称为时间局部性。还有就是当
前访问的数据，那么它相邻的数据，也有可能在一段时间内被访问到，这被称为空间局部性。计算机缓存利用了局部性的原理
来对数据进行缓存，来尽可能少的减少磁盘的 I/O 次数，以此来提高执行效率。对于堆排序来说，它最大的问题就是它对于
空间局部性的违背，它在进行比较时，比较的并不是相邻的元素，而是与自己相隔很远的元素，这对于利用空间局部性来进行
数据缓存的计算机来说，它的很多缓存都是无效的。并且对于大数据量的排序来说，缓存的命中率就会变得很低，因此会明显
提高磁盘的 I/O 次数，并且由于堆排序的大量的无效比较，因此这样就造成了堆排序执行效率的低下。而相对来快速排序来
说，它的排序每一次都是在相邻范围内的比较，并且比较的范围越来越小，它很好的利用了局部性原理，因此它的执行效率更
高。简单来说就是在堆排序中获取一个元素的值所花费的时间比在快速排序获取一个元素的值所花费的时间要大。因此我们可
以看出，时间复杂度类似的算法，在计算机中实际执行可能会有很大的差别，因为决定算法执行效率的还有内存读取这样的其
他的因素。
参考资料
1.为什么在平均情况下快速排序比堆排序要优秀？
2.算法的时间复杂度和空间复杂度-总结
3.十大经典排序算法（动图演示）
4.各类排序算法的对比及实现