按平均時(shí)間將排序分為四類：

• 平方階(O(n2))排序：一般稱為簡(jiǎn)單排序，例如直接插入、直接選擇和冒泡排序；

• 線性對(duì)數(shù)階(O(nlgn))排序：如快速、堆和歸并排序；

• O(n1+￡)階排序：￡ 是介于 0 和 1 之間的常數(shù)，即 0<￡<1，如希爾排序；

• 線性階(O(n))排序：如桶、箱和基數(shù)排序。

各種排序方法比較

簡(jiǎn)單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時(shí)，直接插入和冒泡均最佳。

影響排序效果的因素

因?yàn)椴煌呐判蚍椒ㄟm應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：

①待排序的記錄數(shù)目 n；

②記錄的大小(規(guī)模)；

③關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；

④對(duì)穩(wěn)定性的要求；

⑤語(yǔ)言工具的條件；

⑥存儲(chǔ)結(jié)構(gòu)；

⑦時(shí)間和輔助空間復(fù)雜度等。

不同條件下，排序方法的選擇

(1)若 n 較小(如 n≤50)，可采用直接插入或直接選擇排序。

當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序?yàn)橐恕?/p>

(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐耍?/p>

(3)若 n 較大，則應(yīng)采用時(shí)間復(fù)雜度為 O(nlgn)的排序方法：快速排序、堆排序或歸并排序。

快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短； 堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。

若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的 排序算法并不值得提倡，通?？梢詫⑺椭苯硬迦肱判蚪Y(jié)合在一起使用。先利用直接插入排序求得較長(zhǎng)的有序子文件，然后再兩兩歸并之。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。

(4)在基于比較的排序方法中，每次比較兩個(gè)關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹(shù)來(lái)描述比較判定過(guò)程。

當(dāng)文件的 n 個(gè)關(guān)鍵字隨機(jī)分布時(shí)，任何借助于"比較"的排序算法，至少需要 O(nlgn)的時(shí)間。

箱排序和基數(shù)排序只需一步就會(huì)引起m種可能的轉(zhuǎn)移，即把一個(gè)記錄裝入 m 個(gè)箱子之一，因此在一般情況下，箱排序和基數(shù)排序可能在O(n)時(shí)間內(nèi)完成對(duì)n個(gè)記錄的排序。但是，箱排序和基數(shù)排序只適用于像字符串和整數(shù)這類有明顯結(jié)構(gòu)特征的關(guān)鍵字，而當(dāng)關(guān)鍵字的取值范圍屬于某個(gè)無(wú)窮集合(例如實(shí)數(shù)型關(guān)鍵字)時(shí)，無(wú)法使用箱排序和基數(shù)排序，這時(shí)只有借助于"比較"的方法來(lái)排序。

若 n 很大，記錄的關(guān)鍵字位數(shù)較少且可以分解時(shí)，采用基數(shù)排序較好。雖然桶排序?qū)﹃P(guān)鍵字的結(jié)構(gòu)無(wú)要求，但它也只有在關(guān)鍵字是隨機(jī)分布時(shí)才能使平均時(shí)間達(dá)到線性階，否則為平方階。同時(shí)要注意，箱、桶、基數(shù)這三種分配排序均假定了關(guān)鍵字若為數(shù)字時(shí)，則其值均是非負(fù)的，否則將其映射到箱(桶)號(hào)時(shí)，又要增加相應(yīng)的時(shí)間。

(5)有的語(yǔ)言(如 Fortran，Cobol 或 Basic 等)沒(méi)有提供指針及遞歸，導(dǎo)致實(shí)現(xiàn)歸并、快速(它們用遞歸實(shí)現(xiàn)較簡(jiǎn)單)和基數(shù)(使用了指針)等排序算法變得復(fù)雜。此時(shí)可考慮用其它排序。

(6)本章給出的排序算法，輸人數(shù)據(jù)均是存儲(chǔ)在一個(gè)向量中。當(dāng)記錄的規(guī)模較大時(shí)，為避免耗費(fèi)大量的時(shí)間去移動(dòng)記錄，可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。譬如插入排序、歸并排序、基數(shù)排序都易于在鏈表上實(shí)現(xiàn)，使之減少記錄的移動(dòng)次數(shù)。但有的排序方法，如快速排序和堆排序，在鏈表上卻難于實(shí)現(xiàn)，在這種情況下，可以提取關(guān)鍵字建立索引表，然后對(duì)索引表進(jìn)行排序。然而更為簡(jiǎn)單的方法是：引人一個(gè)整型向量 t 作為輔助表，排序前令 t[i]=i(0≤i<n)，若排序算法中要求交換 R[i]和 R[j]，則只需交換 t[i]和 t[j]即可；排序結(jié)束后，向量t就指示了記錄之間的順序關(guān)系：

R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key

若要求最終結(jié)果是：

R[0].key≤R[1].key≤…≤R[n-1].key

則可以在排序結(jié)束后，再按輔助表所規(guī)定的次序重排各記錄，完成這種重排的時(shí)間是 O(n)。