1.歸并排序：
核心思想：先把數(shù)組從中間分成前后兩部分，然后對(duì)前后兩部分分別排序忿危，再將排好序的兩部分合并在一起达箍，這樣整個(gè)數(shù)組就有序了。使用了分治的處理思想與遞歸的編程技巧铺厨。
其實(shí)歸并排序是先歸再并缎玫，“歸”就是分解，遞歸地將數(shù)組從中間一分為二解滓，直至子數(shù)組長度為1赃磨，這個(gè)過程并不涉及數(shù)組元素之間的比較。而“并”洼裤，則是將被分解的子數(shù)組兩兩合并（從最細(xì)分的長度為1的子數(shù)組開始合并煞躬，而長度為1的數(shù)組可被認(rèn)為就是有序的，這樣每次合并逸邦，子數(shù)組都已經(jīng)是有序的了）恩沛，這個(gè)過程涉及子數(shù)組 A 與子數(shù)組 B 之間的元素比較。
代碼如下：
// 將兩個(gè)已經(jīng)排好序的子數(shù)組合并
// left左子數(shù)組缕减，right右子數(shù)組
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){
// 判斷兩個(gè)子數(shù)組的元素大小雷客，依次插入到臨時(shí)數(shù)組temp
// 下面這個(gè)判斷條件使得歸并排序是穩(wěn)定排序
if(left[leftIndex]<=right[rightIndex]){
temp.push(left[leftIndex++]);
}
else{
temp.push(right[rightIndex++]);
}
}
// 此時(shí)某一數(shù)組可能還有剩余元素未插入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）穩(wěn)定的排序算法，值相等的元素桥狡，在排序前后相對(duì)先后順序不變搅裙。（原因在合并函數(shù) mergeArr 中皱卓，自己看代碼就知道了）。
（2）時(shí)間復(fù)雜度：O(nlogn)部逮，歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序程度無關(guān)娜汁，所以其時(shí)間復(fù)雜度是非常穩(wěn)定的，不管是最好情況兄朋、最壞情況掐禁，還是平均情況，都是O(nlogn)颅和。（這里的時(shí)間復(fù)雜度分析涉及數(shù)學(xué)公式推導(dǎo)傅事，很有代表性，具體見極客幫王爭老師的課程）峡扩。
（3）空間復(fù)雜度：歸并排序不是原地排序蹭越，時(shí)間復(fù)雜度為 O(n)。（合并兩個(gè)有序數(shù)組為一個(gè)有序數(shù)組時(shí)教届，需要借助額外的存儲(chǔ)空間响鹃，即代碼中的 temp 臨時(shí)數(shù)組，長度不會(huì)超過原始數(shù)組長度案训，且每個(gè)合并操作結(jié)束买置，自動(dòng)回收 temp 占用的內(nèi)存，下次合并再新建 temp 數(shù)組萤衰，所以占用的額外空間并不會(huì)累加）。
2. 快速排序：待排序數(shù)組下標(biāo)從 p 到 r猜旬，選擇 p 到 r 之間的一個(gè)元素作為分區(qū)點(diǎn)（pivot）脆栋。然后遍歷數(shù)組元素，將小于 pivot 的元素放到左邊洒擦，將大于 pivot 的元素放到右邊椿争。一次遍歷結(jié)束，數(shù)組就被分成了3個(gè)部分：（1）p 到 q-1 之間全小于 pivot熟嫩；
（2）處于 q 位置處的 pivot秦踪；
（3）q+1 到 r 之間全大于 pivot。
根據(jù)分治掸茅、遞歸的處理思想椅邓，我們可以按照以上操作遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1 到 r 之間的數(shù)據(jù)，直到區(qū)間長度縮小為 1昧狮，就說明所有的數(shù)據(jù)都有序了景馁。
代碼如下：
// 獲取 pivot 交換完后的index
const partition = (arr, pivot, left, right) => {
//注意 pivot 與 startIndex，不能取區(qū)間同一端點(diǎn)逗鸣，而是一個(gè)取開頭合住，另一個(gè)就取結(jié)尾
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;
}
這里補(bǔ)充一個(gè)借助雙指針確定pivot位置的分區(qū)函數(shù)绰精，partition2。參考
//方法二 借助雙指針
const partition2=(arr,pivot,left,right)=>{
const pivotVal = arr[pivot];//pivot是選取的基準(zhǔn)原始下標(biāo)
let l=left;//左指針
let r=right;//右指針
//左右指針相遇的時(shí)候退出掃描循環(huán)
while(l < r) {
//注意透葛，如果基準(zhǔn)選子區(qū)間最后一個(gè)元素笨使，那么先從左指針開始掃描
// 如果基準(zhǔn)選子區(qū)間第一個(gè)元素，就從右指針開始掃描
//左指針從左向右掃描僚害，碰到第一個(gè)大于基準(zhǔn)數(shù)的時(shí)候停住
while(l < r && arr[l] <= pivotVal){
l ++;
}
//右指針從右向左掃描硫椰，碰到第一個(gè)小于基準(zhǔn)數(shù)的時(shí)候停住
while(l < r && arr[r] >= pivotVal){
r --;
}
//交換左右指針?biāo)Ｎ恢玫臄?shù)
[arr[l], arr[r]] = [arr[r], arr[l]];
}
//最后交換基準(zhǔn)數(shù)與指針相遇位置的數(shù)
[arr[pivot], arr[l]] = [arr[l], arr[pivot]];
return l;
}
上面兩個(gè)分區(qū)函數(shù)基準(zhǔn)值選取的都是區(qū)間端點(diǎn)，不過要注意若基準(zhǔn)取右端點(diǎn)贡珊，那么 partition1 中的 startIndex 取左端點(diǎn)最爬，然后向右掃描；partition2 則先從左指針開始向右掃描门岔。這個(gè)順序不能錯(cuò)爱致，否則結(jié)果不對(duì)。
上述代碼中比較核心的就是 partition函數(shù)寒随，它用來獲取 pivot 在數(shù)組中的下標(biāo)糠悯，確保左邊元素均小于它，右邊元素均大于它妻往。由于 partition 函數(shù)設(shè)計(jì)巧妙互艾，只涉及部分?jǐn)?shù)組元素的交換，并沒有占用額外的內(nèi)存讯泣，所以快排是原地排序纫普。
不過由于在 partition 中涉及交換操作，比如數(shù)組 6,8,7,6,2,4好渠，若取 4 為 pivot昨稼，那么第一次分區(qū)操作完畢，兩個(gè) 6 的相對(duì)前后順序會(huì)改變拳锚，所以快排并不是穩(wěn)定排序假栓。
快排的時(shí)間復(fù)雜度較為麻煩，如果每次分區(qū)的操作結(jié)果都能將數(shù)組分成長度接近相等的兩個(gè)小區(qū)間（對(duì)應(yīng)最好情況復(fù)雜度）霍掺，那快排的時(shí)間復(fù)雜度就和歸并排序相同匾荆，為 O(nlogn)。
然而杆烁，分區(qū)結(jié)果很難如此均勻牙丽。一個(gè)極端的例子，就是原先已經(jīng)完全有序的數(shù)組1,3,5,7,9兔魂，如果每次都選區(qū)間最后一個(gè)元素作為 pivot 剩岳，那每次分區(qū)都極不平衡。如果是對(duì) 長度為 n 的完全有序數(shù)組進(jìn)行同樣處理入热，那約需 n 次分區(qū)操作拍棕，每次分區(qū)平均處理約 n/2 個(gè)元素晓铆，這時(shí)快排的時(shí)間復(fù)雜度（最壞）退化為 O(n平方)。
利用遞歸樹求解快排時(shí)間復(fù)雜度绰播，其在大部分情況下的時(shí)間復(fù)雜度為 O(nlogn)骄噪，極端情況下退化到 O(n平方)。
快排的優(yōu)化就是盡量使得分區(qū)結(jié)果均勻蠢箩，即分區(qū)點(diǎn)前后兩個(gè)子區(qū)間元素?cái)?shù)量差不多链蕊，避免時(shí)間復(fù)雜度退化為 O(n平方)。
兩個(gè)常見快排優(yōu)化方法：
（1）三數(shù)取中法：從區(qū)間的首谬泌、尾滔韵、中間，分別取出一個(gè)數(shù)掌实，然后對(duì)比大小陪蜻，取這 3 個(gè)數(shù)的中間值作為分區(qū)點(diǎn)。這樣每間隔某個(gè)固定的長度贱鼻，取數(shù)據(jù)出來比較宴卖，將中間值作為分區(qū)點(diǎn)的分區(qū)算法，肯定要比單純?nèi)∧骋粋€(gè)數(shù)據(jù)更好邻悬。如果要排序的數(shù)組長度很大症昏，那么就要多取幾個(gè)數(shù)，比如“5數(shù)取中”父丰、“十?dāng)?shù)取中”肝谭。
（2）隨機(jī)法：每次從要排序的區(qū)間中，隨機(jī)選擇一個(gè)元素作為分區(qū)點(diǎn)蛾扇。這種方法并不能保證每次分區(qū)點(diǎn)都選的比較好攘烛，但是從概率的角度來看，也不大可能會(huì)出現(xiàn)每次分區(qū)點(diǎn)都選的很差的情況屁桑，所以平均情況下医寿，這樣選的分區(qū)點(diǎn)是比較好的栏赴。
快排通過與基準(zhǔn)值比較遞歸地將區(qū)間分為左右子區(qū)間蘑斧，這個(gè)過程中，左子區(qū)間可視為左子樹须眷，右子區(qū)間可視為右子樹竖瘾，而基準(zhǔn)可視為根節(jié)點(diǎn)。因而可以利用快排的思想來構(gòu)建二叉搜索樹（Binary Search Tree）花颗。
代碼如下：
//構(gòu)建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;
}
利用快排還可以實(shí)現(xiàn)在 O(n) 的時(shí)間復(fù)雜度內(nèi)求無序數(shù)組的第 k 大元素捕传。（k 為正整數(shù)）
我們選擇數(shù)組區(qū)間 A[0…n-1] 的最后一個(gè)元素 A[n-1] 作為 pivot，對(duì)數(shù)組 A[0…n-1] 原地分區(qū)扩劝， 將數(shù)組分成三部分庸论，A[0…p-1]职辅、A[p]、A[p+1…n-1]聂示。如果 p+1=K域携，那 A[p] 就是要求解的元素；如果 K>p+1, 說明第 K 大元素出現(xiàn)在 A[p+1…n-1] 區(qū)間鱼喉，再按照上面的思路遞歸地在 A[p+1…n-1] 這個(gè)區(qū)間內(nèi)查找秀鞭。同理，如果 K < p+1扛禽，那么就在區(qū)間 A[0,...,p-1]查找锋边。
代碼如下，其中用到了上段代碼的 partition 分區(qū)函數(shù)编曼，另外以下代碼中由于遞歸分區(qū)豆巨，每次得到的分區(qū)點(diǎn)下標(biāo)是相對(duì)于子區(qū)間的，而k是對(duì)于原始整體數(shù)組而言的灵巧，所以將子區(qū)間的分區(qū)點(diǎn)下標(biāo)與 k 比較時(shí)搀矫，加了 base 這個(gè)基礎(chǔ)量。
// 尋找數(shù)組中的第k大元素（k為正整數(shù)且不大于數(shù)組長度）
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
歸并和快速排序用的都是分治的思想刻肄，代碼都通過遞歸來實(shí)現(xiàn)瓤球，過程非常相似。歸并排序的重點(diǎn)是理解遞推公式和 merge() 合并函數(shù)敏弃，理解快排的重點(diǎn)是理解遞推公式卦羡，還有 partition()分區(qū)函數(shù)。
