常用排序算法總結
- 排序算法的分類
- 常用排序算法複雜度及穩定性
-
- 時間性能
- 空間性能
- 穩定性
- 算法特點
-
- 插入排序
- 交換排序：
- 選擇排序
- 歸并排序
- 基數排序
- 面試考點
-
- 算法改進
-
- 冒泡排序
- 快速排序
- 選擇排序算法準則
說明：本部落格适合複習《資料結構》時閱讀。
排序算法的分類
比較類，非比較類
常用排序算法複雜度及穩定性
時間性能
平均的時間性能
時間複雜度為 O(nlogn) ：快速排序、堆排序和歸并排序
時間複雜度為 O(n^2 ) ：直接插入、冒泡和簡單選擇排序
時間複雜度為 O(n) : 基數排序
當待排記錄序列按關鍵字順序有序時
直接插入和冒泡排序：O(n)
快速排序：O(n^2) 。
原表是否有序，對簡單選擇排序、堆排序、歸并排序和基數排序的時間複雜度影響不大。
空間性能
所有的簡單排序方法(直接插入、起泡和簡單選擇) 和堆排序的空間複雜度為 O(1) ；
快速排序為 O(logn)，為遞歸程式執行過程中，棧所需的輔助空間 ；
歸并排序所需輔助空間最多，其空間複雜度為O(n);
鍊式基數排序需附設隊列首尾指針 ， 則空間複雜度為 O(rd) 。
穩定性
排序算法的穩定性:若待排序的序列中，存在多個具有相同關鍵字的記錄，經過排序，這些記錄的相對次序保持不變，則稱該算法是穩定的；若經排序後，記錄的相對次序發生了改變，則稱該算法是不穩定的。
穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序
不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序
算法特點
插入排序
包括直接插入排序 ， 二分插入排序 ，希爾排序
直接插入排序：對于有 n 個資料元素的待排序序列，n - 1 次資料比較 ，最好情況 0 次資料移動 （待排序的資料已經有序）。
注意：當 n<16（一說是n<8） 時 ， 直接插入比 O(nlogn) 的排序方法快。
二分插入排序： 用二分查找方法找出應該插入的位置； 二分插入排序減少了關鍵字的比較次數 ，但資料元素的移動次數不變 ， 其時間複雜度與直接插入排序相同。
希爾排序：設定增量作為距離，按照相同距離分組，對每組進行插入排序。減小增量，重複上述步驟。
綜上，插入排序對基本已經排好序的清單有較好的時間複雜度。
交換排序：
包括冒泡排序 ， 快速排序。
快速排序：顧名思義。找到基準元素，周遊清單，大于或等于基準元素的放在基準元素的後面，小于基準元素的放在基準元素的前面。确定基準元素的位置之後，利用分治的思想快排基準元素前後的兩個子列。
基準元素的選取：快排不穩定，貿然選擇數組第一個元素可能導緻最壞結果（如果排序記錄基本有序，選擇的元素恰為最小元素，時間複雜度o(n^2)）。是以可以選擇第一個資料元素、最後一個資料元素、中間位置的資料元素的中位數。
選擇排序
包括簡單選擇排序，堆排序。
簡單選擇排序：适用于待排序元素較少的情況。
堆排序：大頂堆和小頂堆，本身是一棵完全二叉樹。
ps：堆排序涉及到了樹的相關知識，比較難了解，附上某位前輩的連結：友情連結
歸并排序
多為二路歸并排序。
二路歸并排序： 分而治之，一趟歸并的時間複雜度為 O(n)， 總共需進行 log2n 趟。
基數排序
包括計數排序，桶排序，基數排序，是根據關鍵字本身的性質進行排序，不通過待排序資料元素之間的比較。
桶排序：每個資料元素關鍵字的值将其配置設定到相應的桶中，要求關鍵字的取值範圍已知。
基數排序：“ 配置設定 ” 時，按目前“關鍵字位”所取值，将記錄配置設定到不同的“桶”中，每個隊列“桶”中記錄的 “關鍵字位” 相同；“ 收集 ”時，按目前關鍵字位取值從小到大将各“桶”首尾相鍊成一個連結清單。對每個關鍵字位均重複上兩步。
“ 配置設定 ”和“ 收集 ”的實際操作僅為修改連結清單中的指針和設定隊列的頭、尾指針；
面試考點
除了比較基本的各個排序算法的定義、特點，時間複雜度和空間複雜度分析以外，還經常考察算法的使用場景，算法的改進方法等。
算法改進
冒泡排序
方法1：設定一标志性變量pos,用于記錄每趟排序中最後一次進行交換的位置。由于pos位置之後的記錄均已交換到位,故在進行下一趟排序時隻要掃描到pos位置即可。
方法2：設定布爾變量isSorted作為标記。如果在本輪排序中，元素有交換，則說明數列無序；如果沒有元素交換，說明數列已然有序，直接跳出大循環。
方法3：雙向冒泡排序。
這裡再推薦一篇博文:友情連結
快速排序
可參考STL中的sort()函數：資料量n<8時采用插入排序，n>=8時采用快速排序。
選擇排序算法準則
一般而言，需要考慮的因素有以下四點：
設待排序元素的個數為n.
1）當n較大，則應采用時間複雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
2）當n較大，記憶體空間允許，且要求穩定性：歸并排序
3）當n較小，可采用直接插入或直接選擇排序。
直接插入排序：當元素分布有序，直接插入排序将大大減少比較次數和移動記錄的次數。
直接選擇排序 ：元素分布有序，如果不要求穩定性，選擇直接選擇排序
5）一般不使用或不直接使用傳統的冒泡排序。
6）基數排序是一種穩定的排序算法，但有一定的局限性：
1、關鍵字可分解。
2、記錄的關鍵字位數較少，如果密集更好
3、如果是數字時，最好是無符号的