來源：SegmentFault 思否社區
作者：Warren
本文只是將作者學習的過程以及算法理解進行簡單的分享，提供多一個角度的理解說明，或許讓你的困惑能得以解決（代碼或說明若有問題，歡迎留言、聯繫更正！以免造成更多困惑）
如果要更深入研究這些算法的同學，社區中同類型更優秀，單個算法更深入剖析的文章也是比比皆是，這裡或許作為一個常見排序算法入門學習了解更準確
以上時間和空間複雜度會根據算法的優化有所不同
生成測試所用，包含隨機十萬條數據的數組
以下標註的時間均為對該隨機數組的數據排序的時間，這裡的時間只是作為一個參考，因為並沒有控制到只有唯一變量（每個排序算法用到的數組長度相同，但數組值不同），所以這裡的時間只反應常規情況
運行時間的計算使用 console.time
數組 sort 方法
實現也是基於快排做了很多的優化算法，以保障各種情況都能穩定較快的實現排序 查看C++實現源碼
時間：≈ 75ms
冒泡排序
原理：依次比較兩個相鄰的元素，將較大的放到右邊（升序排列）
一輪循環只找到一個最值，然後通過多次這樣的循環（所以有兩層嵌套循環），獲得一個排序結果
以下是經過簡單優化的算法實現：
時間：≈ 21899ms
returnarray}
選擇排序
原理：從剩餘未排序序列中找到最小（大）元素，放置在已排序序列的末尾位置，以此循環，直到所有元素均排序完畢
時間：≈ 6353ms
插入排序
原理：將未排序隊列中的數值，逐個與已排序隊列中的數進行比較，當出現大於或小於已排序隊列中的某個數時，進行插入操作
注意與選擇排序的區別，選擇排序是在未排序的數中找最值，然後交換位置，插入排序則是在已排序的的數中找對應的第一個相對最值
時間：≈ 2416ms
希爾排序
原理：
插入排序的一種優化
設置一個增量，將數組中的數按此增量進行分組（比如增量為4，那下標為0，4，8...的數為一組）
對分組的數進行插入排序
縮小增量
重複步驟1、2、3，直到增量為1
當增量為1時，對整個數組進行一次插入排序，輸出最後結果
時間複雜度與增量選取有關,以下算法時間複雜度為 O(n^(3/2))
非穩定排序（2個相等的數，在排序完成後，原來在前面的數還是在前面，即為穩定排序）
時間：≈ 35ms
/* 每更新一次增量就進行一次插入排序 */while(gap> 0) { /* 以下邏輯與插入排序一致，當增量變為1時即完全一致 */for(let i = gap; i < len; i++) { /* 這裡要循環到數組最後是因為要保障當前分組中的每一個數都經過排序，所以當前分組靠前的數據會被與後面的數據進行多次排序 */let current = array[i] let endIndex = i - gapwhile(endIndex>= 0&& array[endIndex] > current) { array[endIndex + gap] = array[endIndex] endIndex -= gap}array[endIndex+gap] = current }gap = Math. floor(gap/ 3) }returnarray}
分治法：把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併
歸併排序
原理：將當前數組，遞歸分組，比較大小後再一 一合併分組，是採用分治法的一個應用
獲取一個中間位置的值，然後以該位置為中心點分組
遞歸進行分組
比較當前兩個分組，將其合併為一個數組
時間：≈ 1170ms
/* 遞歸分組 */returnmerge(mergeSort( left), mergeSort( right)) }
function merge( left, right) { const result = []/* 兩個分組都有值時，逐個進行比較 */while( left.length && right.length) { if( left[ 0] <= right[ 0]) { result.push( left.shift) } else{ result.push( right.shift) }}
/* 只有一個分組時，表明其全部為最大值，直接全部放入結果數組即可 */if( left.length){ result.push(... left) }
if( right.length){ result.push(... right) }returnresult }
堆排序
分為大頂堆（子節點都小於父節點），小頂堆（子節點都大於父節點）
原理：
根據給定的數據創建堆
將堆頂和堆尾互換，將堆長度減1
遞歸步驟1、2
時間：≈ 46ms
/* 第一步先將數組構建為堆 這裡是大頂堆 */for(let i = node; i >= 0; i--) { maxHeap( array, i, length) }
/* 第二步 將堆頂元素與堆尾元素交換 再將前 (n-1) 個數重複構建堆 */for(let j = length - 1; j > 0; j--) { swap( array, 0, j) length--/* 這裡相當於把第一個葉子節點改變了，所以下面從 0 開始, 當前堆的堆尾前一個數為結束 重新構建堆 */maxHeap( array, 0, length) }
returnarray}
functionmaxHeap(array, i, length){ /* 左子節點 */let left = i* 2+ 1/* 右子節點 */let right = i* 2+ 2/* 父節點 */let parent= i
/* 找出子節點中比父節點大的數進行交換 */if(left < length && array[left] > array[ parent]) { parent= left }
/* 這裡兩個條件都觸發也沒有關係，只要保障，一個比父節點大的子節點被移上去即可 */if(right < length && array[right] > array[ parent]) { parent= right }
if( parent!== i) { swap( array,i, parent) /* 表示有數據移動，所以要重排一下數據移動後,所影響到的父子節點,也就是此時的 parent 節點和其子節點 */maxHeap( array, parent, length) }}
functionswap(arr, i, j){ vartemp = arr[i]; arr[i] = arr[j];arr[j] = temp;}
快速排序
原理：
在數組中找一個基準
數組中的數與該基準相比較，比它小的放在其前面，比它大的放在其後面（分區操作）
再遞歸的去操作基準前、後的分區
方式一：
需要 O(n) 的額外存儲空間，和歸併排序一樣
但是代碼更清晰的體現快排的思想
時間：≈ 77ms
方式二：
原地排序
時間：≈ 34ms
function fill(array, left, right) { const pivotValue = array[ left] while( left< right){ /* 右邊大於基準的數據不需要移動位置 *//* 這裡或下面的循環，一定要確保有一處把相等的情況包含在內 */while(array[ right] >= pivotValue && left< right){ right-- }/* 將右邊第一個掃描到的小於基準的數據移動到左邊的空位 */array[ left] = array[ right]
/* 左邊小於基準的數據不需要移動位置 */while(array[ left] < pivotValue && left< right){ left++ }array[ right] = array[ left] }
/* 這裡right和left 相等了 */array[ right] = pivotValue
returnright}
還有一些更好的優化，比如基準數的選取，避免最壞時間複雜度情況的發生，可自行探索
總結：
在實際項目中可能直接用到這些算法就能解決掉業務需求的情況並不多，甚至直接用 Array.sort 也能解決。
但是業務需求千變萬化，多種多樣，總有需要你從底層去更改、優化、變異算法的情況，此時就需要用你理解的這些基本算法的原理來快速解決業務問題。
SegmentFault 思否社區和文章作者展開更多互動和交流。