- 相關(guān)推薦
筆試中各種排序算法的復(fù)雜度
大家應(yīng)該注意的是復(fù)雜度中帶logN的這幾個(gè)算法!
B是真數(shù)(0-9),
R是基數(shù)(個(gè)十百)
ShellO(nlogn)
O(n^1.25)
???
O(ns) 1<s<2 不穩(wěn)定 O(1) s是所選分組 快速 O(nlogn) O(n2) 不穩(wěn)定 O(nlogn) n大時(shí)較好 歸并 O(nlogn) O(nlogn) 穩(wěn)定 O(1) n大時(shí)較好 堆 O(nlogn) O(nlogn) 不穩(wěn)定 O(1) n大時(shí)較好各算法的時(shí)間復(fù)雜度
平均時(shí)間復(fù)雜度
插入排序 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)
快速排序是一個(gè)就地排序,分而治之,大規(guī)模遞歸的算法,
筆試中各種排序算法的復(fù)雜度
,資料共享平臺(tái)
《筆試中各種排序算法的復(fù)雜度》(http://www.msguai.com)。從本質(zhì)上來說,它是歸并排序的就地版本?焖倥判蚩梢杂上旅嫠牟浇M成。(1) 如果不多于1個(gè)數(shù)據(jù),直接返回。
(2) 一般選擇序列最左邊的值作為支點(diǎn)數(shù)據(jù)。
(3) 將序列分成2部分,一部分都大于支點(diǎn)數(shù)據(jù),另外一部分都小于支點(diǎn)數(shù)據(jù)。
(4) 對兩邊利用遞歸排序數(shù)列。
快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法,但是就通常情況而言,沒有比它更快的了?焖倥判蚴沁f歸的,對于內(nèi)存非常有限的機(jī)器來說,它不是一個(gè)好的選擇。
2 歸并排序(MergeSort)
歸并排序先分解要排序的序列,從1分成2,2分成4,依次分解,當(dāng)分解到只有1個(gè)一組的時(shí)候,就可以排序這些分組,然后依次合并回原來的序列中,這樣就可以排序所有數(shù)據(jù)。合并排序比堆排序稍微快一點(diǎn),但是需要比堆排序多一倍的內(nèi)存空間,因?yàn)樗枰粋(gè)額外的數(shù)組。
3 堆排序(HeapSort)
堆排序適合于數(shù)據(jù)量非常大的場合(百萬數(shù)據(jù))。
堆排序不需要大量的遞歸或者多維的暫存數(shù)組。這對于數(shù)據(jù)量非常巨大的序列是合適的。比如超過數(shù)百萬條記錄,因?yàn)榭焖倥判,歸并排序都使用遞歸來設(shè)計(jì)算法,在數(shù)據(jù)量非常大的時(shí)候,可能會(huì)發(fā)生堆棧溢出錯(cuò)誤。
堆排序會(huì)將所有的數(shù)據(jù)建成一個(gè)堆,最大的數(shù)據(jù)在堆頂,然后將堆頂數(shù)據(jù)和序列的最后一個(gè)數(shù)據(jù)交換。接下來再次重建堆,交換數(shù)據(jù),依次下去,就可以排序所有的數(shù)據(jù)。
4 Shell排序(ShellSort)
Shell排序通過將數(shù)據(jù)分成不同的組,先對每一組進(jìn)行排序,然后再對所有的元素進(jìn)行一次插入排序,以減少數(shù)據(jù)交換和移動(dòng)的次數(shù)。平均效率是O(nlogn)。其中分組的合理性會(huì)對算法產(chǎn)生重要的影響,F(xiàn)在多用D.E.Knuth的分組方法。
Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相對比較簡單,它適合于數(shù)據(jù)量在5000以下并且速度并不是特別重要的場合。它對于數(shù)據(jù)量較小的數(shù)列重復(fù)排序是非常好的。
5 插入排序(InsertSort)
插入排序通過把序列中的值插入一個(gè)已經(jīng)排序好的序列中,直到該序列的結(jié)束。插入排序是對冒泡排序的改進(jìn)。它比冒泡排序快2倍。一般不用在數(shù)據(jù)大于1000的場合下使用插入排序,或者重復(fù)排序超過200數(shù)據(jù)項(xiàng)的序列。
6 冒泡排序(BubbleSort)
冒泡排序是最慢的排序算法。在實(shí)際運(yùn)用中它是效率最低的算法。它通過一趟又一趟地比較數(shù)組中的每一個(gè)元素,使較大的數(shù)據(jù)下沉,較小的數(shù)據(jù)上升。它是O(n^2)的算法。
7 交換排序(ExchangeSort)和選擇排序(SelectSort)
這兩種排序方法都是交換方法的排序算法,效率都是 O(n2)。在實(shí)際應(yīng)用中處于和冒泡排序基本相同的地位。它們只是排序算法發(fā)展的初級(jí)階段,在實(shí)際中使用較少。
8 基數(shù)排序(RadixSort)
基數(shù)排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法,但是它只能用于整數(shù)的排序,如果我們要把同樣的辦法運(yùn)用到浮點(diǎn)數(shù)上,我們必須了解浮點(diǎn)數(shù)的存儲(chǔ)格式,并通過特殊的方式將浮點(diǎn)數(shù)映射到整數(shù)上,然后再映射回去,這是非常麻煩的事情,因此,它的使用同樣也不多。而且,最重要的是,這樣算法也需要較多的存儲(chǔ)空間。
相關(guān)筆試題目推薦:
運(yùn)營維護(hù)工程師筆試題 房地產(chǎn)銷售代理人員筆試題 申銀萬國校園招聘筆試題目
【筆試中各種排序算法的復(fù)雜度】相關(guān)文章:
中金筆試經(jīng)歷09-11
生活中各種小常識(shí)07-16
佛教常識(shí)中的各種稱謂10-19
中金CICC筆試題10-24
筆試中的硬件類題09-24
中芯國際南京筆試07-18
中糧集團(tuán)筆試題分享07-08
中軟Java筆試題目10-04
中金暑期實(shí)習(xí)筆試經(jīng)驗(yàn)04-28
南京中稅科技筆試題06-27