堆排序
時(shí)間復(fù)雜度：Ο(nlogn)
空間復(fù)雜度：一個(gè)輔助空間
穩(wěn)定性：不穩(wěn)定
排序（升序用大根堆屡萤，降序就用小根堆）：
- 將待排序數(shù)組A[0...n]構(gòu)造成大根堆，此時(shí)，整個(gè)數(shù)組的最大值就是堆結(jié)構(gòu)的頂端；
- 將頂端的數(shù)（A[0]）與末尾的數(shù)（A[n]）交換，此時(shí)钮莲，末尾的數(shù)為最大值；
- 剩余元素構(gòu)成待排序數(shù)組A[0...n-1]彼水，重復(fù)上述步驟崔拥，直至排序完成。
補(bǔ)充：
每個(gè)結(jié)點(diǎn)的值都大于其左凤覆、右孩子結(jié)點(diǎn)的值链瓦，稱之為大根堆；每個(gè)結(jié)點(diǎn)的值都小于其左盯桦、右孩子結(jié)點(diǎn)的值慈俯，稱之為小根堆。
優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：
- 堆排序效率相對(duì)穩(wěn)定拥峦，不像快排在最壞情況下時(shí)間復(fù)雜度會(huì)變成O(n^2)
缺點(diǎn)：
- 堆排序比較和交換次數(shù)比快速排序多贴膘，所以平均而言比快速排序慢；
使用場(chǎng)景：
- 獲取最大/小的元素略号，topK之類刑峡。如果你要在很多元素中找很少幾個(gè)top K的元素洋闽，或者在一個(gè)巨大的數(shù)據(jù)流里找到top K，堆排序更適合突梦。
- 優(yōu)先隊(duì)列喊递。需要在一組不停更新的數(shù)據(jù)中不停地找最大/小元素
快速排序
時(shí)間復(fù)雜度：O(nlogn)，有序時(shí)最差O(n^2)
空間復(fù)雜度：O(logn)~O(n) (遞歸時(shí)使用的椦羲疲空間)
穩(wěn)定性：不穩(wěn)定
排序：
- 從數(shù)列中選擇一個(gè)基準(zhǔn)元素；
- 將比基準(zhǔn)元素大的數(shù)全放到它的右邊铐伴，小于或等于它的數(shù)全放到它的左邊撮奏。
- 再對(duì)左右區(qū)間重復(fù)上述步驟，直到各區(qū)間只有一個(gè)數(shù)当宴。
補(bǔ)充：
元素的移動(dòng)：1. 挖坑法畜吊；2. 指針交換法
優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：
- 快速排序通常明顯比其他 Ο (n log n) 算法更快
缺點(diǎn)：
- 排序效率不穩(wěn)定，數(shù)列有序時(shí)效率最差
歸并排序
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(n)
穩(wěn)定性：穩(wěn)定
排序：
歸并排序的基本思想是基于合并操作户矢，即合并兩個(gè)已經(jīng)有序的序列是容易的玲献，不論這兩個(gè)序列是順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，合并操作都可以在O(m+n)時(shí)間內(nèi)完成（假設(shè)兩個(gè)有序表的長(zhǎng)度為m和n）梯浪。
- 劃分捌年。劃分?jǐn)?shù)列為相等（或大致相等）的兩部分；
- 治理挂洛。當(dāng)劃分后的子數(shù)列長(zhǎng)度大于1時(shí)礼预，遞歸排序子數(shù)列；當(dāng)子數(shù)列長(zhǎng)度等于1時(shí)虏劲，則已經(jīng)成為有序數(shù)列托酸；
- 組合。將兩個(gè)有序子數(shù)列合并為一個(gè)有序數(shù)列柒巫。
優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：
- 歸并排序是最常用的外部排序方法（當(dāng)待排序的記錄放在外存上励堡，內(nèi)存裝不下全部數(shù)據(jù)時(shí)，歸并排序仍然適用堡掏，當(dāng)然歸并排序同樣適用于內(nèi)部排序...）
缺點(diǎn)：
- 輔助空間大O(n)
- 實(shí)用性較差
直接插入排序
時(shí)間復(fù)雜度：最好情況（基本有序)：O(n) 应结、平均情況：O(n^2) 、最壞情況：O(n^2)
空間復(fù)雜度：一個(gè)輔助空間
穩(wěn)定性：穩(wěn)定
排序：
把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表泉唁。開始時(shí)有序表中只包含1個(gè)元素摊趾，無(wú)序表中包含有n-1個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素游两，將它插入到有序表中的適當(dāng)位置砾层，使之成為新的有序表，重復(fù)n-1次可完成排序過(guò)程贱案。
優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：
- 數(shù)列接近有序時(shí)時(shí)間復(fù)雜度接近O(n)
缺點(diǎn)：
- 移動(dòng)元素的次數(shù)比較多
使用場(chǎng)景：
- 當(dāng)數(shù)組基本有序的情況下適合使用直接插入排序和冒泡排序肛炮，它們?cè)诨居行虻那闆r下排序的時(shí)間復(fù)雜度接近O(n)
折半插入排序
時(shí)間復(fù)雜度：最好情況（基本有序)：O(n) 止吐、平均情況：O(n^2) 、最壞情況：O(n^2)
空間復(fù)雜度：一個(gè)輔助空間
穩(wěn)定性：穩(wěn)定
排序：
直接插入排序確認(rèn)插入位置是通過(guò)在有序序列中逐個(gè)比較得到的侨糟。既然是有序序列中確認(rèn)位置碍扔，則可以通過(guò)二分法來(lái)確認(rèn)插入位置。即通過(guò)折半查找的方式確認(rèn)插入位置秕重。
折半插入排序僅減少了元素的比較次數(shù)不同，但是沒(méi)有減少元素的移動(dòng)次數(shù)，時(shí)間復(fù)雜度O(n^2)
希爾排序
時(shí)間復(fù)雜度：比直接插入排序要高溶耘，與增量序列的選取密切相關(guān)二拐。
空間復(fù)雜度：一個(gè)輔助空間
穩(wěn)定性：不穩(wěn)定
排序：
- 確認(rèn)一個(gè)增量序列t1, t2, t3, ... , tk。其中序列遞減凳兵，且tk=1百新；
- 按照增量ti，將待排序列分割成ti個(gè)子序列（例如增量為3時(shí)庐扫，（0,3,6）饭望、(1,4,7)、(2,5,8)分別為一組）形庭；
- 分別對(duì)每個(gè)子序列進(jìn)行直接插入排序铅辞；
- 取下一個(gè)增量t(i+1)，重復(fù)2/3步操作萨醒；
- 直到當(dāng)增量tk=1時(shí)巷挥，所有序列作為一個(gè)序列來(lái)處理，完成排序验靡。
補(bǔ)充：
希爾排序又稱縮小增量排序倍宾。屬于插入類排序，是對(duì)直接插入排序的改進(jìn)胜嗓，在時(shí)間效率上有較大改進(jìn)高职。
希爾排序優(yōu)化出發(fā)點(diǎn)：
- 在序列基本有序時(shí)，直接插入排序時(shí)間復(fù)雜度可接近O(n)辞州。由此可知怔锌，在序列基本有序時(shí)，直接插入排序的效率可大大提高变过；
- 直接插入排序方法簡(jiǎn)單埃元，在n值較小時(shí)效率較高
