數據結構——排序（空間複雜度、時間複雜度、性能等分析）

目錄

（1）插入排序 1

①直接插入排序 1

②折半排序 1

③希爾排序（縮小增量排序） 1

（2）交換排序 2

①冒泡排序 2

②快速排序 2

（3）選擇排序 2

①簡單選擇排序 2

②堆排序 2

（4）二路歸併排序 3

（5）基數排序 3

（1）插入排序

①直接插入排序

【空間】O(1)

【時間】排序過程中，向有序子表中逐個地插入元素的操作進行了n-1趟

最好O(n)，元素已有序，每插入一個元素都只需比較一次而不用移動元素

最壞O(n2)，初始為逆序，總比較次數達到最大∑i=2n i，總的移動次數達到最大∑i=2n （i+1）

平均O(n2)，初始順序隨機，總的比較次數和移動次數均約為n2/4

【比較次數與初始狀態】√

【移動次數與初始狀態】√

【一趟排序一個關鍵字到達最終位置】×，如1,2,3,4,5,0在最後一趟排序前沒有任何一個關鍵字到達最終位置

【穩定性】√ 每次插入元素總是從後向前比較再移動，不會出現相同元素相對位置變化

【適用性】基本有序，數據量不大；順序存儲、鏈式存儲（大部分排序只適用於順序存儲）

②折半排序

【空間】O(1)

【時間】相比於直接插入排序，查找插入位置上花的時間大大減少

最好O(nlog2n)，

最壞O(n2)，

平均O(n2)，

【比較次數與初始狀態】×，僅取決於表中元素個數n（二叉排序樹高）

【移動次數與初始狀態】√

【一趟排序一個關鍵字到達最終位置】×

【穩定性】√

【適用性】關鍵字較多時

③希爾排序（縮小增量排序）

將待排序表按選區的「增量」分割成若干個特殊的子表，進行直接插入排序，希爾排序每趟都會使整個序列變得更加基本有序，最後再來一趟直接插入排序效率更高

增量選取

①希爾：?n/2?，?n/4?……?n/2k?……2,1

②帕佩爾諾夫和斯塔舍維奇：2k+1，……65,33，17,9,5,3,1，其中k為大於1的整數，2k+1<n,增量序列末尾的1是額外添加的，此時時間複雜度為O（n1.5）

註：①增量序列最後一定是1 ②增量序列中的值應盡量沒有除1以外的公因子（素數）

【空間】O(1)

【時間】依賴於增量系列

最壞O(n2)

平均O(nlog2n)

n在特定範圍內，O（n1.3）

【比較次數與初始狀態】

【移動次數與初始狀態】

【一趟排序一個關鍵字到達最終位置】

【穩定性】×，相同關鍵字可能被劃分到不同的子表可能會改變他們的相對次序

【適用性】僅適用於順序存儲

（2）交換排序

①冒泡排序

在一趟排序過程中沒有發生關鍵字交換則冒泡排序結束

【空間】O(1)

【時間】

最好O(n)，初始有序，比較n-1次，移動0次

最壞O(n2)，初始逆序，需要n-1趟排序，第i趟比較n-i次，每次需要移動元素3次交換元素位置，共比較次數∑i=1n-1 (n-i）=n(n-1)/2，移動次數∑i=1n-1 3(n-i）=3n(n-1)/2

平均O(n2)

【比較次數與初始狀態】√

【移動次數與初始狀態】√

【一趟排序一個關鍵字到達最終位置】√

【穩定性】√

【適用性】

②快速排序

劃分思想，一趟後劃分為左右兩部分

【空間】遞歸需要棧，最好?log2(n+1) ?次即O(log2n)，最壞n-1次即O(n)

【時間】與劃分是否對稱有關，後者又與具體劃分演算法有關

最好O(nlog2n)，平衡劃分

最壞O(n2)，初始序列基本有序或逆序，兩個區域分別有n-1和0個元素，最大程度上的不對稱發生在每一層遞歸上

平均O(nlog2n)，是同級別里最好的

【比較次數與初始狀態】√

【移動次數與初始狀態】√

【一趟排序一個關鍵字到達最終位置】√

【穩定性】×

【適用性】初始序列越無序越高效，可根據第i趟是否有i個元素在最終位置，再比較其是否將序列劃分為為左右兩部分判斷是否是快排

（3）選擇排序

①簡單選擇排序

【空間】O(1)

【時間】移動次數很少，不會超過3(n-1)，有序時最好0次；比較次數與初始序列無關，始終是n(n-1)/2次，時間複雜度始終為O(n2)

【比較次數與初始狀態】× O(n2)

【移動次數與初始狀態】√ O(nn2)

【一趟排序一個關鍵字到達最終位置】√

【穩定性】× 第i趟找到最小元素後和第i個元素交換，可能導致相對位置發生變化，順序表交換會導致不穩定，鏈表插入版不會導致不穩定，若無特別說明則是順序表

【適用性】

②堆排序

小根堆滿足L(i)<=L(2i) && L(i)<=L(2i+1)，大根堆滿足L(i)>=L(2i) && L(i)>=L(2i+1)

建立大根堆，輸出堆頂（或者放到最後加入有序序列），將堆底元素送入堆頂，重新調整，重複以上過程直到堆中只剩一個元素

插入結點，按照完全二叉樹插入在最底層最右邊然後調整；刪除結點，與最底層最右邊結點交換再刪除葉結點

篩選（調整），從無序序列所確定的完全二叉樹第一個非葉結點，從右至左，從上至下依次調整。將結點p與其孩子值比較，若孩子大，與最大的孩子交換，p來到下一層重複以上操作直到孩子值都小於p

【空間】O(1)

【時間】O(nlog2n)，建堆O(n)， 只有n-1次向下調整，每次調整時間複雜度與樹高有關為O(log2n)（也是插入一個、刪除一個元素的複雜度）

【比較次數與初始狀態】

【移動次數與初始狀態】

【一趟排序一個關鍵字到達最終位置】√

【穩定性】× 進行篩選時有可能把後面相同關鍵字元素調整到前面

【適用性】在所有時間複雜度O(nlog2n)中空間複雜度最小，適合關鍵字較多的情況，如10000個關鍵字中選出10個最小

【題】小根堆，最大關鍵字一定存儲在對應完全二叉樹的葉子結點中，最後一個非葉子結點存儲在?n/2?，所以最大關鍵字在?n/2? +1~n之間

（4）二路歸併排序

K路歸併n個元素，趟數m= ?logkn ?

【空間】O(n)

【時間】O(nlog2n)，每一趟O(n)，共?log2n ?趟

【比較次數與初始狀態】

【移動次數與初始狀態】

【一趟排序一個關鍵字到達最終位置】×

【穩定性】√

【適用性】

（5）基數排序

藉助「分配」和「收集」對單邏輯關鍵字操作，n個關鍵字，d為關鍵字位數，r為關鍵字基的個數，如930等三位數排序，d=3（3位），r=10（0~9）

【空間】O?

【時間】一趟分配O(n)，一趟收集O?，一共需要d趟分配和收集，時間複雜度O(d(n+r))，與初始狀態無關

【比較次數與初始狀態】

【移動次數與初始狀態】

【一趟排序一個關鍵字到達最終位置】×

【穩定性】√

【適用性】關鍵字很多，但構成關鍵字的元素取值範圍很小（r很小）。如果關鍵字取值範圍也很大，如26個字母並且序列中大多數關鍵字關鍵字都不同，可以考慮使用「最高為優先」，根據最高位排成若干子序列，再對子序列進行直接插入排序

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！