第八章排序
文件有一組記錄組成
排序是將文件按關鍵字的遞增(減)順序排列;
排序文件中有相同的關鍵字時
在排序過程中
排序算法的基本操作
評價排序方法的標准
若關鍵字類型沒有比較運算符
實現過程
void insertsort(seqlist R)
{
int i
for(i=
if(R[i]
R[
do{R[j+
while(R[ R[j+1]=R[0]; } } 算法中引入監視哨R[0]的作用是：1)保存R[i]的副本;2)簡化邊界條件，防止循環下標越界。Tw.wiNgWIt.Com 關鍵字比較次數最大為(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)的排序方法; ·記錄的大小(規模);記錄大最好用鏈表作為存儲結構，而快速排序和堆排序在鏈表上難於實現; ·關鍵字的結構及其初始狀態; ·對穩定性的要求; ·語言工具的條件; ·存儲結構; ·時間和輔助空間復雜度。
From:http://tw.wingwit.com/Article/program/sjjg/201311/23750.html