排序演算法體會

㈠ 排序演算法穩定性的常見排序演算法的穩定性

堆排序、快速排序、希爾排序、直接選擇排序不是穩定的排序演算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序是穩定的排序演算法。
首先，排序演算法的穩定性大家應該都知道，通俗地講就是能保證排序前2個相等的數其在序列的前後位置順序和排序後它們兩個的前後位置順序相同。在簡單形式化一下，如果Ai = Aj, Ai原來在位置前，排序後Ai還是要在Aj位置前。
其次，說一下穩定性的好處。排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就 是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。
回到主題，現在分析一下常見的排序演算法的穩定性，每個都給出簡單的理由。
(1)冒泡排序
冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無 聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改 變，所以冒泡排序是一種穩定排序演算法。
(2)選擇排序
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩餘元素裡面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個 元素不用選擇了，因為只剩下它一個最大的元素了。那麼，在一趟選擇，如果當前元素比一個元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那麼 交換後穩定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9， 我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了，所以選擇排序不是一個穩定的排序演算法。
(3)插入排序
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開 始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相 等的，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，所以插入排序是穩 定的。
(4)快速排序
快速排序有兩個方向，左邊的i下標一直往右走，當a[i] <= a[center_index]，其中center_index是中樞元素的數組下標，一般取為數組第0個元素。而右邊的j下標一直往左走，當a[j] > a[center_index]。如果i和j都走不動了，i <= j, 交換a[i]和a[j],重復上面的過程，直到i>j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為 5 3 3 4 3 8 9 10 11， 現在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩定性打亂，所以快速排序是一個不穩定的排序演算法，不穩定發生在中樞元素和a[j] 交換的時刻。
(5)歸並排序
歸並排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然後把各個有序的段序列合並成一個有 序的長序列，不斷合並直到原序列全部排好序。可以發現，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩定 性。那麼，在短的有序序列合並的過程中，穩定是是否受到破壞？沒有，合並過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結 果序列的前面，這樣就保證了穩定性。所以，歸並排序也是穩定的排序演算法。
(6)基數排序
基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優 先級排序，最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以其是穩定的排序演算法。
(7)希爾排序(shell)
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小， 插入排序對於有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n^2)好一些。由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元 素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。
(8)堆排序
我們知道堆的結構是節點i的孩子為2*i和2*i+1節點，大頂堆要求父節點大於等於其2個子節點，小頂堆要求父節點小於等於其2個子節點。在一個長為n 的序列，堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n /2-1, n/2-2, ...1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把後面一個元素交換過去了，而第n/2-1個父節點把後面一個相同的元素沒 有交換，那麼這2個相同的元素之間的穩定性就被破壞了。所以，堆排序不是穩定的排序演算法。
綜上，得出結論: 選擇排序、快速排序、希爾排序、堆排序不是穩定的排序演算法，而冒泡排序、插入排序、歸並排序和基數排序是穩定的排序演算法。

㈡ 排序演算法的介紹

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序演算法，就是如何使得記錄按照要求排列的方法。排序演算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的演算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規范，要得到一個符合實際的優秀演算法，得經過大量的推理和分析。

㈢ 數據結構復習總結第八章排序

第八章排序

基本概念

文件有一組記錄組成 記錄有若干數據項組成 唯一標識記錄的數據項稱關鍵字;

排序是將文件按關鍵字的遞增(減)順序排列;

排序文件中有相同的關鍵字時 若排序後相對次序保持不變的稱穩定排序 否則稱不穩定排序;

在排序過程中 文件放在內存中處理不涉及數據的內 外存交換的稱內部排序 反之稱外部排序;

排序演算法的基本操作 )比較關鍵字的大小; )改變指向記錄的指針或移動記錄本身

評價排序方法的標准 )執行時間; )所需輔助空間 輔助空間為O( )稱就地排序;另要注意演算法的復雜程度

若關鍵字類型沒有比較運算符 可事先定義宏或函數表示比較運算

插入排序

直接插入排序

實現過程

void insertsort(seqlist R)

{

int i j;

for(i= ;i<=n;i++)

if(R[i] key< R[i ] key{

R[ ]=R[i];j=i ;

do{R[j+ ]=R[j];j ;}

while(R[ ] key <r[j].key); p=""> </r[j].key);>

R[j+1]=R[0];

}

}

演算法中引入監視哨R[0]的作用是：1)保存R[i]的副本;2)簡化邊界條件，防止循環下標越界。WiNgwit

關鍵字比較次數最大為(n+2)(n-1)/2;記錄移動次數最大為(n+4)(n-1)/2;

演算法的最好時間是O(n);最壞時間是O(n^2);平均時間是O(n^2);是一種就地的穩定的排序;

8.2.2希爾排序

實現過程：是將直接插入排序的間隔變為d。d的取值要注意：1)最後一次必為1;2)避免d值互為倍數;

關鍵字比較次數最大為n^1.25;記錄移動次數最大為1.6n^1.25;

演算法的平均時間是O(n^1.25);是一種就地的不穩定的排序;

8.3交換排序

8.3.1冒泡排序

實現過程：從下到上相鄰兩個比較，按小在上原則掃描一次，確定最小值，重復n-1次。

關鍵字比較次數最小為n-1、最大為n(n-1)/2;記錄碼含移動次數最小為0，最大為3n(n-1)/2;

演算法的最好時間是O(n);最壞時間是O(n^2);平均時間是O(n^2);是一種就地的穩定的排序;

8.3.2快速排序

實現過程：將第一個值作為基準，設置i,j指針交替從兩頭與基準比較含輪，有交換後,交換j，i。i=j時確定基準，並以其為界限將序列分為兩段。重復以上步驟。

關鍵字比較次數最好為nlog2n+nC(1)、最壞為n(n-1)/2;

演算法的最好時間是O(nlog2n);最壞時間是O(n^2);平均時間是談模信O(nlog2n);輔助空間為O(log2n);是一種不穩定排序;

8.4選擇排序

8.4.1直接選擇排序

實現過程：選擇序列中最小的插入第一位，在剩餘的序列中重復上一步，共重復n-1次。

關鍵字比較次數為n(n-1)/2;記錄移動次數最小為0，最大為3(n-1);

演算法的最好時間是O(n^2);最壞時間是O(n^2);平均時間是O(n^2);是一種就地的不穩定的排序;

8.4.2堆排序

實現過程：把序列按層次填入完全二叉樹，調整位置使雙親大於或小於孩子，建立初始大根或小根堆，調整樹根與最後一個葉子的位置，排除該葉子重新調整位置。

演算法的最好時間是O(nlog2n);最壞時間是O(nlog2n);平均時間是O(nlog2n);是一種就地的不穩定排序;

8.5歸並排序

實現過程：將初始序列分為2個一組，最後單數輪空，對每一組排序後作為一個單元，對2個單元排序，直到結束。

演算法的最好時間是O(nlog2n);最壞時間是O(nlog2n);平均時間是O(nlog2n);輔助空間為O(n);是一種穩定排序;

8.6分配排序

8.6.1箱排序

實現過程：按關鍵字的取值范圍確定箱子的個數，將序列按關鍵字放入箱中，輸出非空箱的關鍵字。

在桶內分配和收集，及對各桶進行插入排序的時間為O(n),演算法的期望時間是O(n),最壞時間是O(n^2)。

8.6.2基數排序

實現過程：按基數設置箱子，對關鍵字從低位到高位依次進行箱排序。

演算法的最好時間是O(d*n+d*rd);最壞時間是O(d*n+d*rd);平均時間是O(d*n+d*rd);輔助空間O(n+rd);是一種穩定排序;

8.7各種內部排序方法的比較和選擇

按平均時間復雜度分為：

1) 平方階排序：直接插入、直接選擇、冒泡排序;

2) 線性對數階：快速排序、堆排序、歸並排序;

3) 指數階：希爾排序;

4) 線性階：箱排序、基數排序。

選擇合適排序方法的因素：1)待排序的記錄數;2)記錄的大小;3)關鍵字的結構和初始狀態;4)對穩定性的要求;5)語言工具的條件;6)存儲結構;7)時間和輔助空間復雜度。

結論：

1) 若規模較小可採用直接插入或直接選擇排序;

2) 若文件初始狀態基本有序可採用直接插入、冒泡或隨機快速排序;

3) 若規模較大可採用快速排序、堆排序或歸並排序;

4) 任何藉助於比較的排序，至少需要O(nlog2n)的時間，箱排序和基數排序只適用於有明顯結構特徵的關鍵字;

5) 有的語言沒有提供指針及遞歸，使歸並、快速、基數排序演算法復雜;

6) 記錄規模較大時為避免大量移動記錄可用鏈表作為存儲結構，如插入、歸並、基數排序，但快速、堆排序在鏈表上難以實現，可提取關鍵字建立索引表，然後對索引表排序。

附二:

第八章排序

*************************************************************************************

記錄中可用某一項來標識一個記錄，則稱為關鍵字項，該數據項的值稱為關鍵字。

排序是使文件中的記錄按關鍵字遞增(或遞減)次序排列起來。·基本操作：比較關鍵字大小;改變指向記錄的指針或移動記錄。

·存儲結構：順序結構、鏈表結構、索引結構。

經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變,則稱這種排序方法是穩定的，否則排序演算法是不穩定的。

排序過程中不涉及數據的內、外存交換則稱之為"內部排序"(內排序)，反之，若存在數據的內外存交換，則稱之為外排序。

內部排序方法可分五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。

評價排序演算法好壞的標准主要有兩條：執行時間和所需的輔助空間，另外演算法的復雜程序也是要考慮的一個因素。

*************************************************************************************

插入排序：·直接插入排序： ·逐個向前插入到合適位置。

·哨兵(監視哨)有兩個作用： ·作為臨變數存放R[i]

·是在查找循環中用來監視下標變數j是否越界。

·直接插入排序是就地的穩定排序。時間復雜度為O(n^2)，比較次數為(n+2)(n-1)/2;移動次數為(n+4)(n-1)/2;

·希爾排序： ·等間隔的數據比較並按要求順序排列，最後間隔為1。

·希爾排序是就地的不穩定排序。時間復雜度為O(n^1.25)，比較次數為(n^1.25);移動次數為(1.6n^1.25);

交換排序：·冒泡排序：·自下向上確定最輕的一個。·自上向下確定最重的一個。·自下向上確定最輕的一個，後自上向下確定最重的一個。

·冒泡排序是就地的穩定排序。時間復雜度為O(n^2)，比較次數為n(n-1)/2;移動次數為3n(n-1)/2;

·快速排序：·以第一個元素為參考基準，設定、動兩個指針，發生交換後指針交換位置，直到指針重合。重復直到排序完成。

·快速排序是非就地的不穩定排序。時間復雜度為O(nlog2n)，比較次數為n(n-1)/2;

選擇排序：·直接選擇排序： ·選擇最小的放在比較區前。

·直接選擇排序就地的不穩定排序。時間復雜度為O(n^2)。比較次數為n(n-1)/2;

·堆排序 ·建堆：按層次將數據填入完全二叉樹，從int(n/2)處向前逐個調整位置。

·然後將樹根與最後一個葉子交換值並斷開與樹的連接並重建堆，直到全斷開。

·堆排序是就地不穩定的排序，時間復雜度為O(nlog2n)，不適宜於記錄數較少的文件。。

歸並排序： ·先兩個一組排序，形成(n+1)/2組，再將兩組並一組，直到剩下一組為止。

·歸並排序是非就地穩定排序，時間復雜度是O(nlog2n),

分配排序：·箱排序： ·按關鍵字的取值范圍確定箱子數，按關鍵字投入箱子，鏈接所有非空箱。

·箱排序的平均時間復雜度是線性的O(n).

·基數排序：·從低位到高位依次對關鍵字進行箱排序。

·基數排序是非就穩定的排序，時間復雜度是O(d*n+d*rd)。

各種排序方法的比較和選擇： ·.待排序的記錄數目n;n較大的要用時間復雜度為O(nlog2n)的排序方法;

·記錄的大小(規模);記錄大最好用鏈表作為存儲結構，而快速排序和堆排序在鏈表上難於實現;

·關鍵字的結構及其初始狀態;

·對穩定性的要求;

·語言工具的條件;

·存儲結構;

·時間和輔助空間復雜度。

lishixin/Article/program/sjjg/201311/23750