1、典型比較排序法時間復雜度對比2008-09-1213:56平均情況最好情況最壞情況歸并排序O(nlogn)O(nlogn)O(nlogn)快速排序O(nlogn)O(nlogn)O(n2)希爾排序O(nl.5)O(n)O(n1.5)插入排序O(n2)O(n)O(n2)選擇排序O(n2)O(n2)O(n2)堆排序：時間復雜度O(nlogn)選擇排序：時間復雜度O(n2)冒泡排序：時間復雜度O(n2)歸并排序占用附加存儲較多，需要另外一個與原待排序對象數組同樣大小的輔助數組。這是這個算法的缺點。基數排序：時間復雜度是O(d(n+radix)，但d一般不能取常數，d=logn,所以時間復雜度為O(n

2、logn),當k=n時，為O(n)排序方法比較次數移動次數穩定性附加存儲最好最差最好最差最好最差直接插入排序nn20n21折半插入排序nlog2n0n21起泡排序nn20n21快速排序nlog2nn2nlog2nn2Xlg2nn2簡單選擇排序n20nX1錦標賽排序nlog2nnlog2nn堆排序nlog2nnlog2nX1歸并排序nlog2nnlog2nn線性時間排序的有：計數、基數、桶排序。在前面幾節中討論了內部排序和外部排序的方法。對于內部排序主要介紹了五大類排序方法：插入排序(直接插入排序、折半插入排序和希爾排序)、交換排序(冒泡排序和快速排序)、選擇排序(簡單選擇排序和堆排序)、歸并排

3、序和基數排序。詳細討論了各種排序方法的基本原理，并從時間復雜性、空間復雜性以及排序的穩定性三方面討論了各種排序方法的時效性，介紹了各排序方法的實現算法及其存在的優缺點。如果待排序的數據量很小，最好選擇編程簡單的排序算法，因為在這種情況下采用編程復雜、效率較高的排序方法所能節約的計算機時間是很有限的。反之，如果待處理的數據量很大，特別是當排序過程作為應用程序的一部分需要經常執行時，就應該認真分析和比較各種排序方法，從中選出運行效率最高的方法。下面具體比較一下各種排序方法，以便實現不同的排序處理。插入排序的原理：向有序序列中依次插入無序序列中待排序的記錄，直到無序序列為空，對應的有序序列即為排序的

4、結果，其主旨是“插入”。交換排序的原理：先比較大小，如果逆序就進行交換，直到有序。其主旨是“若逆序就交換”。選擇排序的原理：先找關鍵字最小的記錄，再放到已排好序的序列后面，依次選擇，直到全部有序，其主旨是“選擇”。歸并排序的原理：依次對兩個有序子序列進行“合并”，直到合并為一個有序序列為止，其主旨是“合并”。基數排序的原理：按待排序記錄的關鍵字的組成成分進行排序的一種方法，即依次比較各個記錄關鍵字相應“位”的值，進行排序，直到比較完所有的“位”，即得到一個有序的序列。各種排序方法的工作原理不同，對應的性能也有很大的差別，下面通過一個表格可以看到各排序方法具體的時間性能、空間性能等方面的區別。依

5、據這些因素，可得出如下幾點結論：若n較小(如n值小于50)，對排序穩定性不作要求時，宜采用選擇排序方法，若關鍵字的值不接近逆序，亦可采用直接插入排序法。但如果規模相同，且記錄本身所包含的信息域比較多的情況下應首選簡單選擇排序方法。因為直接插入排序方法中記錄位置的移動操作次數比直接選擇排序多，所以選用直接選擇排序為宜。如果序列的初始狀態已經是一個按關鍵字基本有序的序列，則選擇直接插入排序方法和冒泡排序方法比較合適，因為“基本”有序的序列在排序時進行記錄位置的移動次數比較少。如果n較大，則應采用時間復雜度為O(nlog2n)的排序方法，即快速排序、堆排序或歸并排序方法。快速排序是目前公認的內部排序

6、的最好方法，當待排序的關鍵字是隨機分布時，快速排序所需的平均時間最少；堆排序所需的時間與快速排序相同，但輔助空間少于快速排序，并且不會出現最壞情況下時間復雜性達到O(n2)的狀況。這兩種排序方法都是不穩定的，若要求排序穩定則可選用歸并排序。通常可以將它和直接插入排序結合在一起用。先利用直接插入排序求得兩個子文件，然后，再進行兩兩歸并。排序是軟件設計中最常用的運算之一。排序分為內部排序和外部排序，涉及多種排序的方法。內部排序是將待排序的記錄全部放在內存的排序。本章所討論的各種內部排序的方法大致可分為：插入排序、交換排序、選擇排序、歸并排序和基數排序。插入排序算法的基本思想是：將待序列表看做是左、

7、右兩部分，其中左邊為有序序列，右邊為無序序列，整個排序過程就是將右邊無序序列中的記錄逐個插入到左邊的有序序列中。直接插入排序是這類排序算法中最基本的一種，然而，該排序法時間性能取決于待排序記錄的初始特性。折半插入排序是通過折半查找的方法在有序表中查找記錄插入位置的排序方法。希爾排序算法是一種改進的插入排序，其基本思想是：將待排記錄序列劃分為若干組，在每組內先進行直接插入排序，以使組內序列基本有序，然后再對整個序列進行直接插入排序。其時間性能不取決于待排序記錄的初始特性。交換排序的基本思想是：兩兩比較待排序列的記錄關鍵字，發現逆序即交換。基于這種思想的排序有冒泡排序和快速排序兩種。冒泡排序的基本

8、思想是：從一端開始，逐個比較相鄰的兩個記錄，發現逆序即交換。然而，其時間性能取決于待排序記錄的初始特性。快速排序是一種改進的交換排序，其基本思想是：以選定的記錄為中間記錄，將待排序記錄劃分為左、右兩部分，其中左邊所確記錄的關鍵字不大于右邊所有記錄的關鍵字，然后再對左右兩部分分別進行快速排序。選擇排序的基本思想是：在每一趟排序中，在待排序子表中選出關鍵字最小或最大的記錄放在其最終位置上。直接選擇排序和堆排序是基于這一思想的兩個排序算法。直接選擇排序算法采用的方法較直觀：通過對待排序子表中完整地比較一遍以確定最大（小）記錄，并將該記錄放在子表的最前（后）面。堆排序就是利用堆來進行的一種排序，其中堆

9、是一個滿足特定條件的序列，該條件用完全二叉樹模型表示為每個結點不大于（小于）其左、右孩子的值。利用堆排序可使選擇下一個最大（小）數的時間加快，因而提高算法的時間復雜度，達到O（nlog2n）。歸并排序是一種基于歸并的排序，其基本操作是指將兩個或兩個以上的有序表合并成一個新的有序表。首先將n個待排序記錄看成n個長度為1的有序序列，第一趟歸并后變成n/2個長度為2或1的有序序列；再進行第二趟歸并，如此反復，最終得到一個長度為n的有序序列。歸并排序的時間復雜度為O（nlog2n），最初待排序記錄的排列順序對運算時間影響不大，不足之處就是需要占用較大的輔助空間。基數排序是利用多次的分配和收集過程進行排

10、序。關鍵字的長度為d,其每位的基數為r。首先按關鍵字最低位值的大小依次將記錄分配到r個隊列中，然后依次收集；隨后按關鍵字次最低位值的大小依次對記錄進行分配并收集；如此反復，直到完成按關鍵字最高位的值對記錄進行分配和收集。基數排序需要從關鍵字的最低位到最高位進行d趟分配和收集，時間復雜度為，其缺點是多占用額外的內存空間存放隊列指針。外部排序是對存放在外存的大型文件的排序，外部排序基于對有序歸并段的歸并，而其初始歸并段的產生基于內部排序。排序方法時間復雜度空間復雜度穩定性復雜性平均情況最壞情況最好情況直接插入排序O(n2)O(n2)O(n)O(1)穩定簡單折半插入排序O(n2)O(n2)O(n)O(1)穩定一般希爾排序0沖）O(1)不穩定較復雜簡單選擇排序O(n2)O(n2)O(n2)O(1)不穩定簡單堆排序O(nlo次n)O(nlog