排序算法特點(diǎn)

排序算法特點(diǎn)，算法復(fù)雜度和比較直接插入排序如果目標(biāo)是把n個(gè)元素的序列升序排列，那么采用直接插入排序存在最好情況和最壞情況。最好情況就是，序列已經(jīng)是升序排列了，在這種情況下，需要進(jìn)行的比較操作需(n1)次即可。最壞情況就是，序列是降序排列，那么此時(shí)需要進(jìn)行的比較共有n(n1)/2次。直接插入排序的賦值操作是比較操作的次數(shù)減去(n1)次。平均來(lái)說(shuō)直接插入排序算法復(fù)雜度為O(n2)。因而，直接插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用。但是，如果需要排序的數(shù)據(jù)量很小，例如，量級(jí)小于千，那么直接插入排序還是一個(gè)不錯(cuò)的選擇。插入排序在工業(yè)級(jí)庫(kù)中也有著廣泛的應(yīng)用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補(bǔ)充，用于少量元素的排序(通常為8個(gè)或以下)。希爾排序希爾排序是基于插入排序的一種算法，在此算法基礎(chǔ)之上增加了一個(gè)新的特性，提高了效率。希爾排序的時(shí)間復(fù)雜度為O(N*(logN)2)，沒(méi)有快速排序算法快O(N*(logN))，因此中等大小規(guī)模表現(xiàn)良好，對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。但是比O(N2)復(fù)雜度的算法快得多。并且希爾排序非常容易實(shí)現(xiàn)，算法代碼短而簡(jiǎn)單。此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時(shí)快速排序在最壞的情況下執(zhí)行的效率會(huì)非常差。專(zhuān)家們提倡，幾乎任何排序工作在開(kāi)始時(shí)都可以用希爾排序，若在實(shí)際使用中證明它不夠快，再改成快速排序這樣更高級(jí)的排序算法.希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序，當(dāng)剛開(kāi)始元素很無(wú)序的時(shí)候，步長(zhǎng)最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長(zhǎng)很小，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ?，希爾排序的時(shí)間復(fù)雜度會(huì)比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以shell排序是不穩(wěn)定的冒泡排序時(shí)間復(fù)雜度為O(n^2)，雖然不及堆排序、快速排序的O(nlogn，底數(shù)為2)，但是有兩個(gè)優(yōu)點(diǎn)：1.''編程復(fù)雜度〃很低，很容易寫(xiě)出代碼；2.具有穩(wěn)定性。其中若記錄序列的初始狀態(tài)為"正序”，則冒泡排序過(guò)程只需進(jìn)行一趟排序，在排序過(guò)程中只需進(jìn)行n-1次比較，且不移動(dòng)記錄;反之，若記錄序列的初始狀態(tài)為"逆序”，則需進(jìn)行n(n-1)/2次比較和記錄移動(dòng)。因此冒泡排序總的時(shí)間復(fù)雜度為O(n*n)?？焖倥判蛟谧詈玫那闆r，每次我們執(zhí)行一次分割，我們會(huì)把一個(gè)數(shù)列分為兩個(gè)幾近相等的片段。這個(gè)意思就是每次遞回調(diào)用處理一半大小的數(shù)列。因此，在到達(dá)大小為一的數(shù)列前，我們只要作logn次巢狀的調(diào)用。這個(gè)意思就是調(diào)用樹(shù)的深度是O(logn)。但是在同一階層的兩個(gè)程序調(diào)用中，不會(huì)處理到原來(lái)數(shù)列的相同部份；因此，程序調(diào)用的每一階層總共全部?jī)H需要O(n)的時(shí)間(每個(gè)調(diào)用有某些共同的額外耗費(fèi)，但是因?yàn)樵诿恳浑A層僅僅只有O(n)個(gè)調(diào)用，這些被歸納在O(n)系數(shù)中)。結(jié)果是這個(gè)算法僅需使用O(nlogn)時(shí)間。另外一個(gè)方法是為T(mén)(n)設(shè)立一個(gè)遞回關(guān)系式，也就是需要排序大小為n的數(shù)列所需要的時(shí)間。在最好的情況下，因?yàn)橐粋€(gè)單獨(dú)的快速排序調(diào)用牽涉了O(n)的工作，加上對(duì)n/2大小之?dāng)?shù)列的兩個(gè)遞回調(diào)用，這個(gè)關(guān)系式可以是：T(n)=O(n)+2T(n/2)解決這種關(guān)系式型態(tài)的標(biāo)準(zhǔn)數(shù)學(xué)歸納法技巧告訴我們T(n)=O(nlogn)。事實(shí)上，并不需要把數(shù)列如此精確地分割；即使如果每個(gè)基準(zhǔn)值將元素分開(kāi)為99%在一邊和1%在另一邊，調(diào)用的深度仍然限制在100logn，所以全部執(zhí)行時(shí)間依然是O(nlogn)然而，在最壞的情況是，兩子數(shù)列擁有大各為1和n-1，且調(diào)用樹(shù)(calltree)變成為一個(gè)n個(gè)巢狀(nested)呼叫的線(xiàn)性連串(chain)。第i次呼叫作了O(n-i)的工作量，-，)=。(靜)且二|遞回關(guān)系式為：T(n)=O(n)+T(1)+T(n-1)=O(n)+T(n-1)這與插入排序和選擇排序有相同的關(guān)系式，以及它被解為T(mén)(n)=O(n2)。討論平均復(fù)雜度情況下，即使如果我們無(wú)法隨機(jī)地選擇基準(zhǔn)數(shù)值，對(duì)于它的輸入之所有可能排列，快速排序仍然只需要O(nlogn)時(shí)間。因?yàn)檫@個(gè)平均是簡(jiǎn)單地將輸入之所有可能排列的時(shí)間加總起來(lái)，除以n這個(gè)因子，相當(dāng)于從輸入之中選擇一個(gè)隨機(jī)的排列。當(dāng)我們這樣作，基準(zhǔn)值本質(zhì)上就是隨機(jī)的，導(dǎo)致這個(gè)算法與亂數(shù)快速排序有一樣的執(zhí)行時(shí)間。更精確地說(shuō)，對(duì)于輸入順序之所有排列情形的平均比較次數(shù)，可以借由解出這個(gè)遞回關(guān)系式可以精確地算出來(lái)。[n—1C(?z)=—1+—(W)+—i—1))=2nInn=1.39?ilog2n.n在這里，n1是分割所使用的比較次數(shù)。因?yàn)榛鶞?zhǔn)值是相當(dāng)均勻地落在排列好的數(shù)列次序之任何地方，總和就是所有可能分割的平均。這個(gè)意思是，平均上快速排序比理想的比較次數(shù)，也就是最好情況下，只大約比較糟39%。這意味著，它比最壞情況較接近最好情況。這個(gè)快速的平均執(zhí)行時(shí)間，是快速排序比其他排序算法有實(shí)際的優(yōu)勢(shì)之另一個(gè)原因。討論空間復(fù)雜度時(shí)被快速排序所使用的空間，依照使用的版本而定。使用原地(in-place)分割的快速排序版本，在任何遞回呼叫前，僅會(huì)使用固定的額外空^。然而，如果需要產(chǎn)生O(logn)巢狀遞回呼叫，它需要在他們每一個(gè)儲(chǔ)存一個(gè)固定數(shù)量的資訊。因?yàn)樽詈玫那闆r最多需要O(logn)次的巢狀遞回呼叫，所以它需要O(logn)的空間。最壞情況下需要O(n)次巢狀遞回呼叫，因此需要O(n)的空間。然而我們?cè)谶@里省略一些小的細(xì)節(jié)。如果我們考慮排序任意很長(zhǎng)的數(shù)列，我們必須要記住我們的變量像是/eft和right，不再被認(rèn)為是占據(jù)固定的空間；也需要O(log。)對(duì)原來(lái)一個(gè)n項(xiàng)的數(shù)列作索引。因?yàn)槲覀冊(cè)诿恳粋€(gè)堆?？蚣苤卸加邢襁@些的變量，實(shí)際上快速排序在最好跟平均的情況下，需要O(log2n)空間的位元數(shù)，以及最壞情況下O(nlogn)的空間。然而，這并不會(huì)太可怕，因?yàn)槿绻粋€(gè)數(shù)列大部份都是不同的元素，那么數(shù)列本身也會(huì)占據(jù)O(nlogn)的空間字節(jié)。非原地版本的快速排序，在它的任何遞回呼叫前需要使用O(n)空間。在最好的情況下，它的空間仍然限制在O(n)，因?yàn)檫f回的每一階中，使用與上一次所使用最多空間的一半，且它的最壞情況是很恐怖的，需要n工(n—j+1)=Q(n2)i=0空間，遠(yuǎn)比數(shù)列本身還多。如果這些數(shù)列元素本身自己不是固定的大小，這個(gè)問(wèn)題會(huì)變得更大；舉例來(lái)說(shuō)，如果數(shù)列元素的大部份都是不同的，每一個(gè)將會(huì)需要大約O(logn)為原來(lái)儲(chǔ)存，導(dǎo)致最好情況是O(nlogn)和最壞情況是O(n2logn)的空間需求。直接選擇排序選擇排序的交換操作介于0和(n-1)次之間。選擇排序的比較操作為n(n-1)/2次之間。選擇排序的賦值操作介于0和3(n-1)次之間。比較次數(shù)O(n^2),比較次數(shù)與關(guān)鍵字的初始狀態(tài)無(wú)關(guān)，總的比較次數(shù)N=(n-1)+(n-2)+...+1=n*(n-1)/2。交換次數(shù)O(n),最好情況是，已經(jīng)有序，交換0次；最壞情況是，逆序，交換n-1次。交換次數(shù)比冒泡排序少多了，由于交換所需CPU時(shí)間比比較所需的CPU時(shí)間多，n值較小時(shí)，選擇排序比冒泡排序快。堆排序堆排序的平均時(shí)間復(fù)雜度為0(nlogn)，空間復(fù)雜度為0(1)。由于它在直接選擇排序的基礎(chǔ)上利用了比較結(jié)果形成。效率提高很大。它完成排序的總比較次數(shù)為O(nlog2n)。它是對(duì)數(shù)據(jù)的有序性不敏感的一種算法。但堆排序?qū)⑿枰鰞蓚€(gè)步驟:一是建堆，二是排序(調(diào)整堆)。所以一般在小規(guī)模的序列中不合適，但對(duì)于較大的序列，將表現(xiàn)出優(yōu)越的性能。歸并排序歸并排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對(duì)兩個(gè)己有序的序列歸并，將有無(wú)比的優(yōu)勢(shì)。其時(shí)間復(fù)雜度無(wú)論是在最好情況下還是在最壞情況下均是O(nlog2n)。對(duì)數(shù)據(jù)的有序性不敏感。若數(shù)據(jù)節(jié)點(diǎn)數(shù)據(jù)量大，那將不適合?；鶖?shù)排序基數(shù)排序的時(shí)間復(fù)雜度是O(k。)，其中n是排序元素個(gè)數(shù)，k是數(shù)字位數(shù)。注意這不是說(shuō)這個(gè)時(shí)間復(fù)雜度一定優(yōu)于O(n-log(n))，因?yàn)閗的大小一般會(huì)受到n的影響。以排序n個(gè)不同整數(shù)來(lái)舉例，假定這些整數(shù)以B為底，這樣每位數(shù)都有B個(gè)不同的數(shù)字，k就一定不小于logB(n)。由于有B個(gè)不同的數(shù)字，所以就需要B個(gè)不同的桶，在每一輪比較的時(shí)候都需要平均n?log2(B)次比較來(lái)把整數(shù)放到合適的桶中去，所以就有：?k大于或等于logB(n)?每一輪(平均)需要n?log2(B)次比較所以，基數(shù)排序的平均時(shí)間T就是：T>logB(n)?n?log2(B)=log2(n)?logB(2)?n?log2(B)=log2(n).n.logB(2).log2(B)=n?log2(n)所以和比較排序相似，基數(shù)排序需要的比較次數(shù)：T>n?log2(n)。故其時(shí)間復(fù)雜度為Q(n?log2(n))=Q(n-logn)。七、不同條件下，排序方法的選擇若n較小(如n<50)，可采用直接插入或直接選擇排序。當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于直接插入，應(yīng)選直接選擇排序?yàn)橐?。若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插入、冒泡或隨機(jī)的快速排序?yàn)橐耍蝗鬾較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的排序算法并不值得提倡，通常可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長(zhǎng)的有序子文件，然后再兩兩歸并之。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。(4)在基于比較的排序方法中，每次比較兩個(gè)關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹(shù)來(lái)描述比較判定過(guò)程。當(dāng)文件的n個(gè)關(guān)鍵字隨機(jī)分布時(shí)，任何借助于”比較”的排序算法，至少需要O(nlgn)的時(shí)間。箱排序和基數(shù)排序只需一步就會(huì)引起m種可能的轉(zhuǎn)移，即把一個(gè)記錄裝入m個(gè)箱子之一，因此在一般情況下，箱排序和基數(shù)排序可能在O(n)時(shí)間內(nèi)完成對(duì)n個(gè)記錄的排序。但是，箱排序和基數(shù)排序只適用于像字符串和整數(shù)這類(lèi)有明顯結(jié)構(gòu)特征的關(guān)鍵字，而當(dāng)關(guān)鍵字的取值范圍屬于某個(gè)無(wú)窮集合(例如實(shí)數(shù)型關(guān)鍵字)時(shí)，無(wú)法使用箱排序和基數(shù)排序，這時(shí)只有借助于”比較”的方法來(lái)排序。若n很大，記錄的關(guān)鍵字位數(shù)較少且可以分解時(shí)，采用基數(shù)排序較好。雖然桶排序?qū)﹃P(guān)鍵字的結(jié)構(gòu)無(wú)要求，但它也只有在關(guān)鍵字是隨機(jī)分布時(shí)才能使平均時(shí)間達(dá)到線(xiàn)性階，否則為平方階。同時(shí)要注意，箱、桶、基數(shù)這三種分配排序均假定了關(guān)鍵字若為數(shù)字時(shí)，則其值均是非負(fù)的，否則將其映射到箱(桶)號(hào)時(shí)，又要增加相應(yīng)的時(shí)間。有的語(yǔ)言(如Fortran，Cobol或Basic等)沒(méi)有提供指針及遞歸，導(dǎo)致實(shí)現(xiàn)歸并、快速(它們用遞歸實(shí)現(xiàn)較簡(jiǎn)單)和基數(shù)(使用了指針)等排序算法變得復(fù)雜。此時(shí)可考慮用其它排序。本章給出的排序算法，輸人數(shù)據(jù)均是存儲(chǔ)在一個(gè)向量中。當(dāng)記錄的規(guī)模較大時(shí)，為避免耗費(fèi)大量的時(shí)間去移動(dòng)記錄，可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。譬如插入排序、歸并排序、基數(shù)排序都易于在鏈表上實(shí)現(xiàn)，使之減少記錄的移動(dòng)次數(shù)。但有的排序方法，如快速排序和堆排序，在鏈表上卻難于實(shí)現(xiàn)，在這種情況下，可以提取關(guān)鍵字建立索引表，然后對(duì)索引表進(jìn)行排序。然而更為簡(jiǎn)單的方法是：引人一個(gè)整型向量t作為輔助表，排序前令t[i]=i(0Vi<n),若排序算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結(jié)束后，向量t就指示了記錄之間的順序關(guān)系：R[t[0]].keyWR[t[1]].keyW.?.WR[t[n-1]].key若要求最終結(jié)果是：R[0]?keyWR[1]?keyW???WR[n-1]?key則可以在排序結(jié)束后，再按輔助表所規(guī)定的次序重排各記錄，完成這種重排的時(shí)間是O(n)。

八、各排序算法時(shí)間復(fù)雜度和空間復(fù)雜度◎排序算法各類(lèi)排序算法時(shí)間復(fù)雜度和空間復(fù)雜度對(duì)比表類(lèi)別捧序方法平均情況時(shí)間復(fù)雜度最好情況最壞情況育更1復(fù)壑匿銃