一、排序的相关概念

内排序：排序数据在内存中进行排序过程。
外排序：由于数据量太大，无法一次性将所有数据放入内存中，在排序过程中需要对磁盘等外部储存器进行边访问边排序。

• 稳定性：是否会在不必要时破坏原有顺序（比如两元素等，依然交换，就是不稳定）

二、常见的十种排序方式

1.冒泡排序

冒泡排序是最常见的一种排序方式，冒泡的过程就是：

• 从头到尾将元素两两对比，并按正确顺序交换这两元素位置，以实现将最大（或最小）元素放到数列首部（或尾部），多次冒泡即实现排序目的
• 两层循环，外层控制冒泡方向，内层控制冒泡过程（比较、当即交换）

时间复杂度

• O(n2)O(n^2)O(n2)，因为无论原数列是否有序，比较次数都不会减少

空间复杂度

• $O(1)$

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

可以使用临时变量，熟练了之后也可以使用解构的方式简化操作

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

鸡尾酒排序（改进的冒泡排序）

也叫做定向冒泡排序，它的改进在于同时的冒泡两边，从低到高，然后从高到低，相当于同时把最小的数也冒泡到最前面，这个方法比冒泡更加高效

let cocktailSort= (arr) => {let L = 0let R = arr.length-1 while(L < R) {for (let i = L; i < R; i++) {[arr[i], arr[i + 1]] = arr[i] > arr[i + 1] ? [arr[i + 1], arr[i]] : [arr[i], arr[i + 1]]}R--for (let i = R; i > L; i--) {[arr[i], arr[i - 1]] = arr[i] < arr[i - 1] ? [arr[i - 1], arr[i]] : [arr[i], arr[i - 1]]}L++
}return arr
}

2.选择排序

• 排序过程
  • 将当前元素标记与后面其他元素从头到尾两两对比
  • 发现符合条件（小于标记元素）的元素就替换标记，继续寻找
  • 完成一轮比较后交换标记元素与当前元素此时已将最小元素放到数列首部
  • 将下一个元素标记，并进行以上三步操作，将次小的元素放到数列第二位
  • 依次循环完成排序
• 两层循环，外层控制方向，内层控制过程（比较、标记，最后交换）

时间复杂度

• O(n2)O(n^2)O(n2)，因为无论原数列是否有序，比较次数都不会减少

空间复杂度

• $O(1)$

let selectionSort = (arr) => {for (let i = 0; i < arr.length; i++) {min = arr[i]for (let j = i + 1; j < len; j++) {if (arr[j] < min) {let c = minmin = arr[j]arr[j] = c}}arr[i] = min}return arr
}

感觉以上课程提供的选择排序源码有些问题，并不是纯粹的选择排序，因为它里面的min存的是元素内容而不是元素下标，并且发现目标后直接交换内容而不是暂存，这两个操作也是识别选择排序的标志性操作

修改后如下（交换过程也使用了解构赋值）：

let selectionSort = (arr) => {for (let i = 0; i < arr.length; i++) {min = ifor (let j = i + 1; j < len; j++) {min = arr[j] < arr[min] ? j : min}[arr[i], arr[min]] = [arr[min], arr[i]]}return arr
}

3.快速排序

选取第一个数为基准
将比基准小的数交换到左面，比基准大的数交换到右面
对左右区间重复第二步，直到各区间只有一个数

时间复杂度

• 最坏情况就是每次要排序的元素都是数组中最小或最大的，这种情况其实就是冒泡排序了(每一次都直接排好一个元素的顺序)，就是冒泡排序的时间复杂度：T[n]=n×(n−1)=n2+nT[n] = n \\times (n-1) = n^2 + nT[n]=n×(n−1)=n2+n;
• 最好情况下是O(nlog2n)O(nlog_2n)O(nlog2​n)，推导过程如下：
  （递归算法的时间复杂度公式：$T[n]=aT[n/b]+f(n)$ ）
  
• 所以平均时间复杂度为：O(nlog2n)O(nlog_2n)O(nlog2​n)

空间复杂度

快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据：

• 最优的情况下空间复杂度为:O(log2n)O(log_2n)O(log2​n)；每一次都平分数组的情况
• 最差的情况下空间复杂度为：$O(n)$；退化为冒泡排序的情况
• 所以平均空间复杂度为O(log2n)O(log_2n)O(log2​n)

let quickSort = (arr) => {// 如果数组<=1,则直接返回if (arr.length < 2) return arr// 找基准，并把基准从原数组删除let pivot = arr.shift()// 定义左右区间let left = []let right = []// 比基准小的放在left，比基准大的放在rightfor (let i = 0; i < arr.length; i++) {if (arr[i] < pivot) {left.push(arr[i])} else {right.push(arr[i])}}// 递归return quickSort(left).concat([pivot], quickSort(right))
}

4.插入排序

将该数列的第一元素视为有序数列，后面都视为无序数列
将无序数列中的元素依次对比有序数列的元素并插入到有序数列的对应位置

时间复杂度

• 如果数组本来有序，则每个元素都与前一个元素比较一次，即最好情况下时间复杂度为：$O(n)$
• 如果数组恰好是倒序，则每一趟前面的数都要往后移，一共要执行$(n-1)+(n-2)+\dots +2+1=n\times (n-1)/2=0.5\times n2-0.5\times n$次，去掉低次幂及系数，所以最坏情况下时间复杂度为：O(n2)O(n^2)O(n2)
• 平均时间复杂度(n+n2)/2(n+n^2 )/2(n+n2)/2，所以平均时间复杂度为：O(n2)O(n^2)O(n2)

空间复杂度

插入排序算法，只需要两个变量暂存当前数，以及下标，与$n$的大小无关，所以空间复杂度为：$O(1)$

let insertionSort = (arr) => {for (let i = 0; i < arr.length; i++) {// i：未排序部分的当前位置let value = arr[i] // 准备插入的值（新牌）// j：已排序部分的当前位置let j = i - 1 // 已经排好序最后一个元素位置// 如果当已排序部分的当前元素大于valuewhile (j >= 0 && arr[j] > value) {arr[j + 1] = arr[j] // 将当前元素向后移一位，再将前一位与value比较j--}// 否则直接插入，新牌落位arr[j + 1] = value}return arr
}

二分插入排序

二分插入排序与直接插排最大的区别在于查找插入位置时使用的是二分查找的方式,，有效提高排序效率（线性查找 => 折半查找），步骤如下：

• 找插入位置：找到有序数列的中间关键元素，pk决定下次查找位置，如此重复直到找到合适位置

let insertionSort = (arr) => {for (let i = 0; i < arr.length; i++) {let low = 0let high = i - 1 // 已经排序的最大元素的位置let value = arr[i] // 将要插入的值while (low < high) { // 在已排序的元素中二分查找第一个比它大的值let mid = Math.floor((low + high) / 2) // 二分查找的中间值if (value < arr[mid]) { // 当前值比中间值小  则在左边的子数组中继续寻找high = mid - 1} else {low = mid + 1 // 当前值比中间值大   在右边的子数组继续寻找}// console.log('low', low, 'high', high) // 测试查找位置过程}for (let j = i - 1; j >= low; j--) {arr[j + 1] = arr[j]}arr[low] = value// console.log('low', low) // 测试单次排序插入位置// console.log('high', high)// console.log(arr) // 测试单次排序结果}return arr
}

5.希尔排序

希尔排序的实质是分组插入排序，该方法又称缩小增量排序，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列合并为一时再对全体记录进行一次直接插入排序

相比插入排序优点：分组后的排序是组内交换，可以将整个排序过程中平均交换次数压缩（插入排序插入一个特别小的元素时，需要其余元素全部移动，排序效率特别低。）

时间复杂度

• 最坏情况下，每两个数都要比较并交换一次，所以最坏情况下的时间复杂度为：O(n2)O(n^2)O(n2)
• 最好情况下，数组是有序的，不需要交换，只需要比较，所以最好情况下的时间复杂度为$O(n)$。
• 平均时间复杂度为：O(n1.3)O(n^1.3)O(n1.3)（这个我也不知道咋来的，书上和博客上都这样说，也没找到个具体的依据，，，）。

空间复杂度

希尔排序，只需要一个变量用于两数交换，与n的大小无关，所以空间复杂度为：$O(1)$

let shallSort = (arr) => {for (let increment = arr.length, temp; increment > 1;) {// 设置增量increment = Math.floor(increment / 3) + 1for (let i = increment; i < arr.length; i++) {if (arr[i] < arr[i - increment]) {temp = arr[i]while (i >= increment && temp < arr[i - increment]) {arr[i] = arr[i - increment]i -= increment}arr[i] = temp}}}return arr
}

看到其他小伙伴这样写希尔排序，这不是吧。。

let shallSort = (arr) => {let gap = 1// 动态定义间隔序列while (gap < arr.length / 3) {gap = gap * 3 + 1}// 上面是设置动态增量算法// 下面是其实是组内冒泡排序while (gap >= 1) {console.log(gap)for (let i = 0; i < arr.length; i++) {for (let j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {[arr[j - gap], arr[j]] = [arr[j], arr[j - gap]]}}gap = (gap - 1) / 3}return arr
}

6.堆排序

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

算法思想：将待排序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

时间复杂度

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为$O(n)$，在交换并重建堆的过程中，需交换$n-1$次，而重建堆的过程中，根据完全二叉树的性质，[log2(n−1),log2(n−2)...1][log_2(n-1),log_2(n-2)...1][log2​(n−1),log2​(n−2)...1]逐步递减，近似为nlog2nnlog_2nnlog2​n。所以堆排序时间复杂度最好和最坏情况下都是O(nlog2n)O(nlog_2n)O(nlog2​n)。

空间复杂度

堆排序不要任何辅助数组，只需要一个辅助变量，所占空间是常数与n无关，所以空间复杂度为$O(1)$

let len // 因为声明的多个函数都需要数列长度，所以把len设置成为全局变量
/* 堆调整* @param arr 需要调整的数组* @param i 预调整元素下标*/
let adjustHeap = (arr, i) => {let left = 2 * i + 1let right = 2 * i + 2// arr[i]预调整元素let max = i// 下面两步找到左右子树中最大的一个的下标if (left < len && arr[left] > arr[max]) {max = left}if (right < len && arr[right] > arr[max]) {max = right}// 将左右子树的最大值赋给父节点（里面执行说明min有变动）if (max !== i) {[arr[max], arr[i]] = [arr[i], arr[max]]adjustHeap(arr, max) // 这步递归为确保本枝杈下端的最大值提到当前父端（arr[max]）// console.log('调整结果', arr) // 调试代码时，这里打一个输出，每次排序结果都抓的死死的}
}let heapSort = arr => {len = arr.length// 构建大顶堆for (let i = Math.floor(len / 2); i >= 0; i--) {adjustHeap(arr, i)}// console.log('大顶堆：', arr) // 调试时这里也是一个关键点// 堆排序for (let i = len - 1; i > 0; i--) {// 将堆顶（树根）置换到相应位置[arr[0], arr[i]] = [arr[i], arr[0]]len-- // 此时len表示的是未排序的arr长度adjustHeap(arr, 0)}return arr
}
console.log(heapSort([6, 5, 3, 4, 2, 1]))

代码调试过程：

/* 排序前塑造大顶堆的两个目的：* 1.使数列相对有序（与想要结果相反的顺序）* 2.将最大值放到堆顶，方便排序时调换* ----------------------------------------* 起始数列：[3, 5, 1, 4, 2, 6]* 排序过程中数列发生的置换过程如下（不包含组建大顶堆过程）：* 大顶堆：[6, 5, 3, 4, 2, 1]* [1, 5, 3, 4, 2, 6] // 第〇次排序结果* [5, 1, 3, 4, 2, 6]* [5, 4, 3, 1, 2, 6]* [2, 4, 3, 1, 5, 6] // 第一次排序结果* // 在接下来的过程中即使 arr[left] > arr[max] 或 arr[right] > arr[max]，都不会发生置换,* // 因为len--这一步使得left < len 或 right < len 不满足* [4, 2, 3, 1, 5, 6]* [1, 2, 3, 4, 5, 6] // 第二次排序结果，这里其实已经排好了，但是排序过程还是会继续下去。。。* [3, 2, 1, 4, 5, 6]* [1, 2, 3, 4, 5, 6] // 第三次排序结果* [2, 1, 3, 4, 5, 6]* [1, 2, 3, 4, 5, 6] // 第四次排序结果* [1, 2, 3, 4, 5, 6] // 第五次排序结果，虽然只剩一位，但还是要走排序过程，排除“后面”还有更大的（这时len已经是1了。。。没有后面了）* 调试过程中断点位置如下：* - max = left* - max = right* - len--* 找好断点，搭配 Watch 监听器和 console.log（代码中已标出） ，过一遍排序流程，立刻感觉这是人能想出来的方法？？？*/

7.归并排序

归并排序就是递归地将原始数列递归对半分隔，直到不能再分（只剩下一个元素）后，开始从最小的数组向上归并排序

1. 向上归并排序的时候，需要一个暂存数组用来排序，
2. 将待合并的两个数组，从第一位开始比较，小的放到暂存数组，指针向后移，
3. 直到一个数组空，这时，不用判断哪个数组空了，直接将两个数组剩下的元素追加到暂存数组里，
4. 再将暂存数组排序后的元素放到原数组里，两个数组合成一个，这一趟结束。
   根据思路分析，每一趟的执行流程如下图所示：
   

/* 归并排序核心方法* @param left* @param right* @returns {[]}*/
let merge = (left, right) => {let result = []// 这里进行首次排序while (left.length > 0 && right.length > 0) {if (left[0] <= right[0]) {result.push(left.shift())} else {result.push(right.shift())}}console.log('result', result)// 当左右数组长度不等.将比较完后剩下的元素链接起来即可return result.concat(left).concat(right)
}let mergeSort = arr => {let len = arr.lengthif (len < 2) {// 递归分隔结束处，也是归并排序开始处return arr}let middle = Math.ceil(len / 2)let left = arr.slice(0, middle)let right = arr.slice(middle)console.log('left', left, 'right', right)// 这里是递归和归并的核心，先递归分隔，后归并排序return merge(mergeSort(left), mergeSort(right))
}

测试断点适合打在四个result.push（归并排序过程）和return arr（递归分隔过程）处，调试过程如下：

时间复杂度

递归算法的时间复杂度公式：$T[n]=aT[n/b]+f(n)$

无论原始数组是否是有序的，都要递归分隔并向上归并排序，所以时间复杂度始终是O(nlog2n)O(nlog_2n)O(nlog2​n)

空间复杂度

每次两个数组进行归并排序的时候，都会利用一个长度为n的数组作为辅助数组用于保存合并序列，所以空间复杂度为$O(n)$

8.计数排序

计数排序基于一个假设，假设待排序数列的所有数均为整数，且出现在（0，max）的区间之内。如果 max（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它只适用于大于0的正整数排序。
计数排序不是比较排序，对于较小的正整数序列排序的速度快于任何比较排序算法。
算法思想：

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为 i 的元素出现的次数，存入临时数组的第 i 项；
• 统计完毕后，对次数不为0的元素进行遍历，遍历区间即 [ min <= j <= max ]；
• 将统计的下标j作为填充元素，j对应的元素（值为 i 的元素出现的次数）作为元素的个数填充到目标数组，这样即完成排序

复杂度

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法

let countingSort = (arr) => {let maxValue = arr[0] // 数组中最大值let minValue = arr[0] // 数组中最小值// 求数组中最大值arr.forEach(item => { maxValue = maxValue > item ? maxValue : item })// 求数组中最小值arr.forEach(item => { minValue = minValue < item ? minValue : item })let sortedIndex = 0 // 遍历排序时的数组下标let bucket = [] // 临时用来标注的’桶‘（元素存在标注1，否则0）// 统计每种数的个数for (let i = 0; i < arr.length; i++) {if (!bucket[arr[i]]) bucket[arr[i]] = 0bucket[arr[i]]++}// console.log(bucket) // 统计（标注）完成，有必要查看一下// 从最小下标开始到最大下标，遍历赋值完成排序for (let j = minValue; j <= maxValue; j++) {while (bucket[j] > 0) {arr[sortedIndex] = jsortedIndex++bucket[j]-- // 1 => 0}}return arr
}

9.桶排序

将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。

算法思想：

设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。

一个桶使用计数排序。。。（网上好多都是这种。。。）

let bucketSort = (arr) => {// 声明一个空桶, 将数据压入桶中const bucket = []// 统计每种数的个数arr.forEach(item => {if (bucket[item] !== undefined) {bucket[item]++} else {bucket[item] = 1}})arr.length = 0console.log(bucket) // 统计（标注）完成，有必要查看一下bucket.forEach((item, index) => {if (item) {for (let i = 0; i < item; i++) {arr.push(index)}}})return arr
}

对于桶排序来说，我认为最重要的一点是桶的数量和容量，其实，桶的容量也是由桶的数量来决定的，而同的数量取决于数列的最大元素，在适当范围内，桶的数量多些，排序会更加高效。

真正的桶排序：

let insertionSort = (arr) => {for (let i = 0; i < arr.length; i++) {// i：未排序部分的当前位置let value = arr[i] // 准备插入的值（新牌）// j：已排序部分的当前位置let j = i - 1 // 已经排好序最后一个元素位置// 如果当已排序部分的当前元素大于valuewhile (j >= 0 && arr[j] > value) {arr[j + 1] = arr[j] // 将当前元素向后移一位，再将前一位与value比较j--}// 否则直接插入，新牌落位arr[j + 1] = value}return arr
}let bucketSort = (arr) => {let maxValue = arr[0] // 数组中最大值// 求数组中最大值arr.forEach(item => { maxValue = maxValue > item ? maxValue : item })// 创建桶数组（桶的个数是数组最大值开方向下取整+1，与桶容量对应，桶容量与桶的乘积必须大于等于数组最大元素值）const buckets = Array.from({ length: ~~Math.sqrt(maxValue) + 1 }, () => [])// 把元素放入对应桶子for (let i = 0; i < arr.length; i++) {// 计算需要放入的桶的序号（元素值除以桶容量）const index = ~~(arr[i] / ~~Math.sqrt(maxValue))buckets[index].push(arr[i])}// 对每个桶内的元素进行排序for (let i = 0; i < buckets.length; i++) {// 此处选取插入排序, 空间消耗少,元素少常数时间消耗短insertionSort(buckets[i])}// 使用rest参数把每个桶子数据合并return [].concat(...buckets)
}

复杂度

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

10.基数排序

将整数按位数切割成不同的数字，按每位分别分组即完成排序。不只是适用整数，也适用于字符串和特定格式的浮点数等
算法思想：

• 取得数组中的最大位数；
• 在循环中按照个/十/百等基数位进行分组，最后依次按当前基数位从0到9遍历到原数组中，即利用LSD(次位优先)进行基数排序
• 每个基数位如此循环一次即排好序

时间复杂度

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，
每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。
假如待排数据可以以k为基数，d是最高位数（例如百位是3，千位是4），则基数排序的时间复杂度将是$O(k\ast dn)$，当然d要远远小于n，因此基本上还是线性级别的。
系数d可以省略，且无论数组是否有序，都需要从个位排到最大位数，所以时间复杂度始终为$O(k\ast n)$ 。其中，n是数组长度，k为桶的数量。

空间复杂度

基数排序的空间复杂度为$O(n+k)$，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n+k个左右

let radixSort = arr => {let mod = 10 // 进制/基数，常见还有以radix为变量名let dev = 1 // 用来取进制位数据let maxDigit = 0 // 最大位数let counter = []// 获取最大位数arr.forEach(item => {let digit = item.toString().split('').lengthmaxDigit = digit > maxDigit ? digit : maxDigit})for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {for (let j = 0; j < arr.length; j++) {// 提取相应进制位的数据（个位/十位/百位...），相当于桶排序的桶的编号let bucket = Math.floor((arr[j] % mod) / dev)// 初始化统计数组if (counter[bucket] == null) {counter[bucket] = []}// 对应入组（这步相当于排序），利用LSD(次位优先)进行基数排序counter[bucket].push(arr[j])}let pos = 0for (let j = 0; j < counter.length; j++) {let value = nullif (counter[j] != null) {while ((value = counter[j].shift()) != null) {arr[pos++] = value}}}// console.log('arr', arr) // 这里可以得到按个位、十位...排序结果}return arr
}

通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}：

• 在学习与总结这些排序方法过程中，发现好多方法之间是有关联的，或是相应方法的升级版，因此对比学习会更加有效
• 测试用例：
  • [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  • [9, 7, 8, 4, 1, 6]
  • [3, 5, 1, 4, 2, 6]、[6, 5, 4, 3, 2, 1]、[1, 2, 3, 4, 5, 6]
  • [60, 50, 40, 30, 20, 10]
  • 在不同算法中使用不同用例能够大大增加算法的鲁棒性
• 示例与说明都是默认从前往后进行从小到大排序
• 演示图片来自十大经典排序算法（动图演示），gif动图无法打断，想重头开始看建议在新标签页打开图片
• 在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具
• 数学函数图像绘制：
  • https://www.desmos.com/calculator
  • https://webdemo.myscript.com/