有且仅有的10个常见的排序算法，东西不多，怎么就背不下来呢

就这么跟你说吧，面试中肯定会出排序算法的算法题，你只需要背下来代码+背下来他们的时间复杂度和空间复杂度就能蒙混过关。

不管你是前端还是后端，关于排序的算法有且仅有这 10个，如果你用心了，怎么会记不住呢。看完这篇文章你还没记住，就说明你是笨蛋。

好吧，最最坏的情况下，也需要记住这个8【冒泡、选择、插入、希尔、归并、快速、桶、堆】

可以把所有排序分成三类

第一类【冒泡 + 选择 + 插入 + 希尔】重点是使用【循环+交换】

第二类【归并 + 堆排序 + 快速】重点是【辅助函数 + 递归】

第三类【快速排序】他自己一组，说明很重要，使用【递归思想】

第三类【计数 + 桶 + 基数】重点是使用【额外空间桶】

一、循环+交换

1.1 冒泡排序

这个是你必须会的，我记得之前最先学的就是这个算法，因为他最简单，但是因为他的时间复杂度大，所以考的概率确实最小的，但是你怎么可以不会这么简单的排序呢？

冒泡排序分为三个，一个是基本的冒泡排序，二个改进的冒泡排序，我建议是至少记住一个基本的一个改进的。冒泡排序的时间复杂度都是 o（n^2）

改进的冒泡排序你一定要学会，因为如果你在面试中答了简单的冒泡排序，面试官一定会问你，有没有什么地方可以优化？如果你一步到位写出改进的冒泡排序说不定人家就放过你了。

1.1.1 基本的冒泡排序

记住一个关键字【双层 for 循环】

1. 外层 for 循环 i < len
2. 内层 for 循环 j 初始化为 0，j < len - i - 1
3. 使用内层 for 循环交换元素
4. 时间复杂度是 n^2， 因为有两层 for 循环
5. 注意是升序排序，还是降序排序

function bubbleSort(arr) {let len = arr.lengthfor (let i = 0; i < len; i++) {for (let j = 0; j < len - i - 1; j++) {if (arr[j] > arr[j + 1]) {let temp = arr[j + 1]arr[j + 1] = arr[j]arr[j] = temp}}}return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));

1.1.2 改进的冒泡排序

记住关键子【while 循环 + for 循环 + pos 位置信息】

1. 设置一个位置信息 pos 记录每趟排序中最后一次进行交换的位置
2. pos 初始化为0 ，在 while 循环内初始化，每次循环都重置
3. pos 位置之后的记录均已经交换到位
4. 在交换的时候 if 语句内更新 pos
5. 内层 for 循环 j < i 
6. 在下一趟排序时，只需要扫描到 pos 位置即可【说明 posm是用来改变循环终止位置的】
7. 注意 while 循环一定要有更改 while 循环条件的语句，这里就使用 pos
8.  时间复杂度还是为O(N^2)

function bubbleSort(arr) {let i = arr.length - 1while (i > 0) {let pos = 0for (let j = 0; j < i; j++) {if (arr[j] > arr[j + 1]) {// 记录位置pos = jlet temp = arr[j + 1]arr[j + 1] = arr[j]arr[j] = temp}}// 更改 while 循环条件i = pos}return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));

1.1.3 终极版的冒泡排序

关键值【while 循环和2个for循环 +下标 最大值和最小值】

1. 这个是在 1.2 的基础上再进行优化的
2. 关键是使用最大值和最小值的概念【这里是指的下标的最大最小值】
3. 正向冒泡，找到最大值
4. 反向冒泡， 找到最小值
5. 2个 for 循环，不是双层 for 循环
6. while 循环条件是 low < high 所以内部有high-- low ++的语句
7. 要定义四个变量
8. 排序趟数几乎减少了一半

function bubbleSort(arr) {let low = 0;let high = arr.length - 1let temp, jwhile (low < high) {// 注意这个是 j + 1 和 j 的交换for (j = low; j < high; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j + 1]arr[j + 1] = arr[j]arr[j] = temp}}high--// 这个 for 循环是 j - 1 和 j的交换for (j = high; j > low; j--) {if (arr[j - 1] > arr[j]) {temp = arr[j - 1]arr[j - 1] = arr[j]arr[j] = temp}}low++}return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));

1.2 选择排序

重点【双层 for 循环】

1. 找到数据结构中的最小值，并把放在第一位。
2. 选择排序的时间复杂度也是O(n^2)
3. 也是使用 双层的for循环
4. 外层 for 循环交换当前值和 最小值，外层循环小于 len - 1,因为内层循环初始化为i+1
5. 内层 for 循环用来寻找最小值【j = i + 1】
6. 使用 minIndex 存最小值的下标，初始化为 i

function selectSort(arr) {let len = arr.lengthlet temp, minIndexfor (let i = 0; i < len - 1; i++) {minIndex = ifor (let j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) {minIndex = j}}temp = arr[i]arr[i] = arr[minIndex]arr[minIndex] = temp}return arr}
var arr = [1, 10, 8, 2, 30];
console.log(selectSort(arr));

1.3 插入排序

这个插入排序也一定要会

重点【外层 for + 内层 while 】

1. 时间复杂度依旧为 O(n^2)
2. 外层使用 for 循环，初始化 i = 1【这就意味着使用j-1】
3. 内层使用 while 循环 j = i
4. 关键是 while 循环的条件
   1. 比较放在 while 循环的条件中 arr[j-1] > arr[i]
   2. 使用的是 j - 1, j--
5. 交换发生在 for 循环中
6. 适用于排小数组

function insertSort(arr) {let len = arr.lengthlet tempfor (let i = 1; i < len; i++) {temp = arr[i]let j = iwhile (j > 0 && arr[j - 1] > temp) {arr[j] = arr[j - 1]j--}arr[j] = temp}return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(insertSort(arr));

1.4 希尔排序

希尔排序可以说是特殊的插入排序

重点是有一个【间隔 + while 循环 + for 循环  + while 循环】

1. gap 初始化为 len /2，更新 gap = gap /2
2. while 循环条件是 gap > 0
3. 在插入排序的基础上外面加了一个 gap 的while循环
4. gap 是for 循环的初始值【普通插入排序是1】
5. 插入排序的 j-1 变成 j -gap
6. 大幅减少数据移动的次数

function shellSort(arr) {let len = arr.lengthlet gap = Math.floor(len / 2)while (gap > 0) {for (let i = gap; i < len; i++) {const temp = arr[i]let j = iwhile (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap]j -= gap}arr[j] = temp}gap = Math.floor(gap / 2)}return arr
}
var arr = [1, 10, 8, 2, 30];
console.log('希尔排序', shellSort(arr));

二、辅助函数+递归

2.1 归并排序

重点【两个函数 + 递归】

1. 时间复杂度是O(nlogn)
2. 将整个数组分为两个数组
3. 对两个数组分别使用递归，调用两次
4. 写一个辅助函数
5. 第二个函数类似合并两个有序数组【使用双指针】
6. 最后调用辅助函数

function merge(left, right) {let res = []let i = 0, j = 0while (i < left.length && j < right.length) {if (left[i] < right[j]) {res.push(left[i])i++}else {res.push(right[j])j++}}if (i < left.length) {res = res.concat(left.slice(i))}if (j < right.length) {res = res.concat(right.slice(j))}return res
}
function mergeSort(arr) {let len = arr.lengthif (len < 2) {return arr}let middle = Math.floor(len / 2)let left = arr.slice(0, middle)let right = arr.slice(middle)return merge(mergeSort(left), mergeSort(right))
}
var arr = [1, 10, 8, 2, 30];
console.log(mergeSort(arr));

2.2 堆排序

重点是【3个函数+递归】

1. 总共需要3个函数，其中两个辅助函数，一个构建最大堆，一个调整堆
2. 每个函数都需要调用调整堆的函数 heapify
3. heapify 递归调用自身
4. 两个 for 循环都是递减的
5. 堆的性质：在一个最大堆（或最小堆）中，堆顶元素总是数组中最大（或最小）的元素
6. 时间复杂度是O(n log n)

function heapSort(arr) {// 构建最大堆buildMaxHeap(arr);// 从最后一个非叶子节点开始向上调整堆for (let i = arr.length - 1; i > 0; i--) {// 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换[arr[0], arr[i]] = [arr[i], arr[0]];// 调整堆，使其满足最大堆性质heapify(arr, 0, i);}return arr;
}// 构建最大堆
function buildMaxHeap(arr) {const len = arr.length;// 从最后一个非叶子节点开始向上调整堆for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {heapify(arr, i, len);}
}// 调整堆
function heapify(arr, i, len) {let largest = i; // 当前节点const left = 2 * i + 1; // 左子节点const right = 2 * i + 2; // 右子节点// 如果左子节点比当前节点大，则更新最大值索引if (left < len && arr[left] > arr[largest]) {largest = left;}// 如果右子节点比当前节点大，则更新最大值索引if (right < len && arr[right] > arr[largest]) {largest = right;}// 如果最大值索引不是当前节点，则交换节点，并递归调整堆if (largest !== i) {[arr[i], arr[largest]] = [arr[largest], arr[i]];heapify(arr, largest, len);}
}var arr = [1, 10, 8, 2, 30];
console.log('堆-排序', heapSort(arr));

三、快速排序

快速排序是一定一定会考的，频率最高的算法，就算被也要背下来，你看他的名字里面有快速两个字，就说明他的重要性。

通过一趟排序将待排序记录分割成独立的两部分，其中一步跟记录的关键字均比另一部分的关键字小，则可分别将两部分记录继续进行排序，达到整个序列有序。

关键字【分治法 + 递归】

1. 时间复杂度为 O(nlogn)
2. 有一个基准，每次递归只初始化一次基准，不会手动修改
3. 有一个小于基准的数组
4. 一个大于基准的数组
5. 有一个 for 循环，有一个 continue 语句
6. 在函数返回的地方，使用递归

function quickSort(arr) {if (arr.length <=1) {return arr}let baseIndex = Math.floor(arr.length / 2)let base = arr[baseIndex]let less = []let greater = []for(let i =0; i < arr.length; i ++) {if (i === baseIndex) {continue}if(arr[i] < base) {less.push(arr[i])} else {greater.push(arr[i])}}return [...quickSort(less), base, ...quickSort(greater)]
}
var arr = [1, 10, 8, 2, 30];
console.log(quickSort(arr));

四、额外桶空间

4.1 计数排序

分布式排序，使用一个用来存储每个元素在原始数组中出现次数的临时数组，在所有元素都计数完成后，临时数组已排好序,并可以带以构建排序后的结果数组

重点【找到最大值和最小值+一个计数数组】

1. 时间复杂度是O(o+k)，k是临时计数数组的大小
2. 找出数组中的最大值最小值
3. 计算每个元素的出现次数 arr[i] -min 
4. 计数数组，重建排序后的数组
5. 适用于整数数组的排序

function countSort(arr) {// 找出最大值和最小值let min = max = arr[0]for (let i = 1; i < arr.length; i++) {if (arr[i] < min) {min = arr[i]}if (arr[i] > max) {max = arr[i]}}// 由于是计数排序适用于整数数组，所以这样初始化数组const countArr = new Array(max - min + 1).fill(0)for (let i = 0; i < arr.length; i++) {countArr[arr[i] - min]++ // 用数组下标对应一个元素}// 结果数组的 indexlet sortedIndex = 0for (let i = 0; i < countArr.length; i++) {while (countArr[i] > 0) {// 因为计数数组中减去了 min// 所以这里面要使用循环的下标 i 加上 最小值 minarr[sortedIndex] = i + minsortedIndex++countArr[i]--}}return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(countSort(arr));

4.2 桶排序

也是分布式排序，重点是【分桶+插入排序】

1. 和计数排序一样，先找到最大值和最小值
   1. 最大最小值，用于计算桶的个数
   2. 最小值，还用于把元素加入桶
2. 有两个函数
3. 第一个个函数将元素分成不同的桶
   1. 有两个参数，第二个参数是桶的大小
4. 将元素插入桶，重点是计算bucketIndex = (arr[i]-min )/ bucketSize
5. 第二个函数对桶进行排序，使用插入排序，因为插入排序用来排小数组不错
6. 时间复杂度 O(n+k)

function bucketSort(arr, bucketSize = 5) {if (arr.length ===0) {return arr}let min = arr[0]let max = arr[0]for(let i = 1; i < arr.length; i++) {if(arr[i] < min) {min = arr[i]}if (arr[i] > max) {max = arr[i]}}const bucketCount = Math.floor((max- min)/bucketSize ) + 1const bucketArr = Array.from({length: bucketCount}, () => [])for(let i =0; i < arr.length; i++) {let bucketIndex = Math.floor((arr[i] - min) / bucketSize)bucketArr[bucketIndex].push(arr[i])}let sortedArr = []for(let i = 0; i < bucketArr.length; i ++) {insertSort(bucketArr[i])sortedArr.push(...bucketArr[i])}return sortedArr
}
var arr = [1, 10, 8, 2, 30];
console.log(bucketSort(arr));

4.3 基数排序

重点是【获取最大数的位数+桶的个数时基数的大小】

1. 需要获取数组中的最大值
2. 桶的个数时基数的大小，通常是10进制就是10
3. 使用一个辅助函数获取指定位置上的数字
4. 时间复杂度是 O(n+k)

function radixSort(arr) {let maxNum = Math.max(...arr)let maxLen = `${maxNum}`.length// 通常创建桶的数量是基数的大小// Array.from 的第二个参数时map函数依次迭代let buckets = Array.from({ length: 10 }, () => [])// 获取数字num的指定位数上的数字const getDigit = (num, digit) => {// Math.pow返回基数得幂return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10}for (let i = 0; i < maxLen; i++) {for (let j = 0; j < arr.length; j++) {let digit = getDigit(arr[j], i)buckets[digit].push(arr[j])}arr = [].concat(...buckets)for (let j = 0; j < 10; j++) {buckets[j] = []}}return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(radixSort(arr));