筆試中各種排序算法的復雜度

 　　大家應該注意的是復雜度中帶logN的這幾個算法!

排序法 平均時間 最差情形 穩(wěn)定度 額外空間 備注 冒泡 O(n²) O(n²) 穩(wěn)定 O(1) n小時較好 交換 O(n²) O(n²) 不穩(wěn)定 O(1) n小時較好 選擇 O(n²) O(n²) 不穩(wěn)定 O(1) n小時較好 插入 O(n²) O(n²) 穩(wěn)定 O(1) 大部分已排序時較好 基數(shù) O(log_RB) O(log_RB) 穩(wěn)定 O(n)

B是真數(shù)(0-9)，

R是基數(shù)(個十百)

Shell

O(nlogn)

O(n^1.25)

???

O(n^s) 1<s<2 不穩(wěn)定 O(1) s是所選分組 快速 O(nlogn) O(n²) 不穩(wěn)定 O(nlogn) n大時較好 歸并 O(nlogn) O(nlogn) 穩(wěn)定 O(1) n大時較好 堆 O(nlogn) O(nlogn) 不穩(wěn)定 O(1) n大時較好

　　各算法的時間復雜度

　　平均時間復雜度

　　插入排序 O(n^2)

　　冒泡排序 O(n^2)

　　選擇排序 O(n^2)

　　快速排序 O(n log n)

　　堆排序 O(n log n)

　　歸并排序 O(n log n)

　　基數(shù)排序 O(n)

　　希爾排序 O(n^1.25)

　　1 快速排序(QuickSort)

　　快速排序是一個就地排序，分而治之，大規(guī)模遞歸的算法，

筆試中各種排序算法的復雜度

，

資料共享平臺

《筆試中各種排序算法的復雜度》(http://www.stanzs.com)。從本質上來說，它是歸并排序的就地版本。快速排序可以由下面四步組成。

　　(1) 如果不多于1個數(shù)據(jù)，直接返回。

　　(2) 一般選擇序列最左邊的值作為支點數(shù)據(jù)。

　　(3) 將序列分成2部分，一部分都大于支點數(shù)據(jù)，另外一部分都小于支點數(shù)據(jù)。

　　(4) 對兩邊利用遞歸排序數(shù)列。

　　快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常情況而言，沒有比它更快的了。快速排序是遞歸的，對于內存非常有限的機器來說，它不是一個好的選擇。

　　2 歸并排序(MergeSort)

　　歸并排序先分解要排序的序列，從1分成2，2分成4，依次分解，當分解到只有1個一組的時候，就可以排序這些分組，然后依次合并回原來的序列中，這樣就可以排序所有數(shù)據(jù)。合并排序比堆排序稍微快一點，但是需要比堆排序多一倍的內存空間，因為它需要一個額外的數(shù)組。

　　3 堆排序(HeapSort)

　　堆排序適合于數(shù)據(jù)量非常大的場合(百萬數(shù)據(jù))。

　　堆排序不需要大量的遞歸或者多維的暫存數(shù)組。這對于數(shù)據(jù)量非常巨大的序列是合適的。比如超過數(shù)百萬條記錄，因為快速排序，歸并排序都使用遞歸來設計算法，在數(shù)據(jù)量非常大的時候，可能會發(fā)生堆棧溢出錯誤。

　　堆排序會將所有的數(shù)據(jù)建成一個堆，最大的數(shù)據(jù)在堆頂，然后將堆頂數(shù)據(jù)和序列的最后一個數(shù)據(jù)交換。接下來再次重建堆，交換數(shù)據(jù)，依次下去，就可以排序所有的數(shù)據(jù)。

　　4 Shell排序(ShellSort)

　　Shell排序通過將數(shù)據(jù)分成不同的組，先對每一組進行排序，然后再對所有的元素進行一次插入排序，以減少數(shù)據(jù)交換和移動的次數(shù)。平均效率是O(nlogn)。其中分組的合理性會對算法產生重要的影響。現(xiàn)在多用D.E.Knuth的分組方法。

　　Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對比較簡單，它適合于數(shù)據(jù)量在5000以下并且速度并不是特別重要的場合。它對于數(shù)據(jù)量較小的數(shù)列重復排序是非常好的。

　　5 插入排序(InsertSort)

　　插入排序通過把序列中的值插入一個已經(jīng)排序好的序列中，直到該序列的結束。插入排序是對冒泡排序的改進。它比冒泡排序快2倍。一般不用在數(shù)據(jù)大于1000的場合下使用插入排序，或者重復排序超過200數(shù)據(jù)項的序列。

　　6 冒泡排序(BubbleSort)

　　冒泡排序是最慢的排序算法。在實際運用中它是效率最低的算法。它通過一趟又一趟地比較數(shù)組中的每一個元素，使較大的數(shù)據(jù)下沉，較小的數(shù)據(jù)上升。它是O(n^2)的算法。

　　7 交換排序(ExchangeSort)和選擇排序(SelectSort)

　　這兩種排序方法都是交換方法的排序算法，效率都是 O(n2)。在實際應用中處于和冒泡排序基本相同的地位。它們只是排序算法發(fā)展的初級階段，在實際中使用較少。

　　8 基數(shù)排序(RadixSort)

　　基數(shù)排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法，但是它只能用于整數(shù)的排序，如果我們要把同樣的辦法運用到浮點數(shù)上，我們必須了解浮點數(shù)的存儲格式，并通過特殊的方式將浮點數(shù)映射到整數(shù)上，然后再映射回去，這是非常麻煩的事情，因此，它的使用同樣也不多。而且，最重要的是，這樣算法也需要較多的存儲空間。

相關筆試題目推薦：

運營維護工程師筆試題    房地產銷售代理人員筆試題   申銀萬國校園招聘筆試題目

【筆試中各種排序算法的復雜度】相關文章：

中金筆試經(jīng)歷09-11

生活中各種小常識07-16

佛教常識中的各種稱謂10-19

中金CICC筆試題10-24

筆試中的硬件類題09-24

中芯國際南京筆試07-18

中糧集團筆試題分享07-08

中軟Java筆試題目10-04

中金暑期實習筆試經(jīng)驗04-28

南京中稅科技筆試題06-27