排序
JavaScript 原生提供了对数组元素排序的方法 arr.sort()，实现排序只需要数行代码即可实现
arr.sort((a,b) => {
return a - b
})
但以面试为导向来看，一般会考察主要是以下 5 种算法的详细细节和优化：
- 基础排序算法：
- 冒泡排序
- 插入排序
- 选择排序
- 进阶排序算法
- 归并排序
- 快速排序
Tip
排序算法的时间复杂度也是一个不能忽视的考点
在未经特别声明的情况下，都默认以「从小到大排列」为有序标准。
冒泡排序
j基本的冒泡排序的过程，就是每次从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；反之不动。每一轮操作，都会将这一轮中最大的元素放置到数组的末尾，仿佛气泡浮出水面一样，被「冒」到了数组顶部。这也是冒泡排序得名的原因。
假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。
Warning
因为每一次从头到尾的遍历都只能定位到一个元素的位置（第 n 轮可以将较大的第 n 个元素定位到倒数第 n 位上），因此元素有多少个，总的循环就要执行多少轮。
/**
* basic bubble sort
*/
function bubbleSort(arr) {
// 数组长度决定遍历次数
const len = arr.length;
// 外层循环控制遍历（从头到尾的比较+交换）次数
for(let i=0;i<len;i++) {
// 内层循环用于指示每一轮遍历两两元素的比较都是从数组的首位到[尾部-1]
for(let j=0;j<len-1;j++) {
// 若相邻元素前面的数比后面大则进行互换（使用数组解构形式赋值交换）
if(arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr; // 最后返回排序好的数组
}
其实随着外层循环的进行，数组尾部的元素会渐渐变得有序，即走完第 n 轮循环的时候，数组的后 n 个元素就已经是有序的，对于已经有序的部分可以不再进行遍历比较操作，以降低时间复杂度。
function betterBubbleSort(arr) {
const len = arr.length
for (let i = 0; i < len; i++) {
// 对内层循环的范围作了限制，对于第 i 轮，两两元素的比较从数组的首位到[第 i-1 位]
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr
}
Tip
针对「最好」的情况，即在第一次冒泡的时候数组就完全有序，我们如果对这种作出特殊的标记，可以避免不必要的遍历，从而针对特殊的情况大大降低时间复杂度，将最好情况下的时间复杂度定向优化为 O(n)。
function betterBubbleSort(arr) {
const len = arr.length;
for(let i=0;i<len;i++) {
// 加了一个标志位，用于记录是否一开始（虽然也需要进行一轮遍历才能判断）数组就完全有序
let flag = false
for(let j=0;j<len-1-i;j++) {
if(arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
// 只要发生了一次交换，就修改标志位
flag = true
}
}
// 若一次交换也没发生，则说明数组有序，直接放过
if(flag == false) return arr;
}
return arr
}
冒泡排序的时间复杂度分最好、最坏和平均来看：
- 最好时间复杂度：它对应的是数组本身有序这种情况，只需要作比较（n-1 次），而不需要做交换，时间复杂度为 O(n)
- 最坏时间复杂度： 它对应的是数组完全逆序这种情况，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n2)
- 平均时间复杂度：涉及到一些概率论的知识，这里记住平均时间复杂度是 O(n2) 即可
选择排序
选择排序是找出最小值放在头部。每次都找出当前范围内的最小值（第一次循环遍历整个数组），把它放在当前范围的头部；然后缩小排序范围，继续重复以上操作，直至数组完全有序为止。
function selectSort(arr) {
// 数组长度
const len = arr.length;
// 缓存当前区间最小值的索引
let minIndex;
// i 是当前排序区间的起点索引
for (let i = 0; i < len; i++) {
// 初始化 minIndex
minIndex = i;
// 从 i 开始遍历区间的元素
for (let j = i; j < len; j++) {
// 若当前元素比当前的最小值还小，就更新最小值的索引为 j
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// （如果最小值的索引不是当前区间的头部）对调元素，将最小值置于当前区间的头部
if(minIndex !== i) {
// 解构形式对调数组元素
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
}
return arr
}
选择排序的最好情况也好，最坏情况也罢，都是要走内层循环作比较的（两者之间的区别仅仅在于元素交换的次数不同），因此的时间复杂度都对应两层循环消耗的时间量级 O(n2)。
Tip
选择排序将较小的元素排到区间的头部，然后每次缩小比较的区间；类似于冒泡排序（优化版）的步骤，只不过冒泡排序是将较大的元素排到区间的尾部。但是选择排序是在每一轮内循环结束后才进行依一次元素交换；但冒泡排序是频繁地进行两两元素交换的。
插入排序
插入排序所有的操作都基于一个这样的前提，当前元素前面的序列是有序的。然后需要插入的当前元素从这个有序序列的后面往前去寻找，在有序序列里找到正确位置插入。
Tip
由于前面序列是有序的（从小到大），当前元素从后往前寻找，只要比较得到有序序列其中一个元素比自己小（就可以保证有序序列前面的元素都比自己小，因此一般不需要遍历完整个有序序列），即可找到正确的插入位置。通过正确地定位当前元素在有序序列里的位置、不断扩大有序数组的范围，最终达到完全排序的目的。
排序过程演示：原始数组 [5, 3, 2, 4, 1]
- 首先，单个数字一定有序，因此数组首位的这个
5可以看做是一个有序序列。 - 在这样的前提下， 可以选中第二个元素
3作为当前元素，思考它和前面那个序列[5]之间的关系。很明显，3比5小，注意这里按照插入排序的原则，靠前的较大数字要为靠后的较小数字腾出位置js[暂时空出, 5, 2, 4, 1] 当前元素 3
再往前看，发现没有更小的元素可以作比较了。那么现在空出的这个位置就是当前元素3应该待的地方[3, 5, 2, 4, 1]。以上就完成了一轮插入，有序数组[5]现在变成了有序数组[3, 5] - 沿着这个思路，继续往下走，当前元素变成了
2。对比2和5的大小，发现2比5小。按照插入排序的原则，5要往后挪，给较小元素空出一个位置：js[3, 暂时空出, 5, 4, 1] 当前元素 2
接着继续向前对比，遇到了3。对比3和2的大小，发现3比2大。按照插入排序的原则，3要往后挪，给较小元素空出一个位置：js[暂时空出, 3, 5, 4, 1] 当前元素 2
此时2前面的有序序列已经被对比完毕了。把2放到最终空出来的那个属于它的空位里去[2, 3, 5, 4, 1]。以上完成了第二轮插入，有序数组变成了[2, 3, 5]。 - 继续往下走，当前元素是
4。仍然是从后往前，首先对比4和5的大小，发现4比5小，那么5就要为更小的元素空出一个位置：js[2, 3, 暂时空出, 5, 1] 当前元素 4
向前对比，遇到了3。因为4比3大，符合从小到大的排序原则；同时已知当前这个序列是有序的，3前面的数字一定都比3小，再继续向前查找就没有意义了。因此当前空出的这个坑就是4应该待的地方[2, 3, 4, 5, 1] - 以此类推，最后一个元素
1会被插入到[2, 3, 4, 5]这个序列的头部去，最终数组得以完全排序[1, 2, 3, 4, 5]
function insertSort(arr) {
// 数组长度
const len = arr.length;
// 保存当前需要插入的元素
let temp;
// 遍历数组的元素
for (let i = 0; i < len; i++) {
// j 用于作为游标，寻找合适的插入索引位置，从当前元素开始（从后往前）
let j = i;
temp = arr[i];
// 将游标不断从后往前移动，判断前面的元素是否比当前元素大
while (j > 0 && arr[j - 1] > temp) {
// 如果是，需要将 j 前面的一个元素后移一位（则将游标再往前移动），为 temp 让出位置
arr[j] = arr[j-1];
j--
}
// 直到遇到比 temp 小的元素或者到了数组头部，插入 temp
arr[j] = temp;
}
return arr
}
- 最好时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)。
- 最坏时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O(n2)。
- 平均时间复杂度：O(n2)
归并排序
归并排序是对分治思想的典型应用，它按照分治思想的框架进行排序：
- 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
- 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的，即对每个子数组进行排）。
- 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组。
排序过程演示：原始数组 [8, 7, 6, 5, 4, 3, 2, 1]
- 分解子问题
- 将数组整个对半分
[8, 7, 6, 5,| 4, 3, 2, 1] - 对分割出的左右两个子数组各自对半分
[8, 7,| 6, 5,| 4, 3,| 2, 1] - 对四个子数组再进行各自对半分割，使得每个子数组内都只有一个元素
[8,| 7,| 6,| 5,| 4,| 3,| 2,| 1]
- 将数组整个对半分
- 解决每个子问题
- 将规模为 1 的子数组两两合并为规模为 2 的子数组，合并时确保有序
[7, 8,| 5, 6,| 3, 4,| 1, 2] - 接着将规模为 2 的按照有序原则合并为规模为 4 的子数组
[5, 6, 7, 8,| 1, 2, 3, 4]
- 将规模为 1 的子数组两两合并为规模为 2 的子数组，合并时确保有序
- 得出大问题的解
最后将规模为 4 的子数组合并为规模为 8 的数组，得到完整的有序的数组
[1, 2, 3, 4, 5, 6, 7, 8]
Tip
归并排序的核心是先通过分割再通过合并来实现，依托的是递归思想。
function mergeSort(arr) {
// 数组长度
const len = arr.length;
// 处理递归边界
if (len <= 1) {
return arr
}
// 计算数组左右分割点
const mid = Math.floor(len / 2);
// 递归分割左子数组
const leftArr = mergeSort(arr.slice(0, mid));
// 递归分割右子数组
const rightArr = mergeSort(arr.slice(mid, len));
// 递归返回后，依次递归合并左右两个有序数组（每次递归合并都是按从小到大的，因此得到的都是有序数组）
arr = mergeArr(leftArr, rightArr);
return arr
}
function mergeArr(arr1, arr2) {
// 初始化两个指针
let i = 0,
j = 0;
// 初始化结果数组
let res = [];
// 数组 arr1 长度
const len1 = arr1.length;
// 数组 arr2 长度
const len2 = arr2.length;
// 合并两个有序数组，从小到大排列
while(i<len2 && j<len2) {
if(arr1[i]<arr2[j]) {
res.push(arr1[i]);
i++;
} else {
res.push(arr2[j]);
j++;
}
}
// 考虑到其中一个子数组首先被遍历完的情况
// 需要将另一个子数组的剩余的有序元素直接拼接到结果数组中
if(i<len1) {
return res.concat(arr1.slice(i))
} else {
return res.concat(arr2.slice(j))
}
// 返回从小到大排列的有序数组
}
Tip
两个有序数组的合并使用了双指针法，可以参考 合并两个有序数组
我们把每一次切分+归并看做是一轮。对于规模为 n 的数组来说，需要切分 log(n) 次（实际是 log2n 次），因此就有 log(n) 轮。
每一轮中，切分动作都是小事情，只需要固定的几步：
// 计算分割点
const mid = Math.floor(len / 2)
// 递归分割左子数组，然后合并为有序数组
const leftArr = mergeSort(arr.slice(0, mid))
// 递归分割右子数组，然后合并为有序数组
const rightArr = mergeSort(arr.slice(mid,len))
因此单次切分对应的是常数级别的时间复杂度 O(1)；而单次合并的时间复杂度为 O(n)（其中 n 是指两个子数组的元素个数和），因此决定归并排序时间复杂度的操作就是合并操作。
log(n) 轮对应 log(n) 次合并操作，因此归并排序的时间复杂度是 O(nlog(n))
快速排序
快速排序也是基于分而治之的原则实现的，但与归并排序的区别在于，它是直接在原有的数组内部进行排序。快速排序会将原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
排序过程演示：原始数组 [5, 1, 3, 6, 2, 0, 7]
- 首先选取一个基准值（基准值的选择有多种方式，示例选取中间的值），并在左右两端分别设定指针。
[5, 1, 3, 6, 2, 0, 7]
基准
↑
↑
- 先移动左指针，直到找到一个不小于基准值的值为止；然后再移动右指针，直到找到一个不大于基准值的值为止。两端的指针满足条件时，停止移动的状态如下
[5, 1, 3, 6, 2, 0, 7]
基准
↑
↑
- 如果左右指针没有越界（即左指针在右指针的右侧）就停下了（意味着基准值左边存在较大元素或右边存在较小元素），则交换左右指针的值，可以在划分的同时就让两边的元素「相对（与基准值）有序」，同时两个指针共同向中间走一步
[5, 1, 3, 0, 2, 6, 7]
↑ 基准
↑
Tip
可能存在交换的值就是基准值的情况，如示例，但不影响比较。
- 此时 2 比 6 小，故右指针不动，左指针继续前进，此时右指针所指的值不大于 6，左指针所指的值不小于 6，故两个指针都不再移动，而且指针越界*了。
[5, 1, 3, 0, 2, 6, 7]
基准
↑
right
↑
left
- 此时可以基于左指针来划分左右两个子数组，对于左指针所指的数字来说，它左边的所有数字都比它小，右边的所有数字都比它大（也可能存在相等的情况）。由此就能够以左指针为轴心，划分出一左一右、一小一大两个子数组。
[5, 1, 3, 0, 2]
[6, 7]
- 针对两个子数组，重复执行以上操作，直到数组完全排序为止。
// 快速排序
function quickSort(arr, left = 0, right = arr.length - 1) {
// 定义递归边界，若数组只有一个元素，则没有排序必要
if (arr.length > 1) {
// lineIdex 表示划分左右子数组的索引
const lineIndex = partition(arr, left, right)
// 如果左边子数组的长度不小于 1（如果子数组只有一个元素则 left = lineIndex-1），则递归快排该子数组
if (left < lineIndex - 1) {
// 左子数组以 lineIndex-1 为右边界
quickSort(arr, left, lineIndex - 1)
}
// 如果右边子数组的长度不小于 1（如果子数组只有一个元素则 lineIndex = right），则递归快排该子数组
if (lineIndex < right) {
// 右子数组以 lineIndex 为左边界
quickSort(arr, lineIndex, right)
}
}
return arr
}
// 以基准值划分左右子数组的过程
function partition(arr, left, right) {
// 默认取中间位置元素作为基准值
let pivotValue = arr[Math.floor(left + (right - left) / 2)];
// 初始化左右指针
let i = left;
let j = right;
// 当左右指针不越界时，循环移动指针
while (i <= j) {
// 左指针所指元素若小于基准值，则一直右移左指针
while (arr[i] < pivotValue) {
i++
}
// 右指针所指元素若大于基准值，则一直左移右指针
while (arr[j] > pivotValue) {
j--
}
// 如果没有越界，但两指针已满足条件「停下」，意味着基准值左边存在较大元素或右边存在较小元素
// 则直接对调指针所指元素，确保左右两侧的大小有序（相对于基准值），并分别往中间走一步，继续执行循环，直到越界
if(i<=j) {
swap(arr, i, j);
i++;
j--;
}
}
// 指针越界后，返回左指针作为划分子数组的索引
return i;
}
// 快速排序过程中常常会在指针越界前交换左右指针的值，提取成一个独立的函数
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
快速排序的时间复杂度的好坏，是由基准值来决定的：
- 最好时间复杂度：每次选择基准值都刚好是当前子数组的中间数。这时可以确保每一次分割都能将数组分为两半，进而只需要递归 log(n) 次，和归并排序相似，最后结果也是
O(nlog(n)) - 最坏时间复杂度：每次划分取到的都是当前数组中的最大值/最小值，把这种情况代入快排的思路中，此时快排已经退化为了冒泡排序，对应的时间复杂度是
O(n^2^) - 平均时间复杂度：
O(nlog(n))