1.归并排序：
核心思想：先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。使用了分治的处理思想与递归的编程技巧。
其实归并排序是先归再并，“归”就是分解，递归地将数组从中间一分为二，直至子数组长度为1，这个过程并不涉及数组元素之间的比较。而“并”，则是将被分解的子数组两两合并（从最细分的长度为1的子数组开始合并，而长度为1的数组可被认为就是有序的，这样每次合并，子数组都已经是有序的了），这个过程涉及子数组 A 与子数组 B 之间的元素比较。
归并排序分解图（来源极客帮）
代码如下：
// 将两个已经排好序的子数组合并
// left左子数组，right右子数组
const mergeArr=(left,right)=>{
let temp=[];
let leftIndex=0;
let rightIndex=0;
let leftLen=left.length;
let rightLen=right.length;
while(leftIndex<leftLen && rightIndex<rightLen){
// 判断两个子数组的元素大小，依次插入到临时数组temp
// 下面这个判断条件使得归并排序是稳定排序
if(left[leftIndex]<=right[rightIndex]){
temp.push(left[leftIndex++]);
}
else{
temp.push(right[rightIndex++]);
}
}
// 此时某一数组可能还有剩余元素未插入temp
return temp.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const mergeSort=(arr)=>{
if(arr.length<=1)
return arr;
let mid=Math.floor(arr.length/2);
const left=arr.slice(0,mid);
const right=arr.slice(mid);
return mergeArr(mergeSort(left),mergeSort(right));
}
console.log(mergeSort([2,8,7,6,1,5,3,7]));//[1, 2, 3, 5, 6, 7, 7, 8]
归并排序性能：
（1）稳定的排序算法，值相等的元素，在排序前后相对先后顺序不变。（原因在合并函数 mergeArr 中，自己看代码就知道了）。
（2）时间复杂度：O(nlogn)，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，都是O(nlogn)。（这里的时间复杂度分析涉及数学公式推导，很有代表性，具体见极客帮王争老师的课程）。
（3）空间复杂度：归并排序不是原地排序，时间复杂度为 O(n)。（合并两个有序数组为一个有序数组时，需要借助额外的存储空间，即代码中的 temp 临时数组，长度不会超过原始数组长度，且每个合并操作结束，自动回收 temp 占用的内存，下次合并再新建 temp 数组，所以占用的额外空间并不会累加）。
2. 快速排序：待排序数组下标从 p 到 r，选择 p 到 r 之间的一个元素作为分区点（pivot）。然后遍历数组元素，将小于 pivot 的元素放到左边，将大于 pivot 的元素放到右边。一次遍历结束，数组就被分成了3个部分：（1）p 到 q-1 之间全小于 pivot；
（2）处于 q 位置处的 pivot；
（3）q+1 到 r 之间全大于 pivot。
快排分区示意图--源自极客帮
根据分治、递归的处理思想，我们可以按照以上操作递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间长度缩小为 1，就说明所有的数据都有序了。
代码如下：
// 获取 pivot 交换完后的index
const partition = (arr, pivot, left, right) => {
//注意 pivot 与 startIndex，不能取区间同一端点，而是一个取开头，另一个就取结尾
const pivotVal = arr[pivot]
let startIndex = left
for (let i = left; i < right; i++) {
if (arr[i] < pivotVal) {
[arr[i],arr[startIndex]]=[arr[startIndex],arr[i]]
startIndex++
}
}
[arr[startIndex],arr[pivot]]=[arr[pivot],arr[startIndex]]
return startIndex
}
const quickSort = (arr, begin, end) => {
if(begin>=end){
return ;
}
let pivotIndex=partition(arr,end,begin,end);
quickSort(arr,begin,pivotIndex-1);
quickSort(arr,pivotIndex+1,end);
return arr;
}
这里补充一个借助双指针确定pivot位置的分区函数，partition2。参考
//方法二 借助双指针
const partition2=(arr,pivot,left,right)=>{
const pivotVal = arr[pivot];//pivot是选取的基准原始下标
let l=left;//左指针
let r=right;//右指针
//左右指针相遇的时候退出扫描循环
while(l < r) {
//注意，如果基准选子区间最后一个元素，那么先从左指针开始扫描
// 如果基准选子区间第一个元素，就从右指针开始扫描
//左指针从左向右扫描，碰到第一个大于基准数的时候停住
while(l < r && arr[l] <= pivotVal){
l ++;
}
//右指针从右向左扫描，碰到第一个小于基准数的时候停住
while(l < r && arr[r] >= pivotVal){
r --;
}
//交换左右指针所停位置的数
[arr[l], arr[r]] = [arr[r], arr[l]];
}
//最后交换基准数与指针相遇位置的数
[arr[pivot], arr[l]] = [arr[l], arr[pivot]];
return l;
}
上面两个分区函数基准值选取的都是区间端点，不过要注意若基准取右端点，那么 partition1 中的 startIndex 取左端点，然后向右扫描；partition2 则先从左指针开始向右扫描。这个顺序不能错，否则结果不对。
上述代码中比较核心的就是 partition函数，它用来获取 pivot 在数组中的下标，确保左边元素均小于它，右边元素均大于它。由于 partition 函数设计巧妙，只涉及部分数组元素的交换，并没有占用额外的内存，所以快排是原地排序。
不过由于在 partition 中涉及交换操作，比如数组 6,8,7,6,2,4，若取 4 为 pivot，那么第一次分区操作完毕，两个 6 的相对前后顺序会改变，所以快排并不是稳定排序。
快排的时间复杂度较为麻烦，如果每次分区的操作结果都能将数组分成长度接近相等的两个小区间（对应最好情况复杂度），那快排的时间复杂度就和归并排序相同，为 O(nlogn)。
然而，分区结果很难如此均匀。一个极端的例子，就是原先已经完全有序的数组1,3,5,7,9，如果每次都选区间最后一个元素作为 pivot ，那每次分区都极不平衡。如果是对 长度为 n 的完全有序数组进行同样处理，那约需 n 次分区操作，每次分区平均处理约 n/2 个元素，这时快排的时间复杂度（最坏）退化为 O(n平方)。
利用递归树求解快排时间复杂度，其在大部分情况下的时间复杂度为 O(nlogn)，极端情况下退化到 O(n平方)。
快排的优化就是尽量使得分区结果均匀，即分区点前后两个子区间元素数量差不多，避免时间复杂度退化为 O(n平方)。
两个常见快排优化方法：
（1）三数取中法：从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。如果要排序的数组长度很大，那么就要多取几个数，比如“5数取中”、“十数取中”。
（2）随机法：每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选的很差的情况，所以平均情况下，这样选的分区点是比较好的。
快排通过与基准值比较递归地将区间分为左右子区间，这个过程中，左子区间可视为左子树，右子区间可视为右子树，而基准可视为根节点。因而可以利用快排的思想来构建二叉搜索树（Binary Search Tree）。
代码如下：
//构建BST
const createBST=function (arr,begin,end) {
if(begin>end){
return;
}
let pivotIndex=partition(arr,end,begin,end);
let root=new Node(arr[pivotIndex]);
root.leftChild=createBST(arr,begin,pivotIndex-1);
root.rightChild=createBST(arr,pivotIndex+1,end);
return root;
}
利用快排还可以实现在 O(n) 的时间复杂度内求无序数组的第 k 大元素。（k 为正整数）
我们选择数组区间 A[0…n-1] 的最后一个元素 A[n-1] 作为 pivot，对数组 A[0…n-1] 原地分区， 将数组分成三部分，A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1=K，那 A[p] 就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1] 区间，再按照上面的思路递归地在 A[p+1…n-1] 这个区间内查找。同理，如果 K < p+1，那么就在区间 A[0,...,p-1]查找。
代码如下，其中用到了上段代码的 partition 分区函数，另外以下代码中由于递归分区，每次得到的分区点下标是相对于子区间的，而k是对于原始整体数组而言的，所以将子区间的分区点下标与 k 比较时，加了 base 这个基础量。
// 寻找数组中的第k大元素（k为正整数且不大于数组长度）
const findKthMax=function (arr, base, k) {
const len=arr.length;
let partitionIndex=partition(arr,len-1,0,len-1)+base;
if(partitionIndex==k-1){
return arr[partitionIndex];
}
else if(k-1>partitionIndex){
return findKthMax(arr.slice(partitionIndex),partitionIndex,k);
}
else{
return findKthMax(arr.slice(0,partitionIndex),base,k);
}
}
const arr=[3,7,5,2,1,8];
console.log(findKthMax(arr,0,5)); // 7
归并和快速排序用的都是分治的思想，代码都通过递归来实现，过程非常相似。归并排序的重点是理解递推公式和 merge() 合并函数，理解快排的重点是理解递推公式，还有 partition()分区函数。
网友评论