數(shù)據(jù)結(jié)構(gòu)課件：第10章 排序1插入排序和交換排序

1、第10章 內(nèi)部排序選擇排序 (直接排序、堆排序)概述插入排序 (直接排序、折半排序、希爾排序)交換排序 (冒泡排序、快速排序)歸并排序基數(shù)排序概述10.1 概述排序：將數(shù)據(jù)元素的一個(gè)任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。 例：將關(guān)鍵字序列：52, 49, 80, 36, 14, 58, 61, 23 調(diào)整為：14, 23, 36, 49, 52, 58, 61, 80 若按主關(guān)鍵字排序則結(jié)果惟一若按次關(guān)鍵字排序則結(jié)果可以不惟一(因有相同關(guān)鍵字) 概述10.1 概述 設(shè) Ki、Kj (1in, 1jn, ij ) 分別為記錄 Ri、Rj 的關(guān)鍵字，且 Ki = Kj ，在排序前的序列中 R

2、i 領(lǐng)先于 Rj (即 i j )。若在排序后的序列中 Ri 仍領(lǐng)先于 Rj ，則稱所用的排序方法是穩(wěn)定的；反之，則稱所用的排序方法是不穩(wěn)定的。 例：設(shè)排序前的關(guān)鍵字序列為：52, 49, 80, 36, 14, 58, 36, 23 若排序后的關(guān)鍵字序列為：14, 23, 36, 36, 49, 52, 58, 80， 則排序方法是穩(wěn)定的。 若排序后的關(guān)鍵字序列為：14, 23, 36, 36, 49, 52, 58, 80， 則排序方法是不穩(wěn)定的。 概述10.1 概述內(nèi)部排序和外部排序 若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類排序問(wèn)題為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大，整個(gè)

3、序列的排序過(guò)程不可能在內(nèi)存中完成，則稱此類排序問(wèn)題為外部排序。 插入排序10.2 插入排序直接插入排序 初始狀態(tài)4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 3849659776132749 i =5 384965769713274976i =6 384965769713274913i =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟 排序 1 趟 排序 2 趟 排序 排序過(guò)程：先將序列中第 1 個(gè)

4、記錄看成是一個(gè)有序子序列， 然后從第 2 個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。 直接插入排序10.2 插入排序void InsertSort ( SqList &L ) / 對(duì)順序表 L 作直接插入排序。 for ( i = 2; i = L.length; + i ) if (L.ri.key L.ri -1.key) / InsertSort 在 r1. i-1中查找 ri 的插入位置; 對(duì)于在查找過(guò)程中找到的那些關(guān)鍵字 不小于 ri.key 的記錄，在查找的同 時(shí)實(shí)現(xiàn)記錄向后移動(dòng)； 插入 ri ;L.r0 = L.ri; / 復(fù)制為監(jiān)視哨 L.ri = L.ri -1; for

5、( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 記錄后移 L.r j + 1 = L.r0; / 插入到正確位置 直接插入排序性能分析 10.2 插入排序比較次數(shù)： 移動(dòng)次數(shù)： 0 最好的情況：待排序記錄按關(guān)鍵字從小到大排列（正序） 比較次數(shù)： 移動(dòng)次數(shù)： 最壞的情況：待排序記錄按關(guān)鍵字從大到小排列（逆序） 直接插入排序性能分析 10.2 插入排序 由于待排記錄序列是隨機(jī)的，取上述二值的平均值。所以直接插入排序的時(shí)間復(fù)雜度為O(n2)。 直接插入排序是“穩(wěn)定的”：關(guān)鍵碼相同的兩個(gè)記錄，在整個(gè)排序過(guò)程中，不會(huì)通過(guò)比較

6、而相互交換。折半插入排序10.2 插入排序(1) 基本思想 考慮到 L.r1,.,i-1 是按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“L.r1,i-1中查找 L.ri 的插入位置”如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。例：?個(gè)記錄，前5個(gè)已排序的基礎(chǔ)上，對(duì)第6個(gè)記錄排序。 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 42 53 69 10.2 插入排序(high36 )( 4253 ) high mid lowlow highmid high low折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的

7、原理尋找插入位置。待排序元素越多，改進(jìn)效果越明顯。折半插入排序算法10.2 插入排序void BinsertSort(SqList &L) / 折半插入排序 int i,low,high,mid; for(i=2; i= L.length; +i) L.r0=L.ri; /將L.r i 暫存到L.r0 low=1; high=i-1; While(low=high) /比較，折半查找插入位置 mid=(low+high)/2; / 折半 if (L.r0.key=low; j ) L.rj+1=L.rj; / 記錄后移 L.rlow=L.r0; / 插入 / BInsertSort折半插入排序

8、算法分析10.2 插入排序 折半查找比順序查找快，所以折半插入排序就平均性能來(lái)說(shuō)比直接插入排序要快。 折半插入排序減少了關(guān)鍵字的比較次數(shù)，但記錄的移動(dòng)次數(shù)不變，其時(shí)間復(fù)雜度與直接插入排序相同。 在插入第 i 個(gè)對(duì)象時(shí)，需要經(jīng)過(guò) log2i +1 次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。 折半插入排序是一個(gè)穩(wěn)定的排序方法。2-路插入排序10.2 插入排序(1) 基本思想 2-路插入排序是在折半插入排序的基礎(chǔ)上改進(jìn)的，目的是減少排序過(guò)程中移動(dòng)記錄的次數(shù)，但為此需要n個(gè)記錄的輔助空間。2-路插入排序10.2 插入排序(2) 具體做法 另設(shè)一個(gè)和 L.r 同類型的數(shù)組d，首先將 L.r1 賦值給d1 ，

9、并將d1看成是在排好序的序列中處于中間位置的記錄，然后從 L.r中第 2 個(gè)記錄起依次插入到d1之前或之后的有序序列中。先將待插入記錄的關(guān)鍵字和d1 的關(guān)鍵字進(jìn)行比較。 若 L.rid1.key，則將 L.ri 插入到d1 之前的有序表中。反之，插入到d1 之后的有序表中?！境跏缄P(guān)鍵字】 49 38 65 97 76 13 27 49 排序過(guò)程中d 的狀態(tài)如下：i=1: (49) i=2: (49) (38)i=3: (49 65) (38)i=4: (49 65 97) (38)i=5: (49 65 76 97) (38)i=6: (49 65 76 97) (13 38)i=7: (49

10、 65 76 97) (13 27 38)i=8: (49 49 65 76 97) (13 27 38)finalfirst2路插入排序過(guò)程示例：firstfinalfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstvoid Path2Insertion(SqList &L, SqList &d) d0 = L1;/L中D的第一個(gè)記錄為d中排好序的記錄。 int first = 0, final = 0;/first、final分別指示d中排好序的記錄的第1個(gè)和最后1個(gè)記錄的位置 for (int i = 2; i = l

11、ength; +i) /依次將L的第2個(gè)最后一個(gè)記錄插入d中。 if (Li dfinal) /待插入記錄大于d中最小值，插入到dfinal之后 final = final + 1; dfinal = Li; else /待插入記錄大于d中最小值，小于d中最大值，插入到d的中間(需要移動(dòng)d數(shù)組) int j = final +;/移動(dòng)d尾部元素以便按序插入記錄。 while (Li dj) d(j + 1) % length = dj; j = (j - 1 + length) % length; dj + 1 = Li; for (int i = 1; i = length; i +) /循

12、環(huán)把d賦給L。 Li = d(i + first - 1) % length;/線性關(guān)系。 2-路插入排序10.2 插入排序 2-路插入排序只能減少移動(dòng)記錄的次數(shù)，而不能絕對(duì)避免移動(dòng)記錄。 2-路插入排序中，移動(dòng)記錄的次數(shù)約為n2/8 。 當(dāng)L.r1是待排序記錄中關(guān)鍵字最小或最大的記錄時(shí)，2-路插入排序就完全失去了它的優(yōu)越性。表插入排序10.2 插入排序(1) 基本思想 通過(guò)改變排序過(guò)程中采用的存儲(chǔ)結(jié)構(gòu)，減少在排序過(guò)程中進(jìn)行“移動(dòng)”記錄的操作。利用靜態(tài)鏈表進(jìn)行排序，并在排序完成之后，一次性地調(diào)整各個(gè)記錄相互之間的位置，即將每個(gè)記錄都調(diào)整到它們所應(yīng)該在的位置上。表插入排序10.2 插入排序#de

13、fine MAXSIZE 100 /靜態(tài)鏈表容量Typedef struct RcdType rc; /記錄項(xiàng) int next; /指針項(xiàng) SLNode; /表結(jié)點(diǎn)類型Typedef struct SLNode rMAXSIZE+1; /0號(hào)單元為表頭結(jié)點(diǎn) int length; /鏈表當(dāng)前長(zhǎng)度 SLinkListType; /靜態(tài)鏈表類型(2) 待排記錄序列的存儲(chǔ)結(jié)構(gòu)表插入排序10.2 插入排序(3) 具體做法 首先將靜態(tài)鏈表中數(shù)組下標(biāo)為“1”的分量(結(jié)點(diǎn))和表頭結(jié)點(diǎn)構(gòu)成一個(gè)循環(huán)鏈表，然后依次將下標(biāo)為“2”至“n”的分量(結(jié)點(diǎn))按記錄關(guān)鍵字非遞減有序插入到循環(huán)鏈表中。10.2 插入排序vo

14、idTableSort(int*a,intn) nexthead=0=-1; for(i=1;in;i+) if(ai=ahead) nexti=head; head=i; else p=head; while(nextp!=-1&anextpai) p=nextp; nexti=nextp; nextp=i; 初始狀態(tài)012345678MAXINT493865977613274910-i=3012345678MAXINT4938659776132749201-key域next域i=2012345678MAXINT493865977613274910-38123650i=4012345678M

15、AXINT49386597761327492310-9740i=5012345678MAXINT493865977613274923140-i=6012345678MAXINT4938659776132749231504-i=7012345678MAXINT49386597761327496315042-i=8012345678MAXINT493865977613274963150472-7645136227724938表插入排序10.2 插入排序(4) 表插入排序性能分析 從表插入排序的過(guò)程可見(jiàn)，表插入排序的基本操作仍是將一個(gè)記錄插入到已排好序的有序表當(dāng)中。和直接插排序相比，不同之處僅是以修

16、改2n次指針值代替移動(dòng)記錄，排序過(guò)程中所需進(jìn)行的關(guān)鍵字間的比較次數(shù)相同。因此表插入排序的時(shí)間復(fù)雜度仍是O(n2)。表插入排序10.2 插入排序(4) 表插入排序性能分析 表插入排序的結(jié)果只是求得一個(gè)有序鏈表，則只能對(duì)它進(jìn)行順序查找，不能進(jìn)行隨機(jī)查找，為了能實(shí)現(xiàn)有序表的折半查找，尚需對(duì)記錄進(jìn)行重新排列。10.2 插入排序1.我們都能理解，優(yōu)秀排序算法的首要條件就是2.于是人們想了許許多多的排序辦法，目的就是為了提高排序的速度。3.而在很長(zhǎng)的時(shí)間里，眾人發(fā)現(xiàn)盡管各種排序算法花樣繁多，但時(shí)間復(fù)雜度都是O(n2)，似乎沒(méi)法超越了。4.計(jì)算機(jī)學(xué)術(shù)界充斥著“排序算法不可能突破O(n2)”的聲音？速度10.

17、2 插入排序 終于有一天，當(dāng)一位科學(xué)家發(fā)布超越了O(n2)新排序算法后，緊接著就出現(xiàn)了好幾種可以超越O(n2)的排序算法，并把內(nèi)排序算法的時(shí)間復(fù)雜度提升到了O(nlog2n)?！安豢赡艹絆(n2) ”徹底成為了歷史。希爾排序10.2 插入排序基本思想：先將整個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。技巧：子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)增量dk的記錄組成一個(gè)子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk1為止。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序

18、處理，時(shí)間效率會(huì)高很多。312345665499725251321234562525136549971123456132525654997123456132525496597增量3增量2增量1希爾排序過(guò)程希爾排序10.2 插入排序38例：關(guān)鍵字序列 T=(49, 38, 65, 97, 76, 13, 27, 49*, 55, 04) 請(qǐng)寫(xiě)出希爾排序的具體實(shí)現(xiàn)過(guò)程。0123456789104938659776132749*5504初 態(tài)第1趟 (dk=5)第2趟 (dk=3)第3趟 (dk=1)4913134938276549*975576042738 65 49*97551355760455

19、13270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 ri算法分析：開(kāi)始時(shí)dk 的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，dk 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。希爾排序算法描述10.2 插入排序void ShellInsert ( SqList &L, int dk ) /一趟希爾插入排序 /1.前后記錄位置的增量是dk； /2.L.r0只是暫存單元，不是哨兵。當(dāng)j=0時(shí)，插入位置已找到 for ( i=dk

20、+1; i=L.length; +i ) if ( L.ri.key0 & (L.r0.key L.rj.key);j -= dk) L.rj+dk = L.rj; / 記錄后移，查找插入位置 L.rj+dk = L.r0; / 插入 /ShellInsert希爾排序算法描述10.2 插入排序void ShellSort (SqList &L, int dlta , int t) / 按增量序列dlta0.t-1對(duì)順序表L作希爾排序 for (k=0; k1; i-) /i表示趟數(shù)，最多n-1趟 flag=0; /開(kāi)始時(shí)元素未交換 for (int j=2; j=i; j+) if (RjRj

21、-1) /發(fā)生逆序 temp=Rj; Rj=Rj-1; Rj-1=temp; flag=1; if(flag=0) return; / Bubblesort冒泡排序算法分析10.3 交換排序正序： 只需進(jìn)行一趟排序，在排序過(guò)程中進(jìn)行n-1次關(guān)鍵字間的比較，且不移動(dòng)記錄；時(shí)間復(fù)雜度為O(n) 。逆序： 需要進(jìn)行n-1趟排序，需要進(jìn)行n(n-1)/2次比較，并作等數(shù)量級(jí)的記錄移動(dòng)。總的時(shí)間復(fù)雜度為O(n2) 。 起泡排序方法是穩(wěn)定的。適合于數(shù)據(jù)較少的情況。快速排序10.3 交換排序背景 起泡排序的過(guò)程可見(jiàn)，起泡排序是一個(gè)增加有序序列長(zhǎng)度的過(guò)程，也是一個(gè)縮小無(wú)序序列長(zhǎng)度的過(guò)程，每經(jīng)過(guò)一趟起泡，無(wú)序序

22、列的長(zhǎng)度只縮小1。 試設(shè)想：若能在經(jīng)過(guò)一趟排序，使無(wú)序序列的長(zhǎng)度縮小一半，則必能加快排序的速度?？焖倥判?0.3 交換排序(1) 基本思想 通過(guò)一趟排序?qū)⒋判蛄幸詷休S為標(biāo)準(zhǔn)劃分成兩部分，使其中一部分記錄的關(guān)鍵字均比另一部分小，再分別對(duì)這兩部分進(jìn)行快速排序，以達(dá)到整個(gè)序列有序。 通常取第一個(gè)記錄的值為基準(zhǔn)值或樞軸?？焖倥判?0.3 交換排序(2) 具體做法 附設(shè)兩個(gè)指針low和high，初值分別指向第一個(gè)記錄和最后一個(gè)記錄，設(shè)樞軸為key； 1.從high 所指位置起向前搜索，找到第一個(gè)不大于基準(zhǔn)值的記錄與樞軸記錄相互交換； 2.從low 所指位置起向后搜索，找到第一個(gè)不小于基準(zhǔn)值的記錄與樞軸

23、記錄相互交換。 3.重復(fù)這兩步直至low=high為止?？焖倥判?0.3 交換排序lowhigh設(shè)Rs=52 為樞軸例： 52 52 49 80 36 14 58 61 97 23 75 high23 lowlow80highhighhighhigh14lowlow52一趟快速排序算法描述10.3 交換排序int Partition (Elem R , int low, int high) R0 = Rlow; pivotkey = Rlow.key; while (low high) /從兩端交替向中間掃描 while (low = pivotkey) - - high; Rlow = Rh

24、igh; /將比樞軸記錄小的移到低端 while (low high & Rlow.key = pivotkey) + + low; Rhigh = Rlow; /將比樞軸記錄大的移到高端 Rlow = R0; /樞軸記錄到位 return low; /返回樞軸位置 / Partition快速排序算法過(guò)程 10.3 交換排序無(wú) 序 的 記 錄 序 列無(wú)序記錄子序列 (1)無(wú)序子序列 (2) 樞軸 一次劃分 分別進(jìn)行一趟快速排序 有 序 的 記 錄 序 列 快速排序算法描述10.3 交換排序void QSort ( Elem R , int low, int high ) /對(duì)序列Rlow.hi

25、gh進(jìn)行快速排序 if (low high-1) /長(zhǎng)度大于1 pivot = Partition( L,low,high); /將Rlow.high一分為二 QSort(L,low, pivot-1); /對(duì)低子表遞歸排序，pivo是樞軸 QSort(L, pivot+1, high); / 對(duì)高子表遞歸排序 / QSortvoid QuickSort(Elem R, int n) /對(duì)記錄序列進(jìn)行快速排序 QSort(R, 1, n); / QuickSort076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742

26、，751，863，937076，129，256，751，937，863，742，694，301，438076，129，256，438，301，694，742，694，863，937256，301，751，129，937，863，742，694，076，438例：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫(xiě)出執(zhí)行快速算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。原始序列： 256，301，751，129，937，863，742，694，076，438第1趟第2趟第3趟第4趟要求模擬算法實(shí)現(xiàn)步驟25607630112975125675143807

27、6，129，256，301，438，694，742，751，863，937時(shí)間效率：O(nlog2n) 因?yàn)槊刻舜_定的元素呈指數(shù)增加空間效率：O(log2n)因?yàn)樗惴ǖ倪f歸性，要用到?？臻g穩(wěn) 定 性：不穩(wěn)定 因?yàn)榭蛇x任一元素為支點(diǎn)?？焖倥判蛩惴ㄔ敿?xì)分析10.3 交換排序可以證明，函數(shù)Quicksort的平均計(jì)算時(shí)間是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個(gè)?？焖倥判蚴沁f歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)(新的low和high)。最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的深度一致，理想情況為 log2(n+1) 。因此，要求存儲(chǔ)開(kāi)銷為

28、 O(log2n)?？焖倥判蛩惴ㄔ敿?xì)分析10.3 交換排序最好情況：如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同，則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序，這是最理想的情況。此時(shí)，快速排序的趟數(shù)最少。最壞情況：即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下，其遞歸樹(shù)成為單支樹(shù)，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。這樣，必須經(jīng)過(guò) n-1 趟才能把所有對(duì)象定位，而且第 i 趟需要經(jīng)過(guò) n-i 次關(guān)鍵碼比較才能找到第 i 個(gè)對(duì)象的安放位置，總的關(guān)鍵碼比較次數(shù)將達(dá)到n2/2快速排序是否真的比任何排序算法都快？10.3 交換排序設(shè)每個(gè)子表的支點(diǎn)都在中間（比較均衡），則：第1趟比較，可以確定1個(gè)元素的位置；第2趟比較（2個(gè)子表），可以再確定2個(gè)元素的位置；第3趟比較（4個(gè)子表），可以再確定4個(gè)元素的位置；第4趟比較（8個(gè)子表），可以再確定8個(gè)元素的位置； 只需log2n 1趟便可排好序。基本上是！因?yàn)槊?/p>