排序算法匯總(圖解加程序代碼)

1、排序算法匯總第1節(jié)排序及其基本概念一、基本概念1什么是排序排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。設(shè)文件由n個(gè)記錄Rl,R2,Rn組成，n個(gè)記錄對(duì)應(yīng)的關(guān)鍵字集合為Kl,K2,，Kn。所謂排序就是將這n個(gè)記錄按關(guān)鍵字大小遞增或遞減重新排列。b5E2RGbCAP2穩(wěn)定性當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí),排序結(jié)果是惟一的,否則排序結(jié)果不唯一。如果文件中關(guān)鍵字相同的記錄經(jīng)過某種排序方法進(jìn)行排序之后,仍能保持它們?cè)谂判蛑暗南鄬?duì)次序,則稱這種排序方法是穩(wěn)定的；否則,稱這種排序方法是不穩(wěn)定的。plEanqFDPw3排序的方式由于文件大小不同使排序過程中涉及的存儲(chǔ)器不同,可將排序分成內(nèi)部排序和外部排序兩類。整

2、個(gè)排序過程都在內(nèi)存進(jìn)行的排序,稱為內(nèi)部排序；反之,若排序過程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換,則稱之為外部排序。DXDiTa9E3d內(nèi)排序適用于記錄個(gè)數(shù)不是很多的小文件,而外排序則適用于記錄個(gè)數(shù)太多,不能一次性放人內(nèi)存的大文件。內(nèi)排序是排序的基礎(chǔ),本講主要介紹各種內(nèi)部排序的方法。按策略劃分內(nèi)部排序方法可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。二、排序算法分析1排序算法的基本操作幾乎所有的排序都有兩個(gè)基本的操作：1）關(guān)鍵字大小的比較。2）改變記錄的位置。具體處理方式依賴于記錄的存儲(chǔ)形式，對(duì)于順序型記錄，一般移動(dòng)記錄本身，而鏈?zhǔn)酱鎯?chǔ)的記錄則通過改變指向記錄的指針實(shí)現(xiàn)重定位。RTCr

3、pUDGiT為了簡(jiǎn)化描述，在下面的講解中，我們只考慮記錄的關(guān)鍵字，則其存儲(chǔ)結(jié)構(gòu)也簡(jiǎn)化為數(shù)組或鏈表。并約定排序結(jié)果為遞增。5PCzVD7HxA2排序算法性能評(píng)價(jià)排序的算法很多，不同的算法有不同的優(yōu)缺點(diǎn)，沒有哪種算法在任何情況下都是最好的。評(píng)價(jià)一種排序算法好壞的標(biāo)準(zhǔn)主要有兩條：jLBHrnAILg1）執(zhí)行時(shí)間和所需的輔助空間，即時(shí)間復(fù)雜度和空間復(fù)雜度；2）算法本身的復(fù)雜程度，比如算法是否易讀、是否易于實(shí)現(xiàn)。第2節(jié)插入排序插入排序的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的記錄集中，使記錄依然有序，直到所有待排序記錄全部插入完成。xHAQX74J0X一、直接插入排序1直

4、接插入排序的思想否則，將Aj后移一個(gè)位置：Aj-Aj+1；繼續(xù)執(zhí)行否則，將Aj后移一個(gè)位置：Aj-Aj+1；繼續(xù)執(zhí)行假設(shè)待排序數(shù)據(jù)存放在數(shù)組Al.n中，則Al可看作是一個(gè)有序序列，讓i從2開始，依次將Ai插入到有序序列Al.i-1中，An插入完畢則整個(gè)過程結(jié)束，Al.n成為有序序列。LDAYtRyKfE2排序過程示例用【】表示有序序列）待排序數(shù)據(jù)：【25】548542119727315。vari,j:integer。beginfori:=2tondobegina0:=ai。j:=i-1。whileaja0do決定運(yùn)算次數(shù)和移動(dòng)次數(shù)beginaj+1:=aj。j:=j-1。end。aj+1:=a

5、0。end。end。5算法分析1）穩(wěn)定性：穩(wěn)定n時(shí)，本組數(shù)s:=round(s/2。減fork:=1tosdo別排序begini:=k+s。whilei=ndo據(jù)排序結(jié)束begina0:=ai。j:=i-s。約定步長(zhǎng)為Swhile（aja0and（j=kdobeginaj+s:=aj。j:=j-s。end。aj+s:=a0。i:=i+s。end。end。untils=1。end。5算法分析1）穩(wěn)定性：不穩(wěn)定2）時(shí)間復(fù)雜度：Shell排序的執(zhí)行時(shí)間依賴于增量序列。如實(shí)例所示，選擇增量系列為5-2-1的比較次數(shù)增量系列為5-3-2-1的比較次數(shù)。SixE2yXPq5在直接插入排序中，數(shù)據(jù)越趨向于有

6、序，比較和移動(dòng)次數(shù)越少，Shell排序的目的則是增加這種有序趨勢(shì)。雖然看起來重復(fù)次數(shù)較多，需要多次選擇增量，但開始時(shí)，增量較大，分組較多，但由于各組的數(shù)據(jù)個(gè)數(shù)少，則比較次數(shù)累計(jì)值也小，當(dāng)增量趨向1時(shí)，組內(nèi)數(shù)據(jù)增多，而所有數(shù)據(jù)已經(jīng)基本接近有序狀態(tài)，因此，Shell的時(shí)間性能優(yōu)于直接插入排序。6ewMyirQFL3)空間復(fù)雜度：僅需一個(gè)單元AO第3節(jié)交換排序交換排序的基本思想是：兩兩比較待排序的數(shù)據(jù)，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)的次序相反則進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)為止。kavU42VRUs一、冒泡排序1冒泡排序的思想最多進(jìn)行n-1趟排序，每趟排序時(shí)，從底部向上掃描，一旦發(fā)現(xiàn)兩個(gè)相鄰的元素不符合規(guī)則，則交換。我

7、們發(fā)現(xiàn)，第一趟排序后，最小值在Al,第二趟排序后，較小值在A2，第n-1趟排序完成后，所有元素完全按順序排列。y6v3ALoS892排序過程示例待排序數(shù)據(jù)：5333195336382201939。vartemp,i,j:integer。change:boolean。fori:=1ton-1dobeginchange:=false。forj:=n-1downtoidoifajaj+1thenbeginchange:=true。temp:=aj。aj:=aj+1aj+1:=temp。end。ifnot（changethenexit。end。end。4算法分析1）穩(wěn)定性：穩(wěn)定2）時(shí)間復(fù)雜度：原始數(shù)據(jù)

8、正序，需一趟排序，比較次數(shù)n-l=O（n原始數(shù)據(jù)反序，需n-1趟排序，比較次數(shù)據(jù)位置的改變b6vSTnP一般情況下，雖然不一定需要n-1趟排序，但需要3次移動(dòng)操作，因此，總時(shí)間復(fù)雜度高于直接插丿X，交換Ai與Aj，j-1。保證了XWAj.high繼續(xù)執(zhí)行、，直到i=jo這時(shí)，X恰好在Ai位置上。對(duì)序列Alow.i-1及Ai+1.high按照上述規(guī)律繼續(xù)劃分，直到序列為空。仔細(xì)分析算法，我們發(fā)現(xiàn)，在排序中，我們總是用基準(zhǔn)X與另一數(shù)據(jù)交換，因此，一趟排序結(jié)束后，X就能確切定位其最終位置。sQsAEJkW5T3排序過程示例待排序數(shù)據(jù)：6767145229990548771X=67ij掃描jij交換5

9、467145229990678771掃描iij交換5467145229967908771j=i，結(jié)束ij第一趟排序后：5467145229967908771第二趟排序后：9291452546767718790第三趟排序后：9291452546767718790第四趟排序后：9142952546767718790第五趟排序后：91429525467677187904程序代碼procedurequicksort(low,high:integer。vartemp,x,i,j:integer。beginiflowhighthenbeginx:=alow。i:=low。j:=high。whileijdo

10、beginwhile(jiand(aj二xdoj:二jT。j左移temp:=ai。ai:=aj。aj:=temp。i:=i-1。while（jiand（ai=xdoi:=i+1。i右移temp:=ai。ai:=aj。aj:=temp。j:=j-1。end。quicksort（low,i-1。quicksort（i+1,high。end。end。5算法分析1）穩(wěn)定性：不穩(wěn)定2）時(shí)間復(fù)雜度：每趟排序所需的比較次數(shù)為待排序區(qū)間的長(zhǎng)度-1，排序趟數(shù)越多，占用時(shí)間越多。最壞情況：每次劃分選取的基準(zhǔn)恰好都是當(dāng)前序列中的最小（或最大值，劃分的結(jié)果Alow.iT為空區(qū)間或Ai+l.high是空區(qū)間，且非空區(qū)間

11、長(zhǎng)度達(dá)到最大值。GMsIasNXkA這種情況下，必須進(jìn)行n-1趟快速排序，第i次趟去見長(zhǎng)度為n-i+1,總的比較次數(shù)達(dá)到最大值：n(n-l/2=0(n2TIrRGchYzg最好情況：每次劃分所取的基準(zhǔn)都是當(dāng)前序列中的“中值”，劃分后的兩個(gè)新區(qū)間長(zhǎng)度大致相等。共需lgn趟快速排序，總的關(guān)鍵字比較次數(shù)：O(nlgn7EqZcWLZNX基準(zhǔn)的選擇決定了算法性能。經(jīng)常采用選取low和high之間一個(gè)隨機(jī)位置作為基準(zhǔn)的方式改善性能。vartemp,k,i,j:integer。beginfori:=1ton-1dobegink:=i。forj:=i+1tondoifajakthenk:=j。ifkithe

12、nbegina0:=ai。ai:=ak。ak:=a0end。end。end。3算法分析。堆的調(diào)整varj:integer。beginif2*i=sthen如果該結(jié)點(diǎn)為葉子，則不再繼續(xù)調(diào)整begina0:=ai。j:=i。ifa2*ia0thenbegina0:=a2*i。j:=2*i。end。2MiJTy0dTTif(2*i+1=sand(a2*i+1a0thenbegina0:=a2*i+1。j:=2*i+1。end。獲取最大值ifjithenbegineditheap(j,s。調(diào)整左右孩子editheap(j,s。調(diào)整左右孩子end。end。end。procedurebuildheap。堆

13、的建立vari,j:integer。beginfori:=ndiv2downto1do從后往前，依次調(diào)整begina0:=ai。j:=i。ifa2*ia0thenbegina0:=a2*i。j:=2*iend。gIiSpiue7Aif(2*i+1and(a2*i+1a0thenbegina0:=a2*i+1。j:=2*i+1。end。ifjithenbeginaj:=ai。ai:=a0。editheap(j,n。end。end。end。procedureheapsort(n:integer。堆排序vark,i,j:integer。beginbuildheap。fori:=ndownto2dob

14、egina0:=ai。ai:=a1。a1:=a0。editheap（1,i-1。end。end。5算法分析1）穩(wěn)定性：不穩(wěn)定。假定數(shù)據(jù)序列為1，1，已是大堆，經(jīng)過排序后，結(jié)果為1，1。2）時(shí)間復(fù)雜度：堆排序的時(shí)間，主要由建立初始堆和反復(fù)調(diào)整堆這兩部分的時(shí)間開銷構(gòu)成，它們均是通過調(diào)用editheap函數(shù)實(shí)現(xiàn)的。uEhOUlYfmh堆排序的最壞時(shí)間復(fù)雜度為O（nlgn。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。IAg9qLsgBX3）空間復(fù)雜度：0（1第5節(jié)歸并排序歸并排序是利用歸并技術(shù)來進(jìn)行排序。歸并是指將若干個(gè)已排序的子文件合并成一個(gè)

15、有序的文件。一、兩路歸并算法1、算法基本思路設(shè)有兩個(gè)有序ovarp1,p2,p3,j:integerobeginifmnthenh:=nop1:=lop2:=m+1op3:=lowhile(p1and(p2dobeginifap1mthenp3:=p3+1。p3:=p3+1。forj:=p2tohdobegincp3:=aj。end。BkeGuInkxIifp2hthenforj:=p1tomdobegincp3:=aj。end。PgdO0sRlMoforj:=ltohdoaj:=cj。end。end。二、歸并排序歸并排序有兩種實(shí)現(xiàn)方法：自底向上和自頂向下。1自底向上的方法1）自底向上的基本思

16、想自底向上的基本思想是：第1趟歸并排序時(shí)，將數(shù)列Al.n看作是n個(gè)長(zhǎng)度為1的有序序列，將這些序列兩兩歸并，若n為偶數(shù)，則得到n/2個(gè)長(zhǎng)度為2的有序序列；若n為奇數(shù)，則最后一個(gè)子序列不參與歸并。第2趟歸并則是將第1趟歸并所得到的有序序列兩兩歸并。如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序文件為止。3cdXwckml5上述的每次歸并操作，均是將兩個(gè)有序序列合并成一個(gè)有序序列，故稱其為“二路歸并排序”。類似地有k(k2路歸并排序。h8c52W0ngM2)程序代碼proceduremergesort。vari,s,k:integer。begins:=1。whilesndobegini:=1。repeat

17、merge(s*(i-1+1,s*i,s*(i+1。i:=i+2。untilin。s:=s*2。end。end。2自頂向下的方法采用分治法進(jìn)行自頂向下的算法設(shè)計(jì)，形式更為簡(jiǎn)潔1)分治法的三個(gè)步驟設(shè)歸并排序的當(dāng)前區(qū)間是Al.h，分治法的三個(gè)步驟是：分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn)m=（l+h/2求解：遞歸地對(duì)兩個(gè)子區(qū)間Al.m和Am+l.h進(jìn)行歸并排序；組合：將已排序的兩個(gè)子區(qū)間Al.m和Am+l.h歸并為一個(gè)有序的區(qū)間Al.h。遞歸的終結(jié)條件：子區(qū)間長(zhǎng)度為1一個(gè)數(shù)據(jù)組成的區(qū)間必然有序）。2）程序代碼proceduremergesort（l,h:integer。varm:integer。beginifhlthenbeginm:=（h+ldiv2。mergesort（l,m。mergesort（m+1,h。merge（l,m,