)在基於比較的排序方法中每次比較兩個關鍵字的大小之後僅僅出現兩種可能的轉移因此可以用一棵二叉樹來描述比較判定過
程
當文件的n個關鍵字隨機分布時任何借助於比較的排序算法至少需要O(nlgn)的時間
箱排序和基數排序只需一步就會引起m種可能的轉移即把一個記錄裝入m個箱子之一因此在一般情況下箱排序和基數排序可
能在O(n)時間內完成對n個記錄的排序但是箱排序和基數排序只適用於像字符串和整數這類有明顯結構特征的關鍵字而當關鍵
字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時無法使用箱排序和基數排序這時只有借助於比較的方法來排序
若n很大記錄的關鍵字位數較少且可以分解時采用基數排序較好雖然桶排序對關鍵字的結構無要求但它也只有在關鍵字是
隨機分布時才能使平均時間達到線性階否則為平方階同時要注意箱桶基數這三種分配排序均假定了關鍵字若為數字時則
其值均是非負的否則將其映射到箱(桶)號時又要增加相應的時間
()有的語言(如FortranCobol或Basic等)沒有提供指針及遞歸導致實現歸並快速(它們用遞歸實現較簡單)和基數(使用了指
針)等排序算法變得復雜此時可考慮用其它排序
()本章給出的排序算法輸人數據均是存儲在一個向量中當記錄的規模較大時為避免耗費大量的時間去移動記錄可以用鏈表
作為存儲結構譬如插入排序歸並排序基數排序都易於在鏈表上實現使之減少記錄的移動次數但有的排序方法如快速排序
和堆排序在鏈表上卻難於實現在這種情況下可以提取關鍵字建立索引表然後對索引表進行排序然而更為簡單的方法是引
人一個整型向量t作為輔助表排序前令t[i]=i(≤i
結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。tw.WInGwiT.COM
From:http://tw.wingwit.com/Article/program/sjjg/201311/23767.html
