按平均時間將排序分為四類
()平方階(O(n ))排序
一般稱為簡單排序例如直接插入直接選擇和冒泡排序;
()線性對數階(O(nlgn))排序
如快速堆和歸並排序;
()O(n +￡ )階排序
￡是介於和之間的常數即<￡<如希爾排序;
()線性階(O(n))排序
如桶箱和基數排序
各種排序方法比較
簡單排序中直接插入最好快速排序最快當文件為正序時直接插入和冒泡均最佳
影響排序效果的因素
因為不同的排序方法適應不同的應用環境和要求所以選擇合適的排序方法應綜合考慮下列因素
①待排序的記錄數目n;
②記錄的大小(規模);
③關鍵字的結構及其初始狀態;
④對穩定性的要求;
⑤語言工具的條件;
⑥存儲結構;
⑦時間和輔助空間復雜度等
不同條件下排序方法的選擇
()若n較小(如n≤)可采用直接插入或直接選擇排序
當記錄規模較小時直接插入排序較好;否則因為直接選擇移動的記錄數少於直接插人應選直接選擇排序為宜
()若文件初始狀態基本有序(指正序)則應選用直接插人冒泡或隨機的快速排序為宜;
()若n較大則應采用時間復雜度為O(nlgn)的排序方法快速排序堆排序或歸並排序
快速排序是目前基於比較的內部排序中被認為是最好的方法當待排序的關鍵字是隨機分布時快速排序的平均時間最短;
堆排序所需的輔助空間少於快速排序並且不會出現快速排序可能出現的最壞情況這兩種排序都是不穩定的
若要求排序穩定則可選用歸並排序但本章介紹的從單個記錄起進行兩兩歸並的 排序算法並不值得提倡通常可以將它和直接
插入排序結合在一起使用先利用直接插入排序求得較長的有序子文件然後再兩兩歸並之因為直接插入排序是穩定的所以改進
後的歸並排序仍是穩定的
From:http://tw.wingwit.com/Article/program/sjjg/201311/23769.html
