1、概述插入排序(直接插入、折半插入、表插入排序、希爾排序課件概述插入排序(直接插入、折半插入、表插入排序、希爾排序課件概述排序：將一組雜亂無(wú)章的數(shù)據(jù)排列成一個(gè)按關(guān)鍵字有序的序列。 數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對(duì)象的有限集合。關(guān)鍵字(key): 通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)象，作為排序依據(jù)。該域即為關(guān)鍵字。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為關(guān)鍵字，要視具體的應(yīng)用需要而定。即使是同一個(gè)表，在解決不同問(wèn)題的場(chǎng)合也可能取不同的域做關(guān)鍵字。概述排序：將一組雜亂無(wú)章的數(shù)據(jù)排列成一個(gè)按關(guān)鍵字有序的序列。主關(guān)鍵字: 如果在數(shù)據(jù)表中各個(gè)對(duì)象的關(guān)鍵字互 不相同，

2、這種關(guān)鍵字即主關(guān)鍵字。按照主關(guān)鍵字 進(jìn)行排序，排序的結(jié)果是唯一的。次關(guān)鍵字: 數(shù)據(jù)表中有些對(duì)象的關(guān)鍵字可能相 同，這種關(guān)鍵字稱為次關(guān)鍵字。按照次關(guān)鍵字 進(jìn)行排序，排序的結(jié)果可能不唯一。排序算法的穩(wěn)定性: 如果在對(duì)象序列中有兩個(gè)對(duì) 象ri和rj，它們的關(guān)鍵字 ki = kj，且在 排序之前，對(duì)象ri排在rj前面。如果在排序 之后，對(duì)象ri仍在對(duì)象rj的前面，則稱這個(gè) 排序方法是穩(wěn)定的，否則稱這個(gè)排序方法是不 穩(wěn)定的。主關(guān)鍵字: 如果在數(shù)據(jù)表中各個(gè)對(duì)象的關(guān)鍵字互內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序

3、過(guò)程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。排序的時(shí)間開(kāi)銷: 排序的時(shí)間開(kāi)銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開(kāi)銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來(lái)衡量。各節(jié)給出算法運(yùn)行時(shí)間代價(jià)的大略估算一般都按平均情況進(jìn)行估算。對(duì)于那些受對(duì)象關(guān)鍵字序列初始排列及對(duì)象個(gè)數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在靜態(tài)排序: 排序的過(guò)程是對(duì)數(shù)據(jù)對(duì)象本身進(jìn)行物理地重排，經(jīng)過(guò)比較和判斷，將對(duì)象移到合適的位置。這時(shí)，數(shù)據(jù)對(duì)象一般都存放在一個(gè)順序的表中。動(dòng)態(tài)排序: 給每個(gè)對(duì)象增加一個(gè)鏈接指針，在排序的過(guò)程中不移動(dòng)對(duì)象或傳送數(shù)據(jù)，僅通過(guò)修改鏈接指針

4、來(lái)改變對(duì)象之間的邏輯順序，從而達(dá)到排序的目的。算法執(zhí)行時(shí)所需的附加存儲(chǔ): 評(píng)價(jià)算法好壞的另一標(biāo)準(zhǔn)。靜態(tài)排序過(guò)程中所用到的數(shù)據(jù)表的定義，體現(xiàn)了抽象數(shù)據(jù)類型的思想。靜態(tài)排序: 排序的過(guò)程是對(duì)數(shù)據(jù)對(duì)象本身進(jìn)行物理地重排，經(jīng)衡量排序方法的標(biāo)準(zhǔn)排序時(shí)所需要的平均比較次數(shù)排序時(shí)所需要的平均移動(dòng)排序時(shí)所需要的平均輔助存儲(chǔ)空間衡量排序方法的標(biāo)準(zhǔn)插入排序 (Insert Sorting)直接插入排序的基本思想是：當(dāng)插入第i (i 1) 個(gè)對(duì)象時(shí)，前面的V0, V1, , vi-1已經(jīng)排好序。這時(shí)，用vi的關(guān)鍵字與vi-1, vi-2, 的關(guān)鍵字順序進(jìn)行比較，找到插入位置即將vi插入，原來(lái)位置上之后的所有對(duì)象依次

5、向后順移。插入排序的基本方法是：每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。直接插入排序 (Insert Sort)插入排序 (Insert Sorting)直接插入排序的基本各趟排序結(jié)果21254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*160825i = 10 1 2 3 4 5 temp21254925*160849i = 2各趟排序結(jié)果21254925*16080 1 21254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*1608i =

6、 40 1 2 3 4 5 temp21254925*1608i = 5i = 325*160821254925*16080 1 1649161621254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*08i = 4 時(shí)的排序過(guò)程0 1 2 3 4 5 temp21254925*完成160816i = 4j = 3i = 4j = 21649161621254925*16080 2525*161621254925*080 1 2 3 4 50 1 2 3 4 5 temp214925*080 1 2 3 4 5 temp21254925*1608161

7、62521i = 4j = 1i = 4j = 0i = 4j = -1162525*161621254925*080 1直接插入排序的算法 （p265算法10.1）void InsertSort(SqList &L) for (int i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key) L.r0=L.ri; / L.r0為監(jiān)視哨 for (int j=i-1; LT(L.r0.key,L.rj.key); -j)L.rj+1=L.rj; L.rj+1=L.r0; 直接插入排序的算法 （p265算法10.1）算法分析若設(shè)待排序的對(duì)象個(gè)數(shù)為L(zhǎng).length

8、= n，則該算法的主程序執(zhí)行n-1趟。關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵字的初始排列有關(guān)。最好情況下，排序前對(duì)象已經(jīng)按關(guān)鍵字大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象的關(guān)鍵字比較 1 次，移動(dòng) 2 次對(duì)象，總的關(guān)鍵字比較次數(shù)為 n-1，對(duì)象移動(dòng)次數(shù)為 2(n-1)。算法分析若設(shè)待排序的對(duì)象個(gè)數(shù)為L(zhǎng).length= n，則該算分析：一個(gè)記錄的輔助存儲(chǔ)空間 監(jiān)視哨比較次數(shù)最小比較次數(shù)：Cmin=n-1最大比較次數(shù)： Cmax=平均比較次數(shù)： Cavg=(n-1)(n+4)/4移動(dòng)次數(shù)最小移動(dòng)次數(shù)：Mmin=0最大移動(dòng)次數(shù)：Mmax=平均移動(dòng)次數(shù)： Mavg=(n+8)(n-1

9、)/4分析：若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好折半插入排序 (Binary Insertsort)折半插入排序基本思想是：設(shè)在順序表中有一 個(gè)對(duì)象序列 V0, V1, , vn-1。其中，v0, V1, , vi-1 是已經(jīng)排好序的對(duì)象。在插入 vi 時(shí)，利用折半搜索法尋找 vi 的插入位置。折半插入排序 (Binary Insertsort)折半

10、插入 折半插入排序的算法void BInsertSort(SqList &L) int low,high,mid; for (int i=2;i=L.length;+i) L.r0=L.ri; low = 1; high=i-1; while (low =high+1;-j) L.rj+1=L.rj; L.rhigh+1=L.r0;說(shuō)明：low 或者 high+1為插入點(diǎn) 穩(wěn)定排序 折半插入排序的算法算法分析二分查找比順序查找快，所以二分插入排序就平均性能來(lái)說(shuō)比直接插入排序要快。它所需要的關(guān)鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o(wú)關(guān)，僅依賴于對(duì)象個(gè)數(shù)。在插入第 i 個(gè)對(duì)象時(shí)，需要經(jīng)過(guò) log2

11、i +1 次關(guān)鍵字比較，才能確定它應(yīng)插入的位置。因此，將 n 個(gè)對(duì)象（為推導(dǎo)方便，設(shè)為 n=2k )用二分插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為：算法分析二分查找比順序查找快，所以二分插入排序就平均性能來(lái)說(shuō)概述插入排序(直接插入、折半插入、表插入排序、希爾排序課件當(dāng) n 較大時(shí)，總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字排好序或接近有序時(shí)，直接插入排序比二分插入排序執(zhí)行的關(guān)鍵字比較次數(shù)要少。二分插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同，依賴于對(duì)象的初始排列。二分插入排序是一個(gè)穩(wěn)定的排序方法。當(dāng) n 較大時(shí)，總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情

12、況要好希爾排序 (Shell Sort)希爾排序方法又稱為“縮小增量”排序。該方法的基本思想是：先將整個(gè)待排對(duì)象序列按照一定間隔分割成為若干子序列，分別進(jìn)行直接插入排序，然后縮小間隔，對(duì)整個(gè)對(duì)象序列重復(fù)以上的劃分子序列和分別排序工作，直到最后間隔為1，此時(shí)整個(gè)對(duì)象序列已 “基本有序”，進(jìn)行最后一次直接插入排序。希爾排序 (Shell Sort)希爾排序方法又稱為“縮小增21254925*16080 1 2 3 4 52125*i = 10849gap = 32516492516084925*0821252125*16希爾排序過(guò)程示例21254925*16080 1 21254925*16080

13、 1 2 3 4 521i = 20849gap = 22516491625*0821254925*08162125*2521254925*16080 1 21254925*16080 1 2 3 4 521i = 308gap = 125164925*開(kāi)始時(shí) gap（間隔值） 的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，gap 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。21254925*16080 1 希爾排序的算法void ShellSort(SqList &L, int dlta,int t)for (int k=

14、0;kt;+k)ShellInsert(L,dltak);說(shuō)明：dlta3=5，3，1希爾排序的算法/一趟希爾排序,按間隔dk劃分子序列void ShellInsert(SqList &L, int gap)for (int i=gap+1;i0 & LT(L.r0.key,L.rj.key); j-=gap)L.rj+gap=L.rj;L.rj+gap=L.r0;/一趟希爾排序,按間隔dk劃分子序列算法分析對(duì)特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)鍵字的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。但想要弄清關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒(méi)有人能夠做到。gap的取法有

15、多種。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。后來(lái)Knuth 提出取gap = gap/3 +1。還有人提出都取奇數(shù)為好，也有人提出各gap互質(zhì)為好。其他取法：教材p272 倒數(shù)第二段算法分析對(duì)特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)鍵字的比較次Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng) n 很大時(shí)，關(guān)鍵字平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)大約在 n1.25 到 1.6n1.25 的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng) n 很大時(shí)，關(guān)鍵字初始關(guān)鍵字序列：4938659776132749

16、*123456785504910增量d5132749*5504493865123456789776910第一趟排序結(jié)果：增量d3第二趟排序結(jié)果：130449*3827495565123456789776910增量d1第三趟排序結(jié)果：0413273849*495565123456787697910132749*55044938659776練習(xí)題初始關(guān)鍵字序列：4938659776132749*12345交換排序 ( Exchange Sort )起泡排序的基本方法是：設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為 n。最多作 n-1 趟排序。在第 i 趟中順次兩兩比較rj-1.Key和rj.Key，j = i,

17、 i+1, , n-i-1。如果發(fā)生逆序，則交換rj-1和rj。交換排序的基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之，直到所有對(duì)象都排好序?yàn)橹埂Ｆ鹋菖判?(Bubble Sort)交換排序 ( Exchange Sort )起泡排序的基本方21254925*16080 1 2 3 4 52125*i = 149251649chang=10825*chang=1i = 2i = 30816chang=125*25214921251608起泡排序過(guò)程示例21254925*16080 1 25*0 1 2 3 4 5i = 44916chang=

18、108252125*0 1 2 3 4 5i = 54916chang=008252125*0 1 2 void BubbleSort(SqList &L) int i, j, tag; j = L.length-1; do tag=1; for(i=1; i=j; i+) if( L.ri+1.key1 & change; -i) change = FALSE;for (int j=1; ji; +j) if (LT(L.rj+1.key,L.rj.key) ElemType temp=L.rj;L.rj=L.rj+1;L.rj+1=temp;change = TRUE; 起泡排序的算法2v

19、oid BubbleSort(SqList &L)起泡排序特 點(diǎn)至少比較1次，至多比較n-1次；一次確定位置；可實(shí)現(xiàn)部分排序穩(wěn)定排序特 點(diǎn)至少比較1次，至多比較n-1次；算法分析在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵字比較，不移動(dòng)對(duì)象。這是最好的情形。最壞的情形是算法執(zhí)行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次關(guān)鍵字比較，執(zhí)行了n-i 次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：算法分析在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法 起泡排序需要一個(gè)附加對(duì)象以實(shí)現(xiàn)對(duì)象值的對(duì)換。起泡排序是

20、一個(gè)穩(wěn)定的排序方法。 起泡排序需要一個(gè)附加對(duì)象以實(shí)現(xiàn)對(duì)象值的對(duì)換。練習(xí)題初始關(guān)鍵字序列：4938659776132749*1234567838496576132749*97第一趟排序后：384965132749*7697第二趟排序后：3849132749*657697第三趟排序后：3813274949*657697第四趟排序后：1327384949*657697第五趟排序后：1327384949*657697第六趟排序后：練習(xí)題初始關(guān)鍵字序列：4938659776132749*12快速排序 (Quick Sort)快速排序方法的基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象 (例如取第一個(gè)對(duì)象) 作

21、為樞軸(pivot)，按照該對(duì)象的關(guān)鍵字大小，將整個(gè)對(duì)象序列劃分為左右兩個(gè)子序列： 左側(cè)子序列中所有對(duì)象的關(guān)鍵字都小于或等于樞軸對(duì)象的關(guān)鍵字 右側(cè)子序列中所有對(duì)象的關(guān)鍵字都大于樞軸對(duì)象的關(guān)鍵字樞軸對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置)。快速排序 (Quick Sort)快速排序方法的基本思想是任 然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止。算法描述QuickSort ( List ) if ( List的長(zhǎng)度大于1) 將序列List劃分為兩個(gè)子序列 LeftList 和 Right List; QuickSort ( LeftList );Q

22、uickSort ( RightList ); 將兩個(gè)子序列 LeftList 和 RightList 合并為一個(gè)序列List; 然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)21254925*16080 1 2 3 4 52125*i = 149251625160849pivot0825*4921i = 2i = 3081625*2521pivotpivotpivot21254925*16080 1 21254925*16080 1 2 3 4 525*i = 1劃分251625160849pivotpos0825*49081625*2521pivotpos21比較4次交換25,16i

23、ipivotpos21比較1次交換49,0849low pivotpos交換21,0821254925*16080 1 快速排序的算法void QSort(SqList &L, int low, int high)if (low high)int pivotloc = Partition(L,low,high);QSort(L,low, pivotloc-1);PrintST(L);QSort(L,pivotloc+1, high);PrintST(L);void QuickSort(SqList &L)QSort(L,1,L.length);快速排序的算法int Partition(SqLi

24、st &L, int low, int high) L.r0 = L.rlow; int pivotkey = L.rlow.key; while (low high) while (low= pivotkey) -high;L.rlow = L.rhigh;while (lowhigh & L.rlow.key = pivotkey) +low;L.rhigh = L.rlow; L.rlow=L.r0;return low;int Partition(SqList &L, int l 算法quicksort是一個(gè)遞歸的算法，其遞歸樹(shù)如圖所示。算法partition利用序列第一個(gè)對(duì)象作為樞軸

25、，將整個(gè)序列劃分為左右兩個(gè)子序列。算法中執(zhí)行了一個(gè)循環(huán)，只要是關(guān)鍵字小于樞軸對(duì)象關(guān)鍵字的對(duì)象都移到序列左側(cè)，最后樞軸對(duì)象安放到位，函數(shù)返回其位置。2125*25490816 算法quicksort是一個(gè)遞歸的算法，其遞歸樹(shù)如圖算法分析從快速排序算法的遞歸樹(shù)可知，快速排序的趟數(shù)取決于遞歸樹(shù)的深度。如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同，則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序，這是最理想的情況。在n個(gè)元素的序列中，對(duì)一個(gè)對(duì)象定位所需時(shí)間為 O(n)。若設(shè) t(n) 是對(duì) n 個(gè)元素的序列進(jìn)行排序所需的時(shí)間，而且每次對(duì)一個(gè)對(duì)象正確定位后，正好把序列劃分為長(zhǎng)度相等的

26、兩個(gè)子序列，此時(shí)，總的計(jì)算時(shí)間為：算法分析從快速排序算法的遞歸樹(shù)可知，快速排序的趟數(shù)取決于遞歸 T(n) cn + 2 t(n/2 ) / c是一個(gè)常數(shù) Cn + 2 ( cn/2 + 2t(n/4) ) = 2cn + 4t(n/4) 2cn + 4 ( cn/4 +2t(n/8) ) = 3cn + 8t(n/8) Cn log2n + nt(1) = o(n log2n )可以證明，函數(shù)quicksort的平均計(jì)算時(shí)間也是o(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個(gè)。 T(n) cn + 2 t(n/2 ) 快速排序是遞歸的，需要

27、有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的深度一致，理想情況為 log2(n+1) 。因此，要求存儲(chǔ)開(kāi)銷為 o(log2n)。在最壞的情況，即待排序?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á)到快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)其排序速度退化到簡(jiǎn)單排序的水平，比直接插入排序還慢。占用附加存儲(chǔ)(即棧)將達(dá)到o(n)。若能更合理地選擇基

28、準(zhǔn)對(duì)象，使得每次劃分所得的兩個(gè)子序列中的對(duì)象個(gè)數(shù)盡可能地接近，可以加速排序速度，但是由于對(duì)象的初始排列次序是隨機(jī)的，這個(gè)要求很難辦到。有一種改進(jìn)辦法：取每個(gè)待排序?qū)ο笮蛄械牡谝粋€(gè)對(duì)象、最后一個(gè)對(duì)象和位置接近正中的3個(gè)對(duì)象，取其關(guān)鍵字居中者作為基準(zhǔn)對(duì)象。其排序速度退化到簡(jiǎn)單排序的水平，比直接插入排序還慢。占用附加用第一個(gè)對(duì)象作為基準(zhǔn)對(duì)象 快速排序退化的例子 08 16 21 25 25* 49080 1 2 3 4 5 pivot初始 16 21 25 25* 49 0816 21 25 25* 4921 08 1625 25 25* 49 08 16 21 25* 4925* 08 16 21

29、 2549 08 16 21 25 25*i = 1i = 2i = 3i = 4i = 5用第一個(gè)對(duì)象作為基準(zhǔn)對(duì)象 快速排序退化的例子 08用居中關(guān)鍵字對(duì)象作為基準(zhǔn)對(duì)象快速排序是一種不穩(wěn)定的排序方法。對(duì)于 n 較大的平均情況而言，快速排序是“快速”的，但是當(dāng) n 很小時(shí)，這種排序方法往往比其它簡(jiǎn)單排序方法還要慢。 08 16 21 25 25* 490 1 2 3 4 5 pivot21初始 08 16 21 25 25* 490825* 08 16 21 25 25*49i = 1i = 2用居中關(guān)鍵字對(duì)象作為基準(zhǔn)對(duì)象快速排序是一種不穩(wěn)定的排序方法。386597132749*5512345

30、67849049pivotij練習(xí)題:快速排序中的一趟劃分386597132749*551234567849049pi快速排序中的一趟劃分(續(xù))386597132749*55123456784904949ijL.rj與pivot比較，L.rj小則與L.ri交換；否則j減10449L.rj 與L.ri交換，i加1快速排序中的一趟劃分(續(xù))386597132749*5512快速排序中的一趟劃分(續(xù))386597132749*55123456780449949pivotijL.ri與pivot比較，L.ri大則與L.rj交換；否則i增1快速排序中的一趟劃分(續(xù))386597132749*5512快速

31、排序中的一趟劃分(續(xù))L.ri與pivot比較，L.ri大則與L.rj交換；否則i增1386597132749*55123456780449949pivotij4965L.ri與L.rj交換，j減1快速排序中的一趟劃分(續(xù))L.ri與pivot比較，L.快速排序中的一趟劃分(續(xù))384997132749*55123456780465949ijL.rj與pivot比較，L.rj小則與L.ri交換；否則j減1快速排序中的一趟劃分(續(xù))384997132749*5512快速排序中的一趟劃分(續(xù))384997132749*55123456780465949pivotijL.rj與pivot比較，L.r

32、j小則與L.ri交換；否則j減1快速排序中的一趟劃分(續(xù))384997132749*5512快速排序中的一趟劃分(續(xù))L.rj與pivot比較，L.rj小則與L.ri交換；否則j減1384997132749*55123456780465949pivotij2749L.rj小則與L.ri交換，i加1快速排序中的一趟劃分(續(xù))L.rj與pivot比較，L.快速排序中的一趟劃分(續(xù))pivot382797134949*55123456780465949pivotijL.ri與pivot比較，L.ri大則與L.rj交換；否則i增1L.ri大則與L.rj交換，j減14997快速排序中的一趟劃分(續(xù))pi

33、vot382797134949快速排序中的一趟劃分(續(xù))pivotL.rj與pivot比較，L.rj小則與L.ri交換；否則j減1382749139749*55123456780465949pivotijL.rj小則與L.ri交換，i加11349快速排序中的一趟劃分(續(xù))pivotL.rj與pivot快速排序中的一趟劃分(續(xù))382713499749*55123456780465949pivotij當(dāng)i與j相等時(shí)，樞軸元素確定了位置i，結(jié)束本次劃分快速排序中的一趟劃分(續(xù))382713499749*5512 選擇排序的基本思想是：每一趟 (例如第 i 趟，i = 1, , n-1) 在后面的

34、n-i+1 個(gè)待排序?qū)ο笾羞x出關(guān)鍵字最小的對(duì)象, 作為有序?qū)ο笮蛄械牡?i 個(gè)對(duì)象。待到第 n-1 趟作完，待排序?qū)ο笾皇Ｏ?個(gè)，就不用再選了。選擇排序(Selection Sort)基本步驟為：i從1開(kāi)始，直到n-1，進(jìn)行n-1趟排序，第i 趟的排序過(guò)程為： 在一組對(duì)象rirn (i=1,2,n-1)中選擇具有最小關(guān)鍵字的對(duì)象；并和第 i 個(gè)對(duì)象進(jìn)行交換；簡(jiǎn)單選擇排序 (Simple Selection Sort) 選擇排序的基本思想是：每一趟 (例如第 i 趟，i 簡(jiǎn)單選擇排序的算法void SelectSort(SqList &L) for (int i=1; iL.length;+i)

35、 int k=i; for (int j=i+1;j L.rj.key) k=j; if (i!=k) ElemType temp=L.ri; L.ri=L.rk; L.rk=temp; 簡(jiǎn)單選擇排序的算法21254925*16080 1 2 3 4 52125*i = 1492516251608490825*4921i = 2i = 3081625*2521初始最小者 08交換21,08最小者 16交換25,16最小者 21交換49,2121254925*16080 1 4925*0 1 2 3 4 525*i = 52516084925*4921結(jié)果i = 408162521最小者 25*

36、無(wú)交換最小者 25無(wú)交換25211608各趟排序后的結(jié)果4925*0 1 20 1 2 3 4 549160825*49210825*2521i =2時(shí)選擇排序的過(guò)程i k j 49250825*1621i k j 49 2525* 251625i k j 16 250 1 2 49250825*16210 1 2 3 4 5i k j 21 16k 指示當(dāng)前序列中最小者算法分析 直接選擇排序的關(guān)鍵字比較次數(shù)KCN與對(duì)象的初始排列無(wú)關(guān)。第 i 趟選擇具有最小關(guān)鍵字對(duì)象所需的比較次數(shù)總是 n-i-1 次，此處假定整個(gè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象。因此，總的關(guān)鍵字比較次數(shù)為49250825*162

37、10 1 對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時(shí)候，對(duì)象的移動(dòng)次數(shù)RMN = 0，達(dá)到最少。最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為RMN = 3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)錦標(biāo)賽排序 (Tournament Tree Sort)樹(shù)形選擇排序(Tree Selection Sort)它的思想與體育比賽時(shí)的淘汰賽類似。首先取得 n 個(gè)對(duì)象的關(guān)鍵字，進(jìn)行兩兩比較，得到 n/2 個(gè)比較的優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來(lái)。然后對(duì)這 n/2 個(gè)對(duì)象再

38、進(jìn)行關(guān)鍵字的兩兩比較，如此重復(fù)，直到選出一個(gè)關(guān)鍵字最小的對(duì)象為止。在圖例中，最下面是對(duì)象排列的初始狀態(tài)，相當(dāng)于一棵滿二叉樹(shù)的葉結(jié)點(diǎn)，它存放的是所有參加排序的對(duì)象的關(guān)鍵字。錦標(biāo)賽排序 (Tournament Tree Sort)樹(shù)如果 n 不是2的 k 次冪，則讓葉結(jié)點(diǎn)數(shù)補(bǔ)足到滿足 2k-1 n 2k 的2k個(gè)。葉結(jié)點(diǎn)上面一層的非葉結(jié)點(diǎn)是葉結(jié)點(diǎn)關(guān)鍵字兩兩比較的結(jié)果。最頂層是樹(shù)的根。08Winner 2108086325*2121254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14如果 n 不是2的 k 次冪，則讓葉結(jié)點(diǎn)

39、數(shù)補(bǔ)足到滿足 2k-勝者樹(shù)的概念每次兩兩比較的結(jié)果是把關(guān)鍵字小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn)，稱這種比賽樹(shù)為勝者樹(shù)。位于最底層的葉結(jié)點(diǎn)叫做勝者樹(shù)的外結(jié)點(diǎn)，非葉結(jié)點(diǎn)稱為勝者樹(shù)的內(nèi)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)除了存放對(duì)象的關(guān)鍵字 key 外，還存放了此對(duì)象是否要參選的標(biāo)志 Active 和此對(duì)象在滿二叉樹(shù)中的序號(hào)index。勝者樹(shù)最頂層是樹(shù)的根，表示最后選擇出來(lái)的具有最小關(guān)鍵字的對(duì)象。勝者樹(shù)的概念每次兩兩比較的結(jié)果是把關(guān)鍵字小者作為優(yōu)勝者上升到08Winner (勝者)2108086325*2121254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13

40、tree14 形成初始勝者樹(shù)（最小關(guān)鍵字上升到根）a0關(guān)鍵字比較次數(shù) : 6 08Winner (勝者)2108086325*21212516Winner (勝者)2116166325*2121254925*1663tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出冠軍并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài)a1關(guān)鍵字比較次數(shù) : 2 16Winner (勝者)2116166325*21212521Winner (勝者)21636325*2121254925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13

41、tree14輸出亞軍并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài)a2關(guān)鍵字比較次數(shù) : 2 21Winner (勝者)21636325*2121254925Winner (勝者)25636325*25254925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出第三名并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài)a3關(guān)鍵字比較次數(shù) : 2 25Winner (勝者)25636325*2525492525*Winner (勝者)25*636325*4925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出第四名并調(diào)

42、整勝者樹(shù)后樹(shù)的狀態(tài)a4關(guān)鍵字比較次數(shù) : 2 25*Winner (勝者)25*636325*4925*663Winner (勝者)636363tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14全部比賽結(jié)果輸出時(shí)樹(shù)的狀態(tài)a6關(guān)鍵字比較次數(shù) : 2 63Winner (勝者)636363tree7 tr算法分析錦標(biāo)賽排序構(gòu)成的樹(shù)是滿的完全二叉樹(shù)，其深度為 log2(n+1)，其中 n 為待排序元素個(gè)數(shù)。除第一次選擇具有最小關(guān)鍵字的對(duì)象需要進(jìn)行 n-1 次關(guān)鍵字比較外，重構(gòu)勝者樹(shù)選擇具有次小、再次小關(guān)鍵字對(duì)象所需的關(guān)鍵字比較次數(shù)均為 O(log

43、2n)。總關(guān)鍵字比較次數(shù)為O(nlog2n)。對(duì)象的移動(dòng)次數(shù)不超過(guò)關(guān)鍵字的比較次數(shù)，所以錦標(biāo)賽排序總的時(shí)間復(fù)雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時(shí)間，但是使用了較多的附加存儲(chǔ)。算法分析錦標(biāo)賽排序構(gòu)成的樹(shù)是滿的完全二叉樹(shù)，其深度為 lo如果有 n 個(gè)對(duì)象，必須使用至少 2n-1 個(gè)結(jié)點(diǎn)來(lái)存放勝者樹(shù)。最多需要找到滿足 2k-1 n 2k 的k，使用 2*2k-1 個(gè)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)包括關(guān)鍵字、對(duì)象序號(hào)和比較標(biāo)志三種信息。錦標(biāo)賽排序是一個(gè)穩(wěn)定的排序方法。如果有 n 個(gè)對(duì)象，必須使用至少 2n-1 個(gè)結(jié)點(diǎn)來(lái)存放勝者堆排序 (Heap Sort)利用堆及其運(yùn)算，可以很容易地實(shí)現(xiàn)選擇排序

44、的思路。堆排序分為兩個(gè)步驟：第一步，根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法 HeapAdjust ( ) 形成初始堆，第二步，通過(guò)一系列的對(duì)象交換和重新調(diào)整堆進(jìn)行排序。給定一組關(guān)鍵字，初始態(tài)存儲(chǔ)時(shí)是一個(gè)完全二叉樹(shù)堆的建立對(duì)堆的篩選與建立的重復(fù)交替堆排序 (Heap Sort)利用堆及其運(yùn)算，可以很容易地實(shí)堆排序 (Heap Sort)給定一組關(guān)鍵字，初始態(tài)存儲(chǔ)時(shí)是一個(gè)完全二叉樹(shù)堆的建立： 對(duì) m/2 1,的元素依次進(jìn)行篩選：若ki=k2i且kik2i(k2i+1)且kik2i且kik2i+1，則ki與較小的哪個(gè)交換若k2i=k2i+1) ki,則ki與k2i交換對(duì)堆的篩選與建立的重復(fù)交替堆排序 (

45、Heap Sort)給定一組關(guān)鍵字，初始態(tài)存儲(chǔ)時(shí)是建立初始的最大堆212525*491608123456i212525*164908136542i21 25 49 25* 16 08初始關(guān)鍵字集合21 25 49 25* 16 08i = 3 時(shí)的局部調(diào)整建立初始的最大堆212525*491608123456i21212525*491608123456i492525*16210813654221 25 49 25* 16 0849 25 21 25* 16 08i = 1 時(shí)的局部調(diào)整形成大頂堆i = 2 時(shí)的局部調(diào)整212525*491608123456i492525*162最大堆的向下調(diào)整

46、算法void HeapAdjust(HeapType &H,int s,int m) ElemType rc=H.rs; for (int j=2*s;j=m;j*=2) if (j0; -i) HeapAdjust(H,i,H.length); for (i=H.length; i1; -i) temp=H.r1;H.r1=H.ri;H.ri=temp;HeapAdjust(H,1,i-1); 堆排序的算法算法分析若設(shè)堆中有 n 個(gè)結(jié)點(diǎn)，且 2k-1 n 2k，則對(duì)應(yīng)的完全二叉樹(shù)有 k 層。在第 i 層上的結(jié)點(diǎn)數(shù) 2i-1 (i = 1, , k)。在第一個(gè)形成初始堆的for循環(huán)中對(duì)每一個(gè)非

47、葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法HeapAdjust ( )，因此該循環(huán)所用的計(jì)算時(shí)間為：其中，i 是層序號(hào)，2i-1 是第 i 層的最大結(jié)點(diǎn)數(shù)，(k-i-1)是第 i 層結(jié)點(diǎn)能夠移動(dòng)的最大距離。算法分析若設(shè)堆中有 n 個(gè)結(jié)點(diǎn)，且 2k-1 n 2在第二個(gè)for循環(huán)中，調(diào)用了n-1次HeapAdjust ( )算法，該循環(huán)的計(jì)算時(shí)間為O(nlog2n)。因此，堆排序的時(shí)間復(fù)雜性為O(nlog2n)。該算法的附加存儲(chǔ)主要是在第二個(gè)for循環(huán)中用來(lái)執(zhí)行對(duì)象交換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個(gè)不穩(wěn)定的排序方法。在第二個(gè)for循環(huán)中，調(diào)用了n-1次HeapAdjust

48、(歸并排序 (Merge Sort)歸并，是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。對(duì)象序列 initList 中有兩個(gè)有序表Vl Vm和Vm+1 Vn。它們可歸并成一個(gè)有序表，存于另一對(duì)象序列 mergedList 的Vl Vn中。這種歸并方法稱為2-路歸并 (2-way merging)。其基本思想是：設(shè)兩個(gè)有序表A和B的對(duì)象個(gè)數(shù)(表長(zhǎng))分別為 al 和 bl，變量 i 和 j 分別是表A和表B的當(dāng)前檢測(cè)指針。設(shè)表C是歸并后的新有序表，變量 k 是它的當(dāng)前存放指針。歸并排序 (Merge Sort)歸并，是將兩個(gè)或兩個(gè)以上的08 21 25 25* 49 62 72 93 16 37

49、 54 l m m+1 ninitListi j08 16 21 25 25* 37 49 54 62 72 93 l nkmergeList當(dāng) i 和 j 都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí)，根據(jù)Ai與Bj的關(guān)鍵字的大小，依次把關(guān)鍵字小的對(duì)象排放到新表Ck中；當(dāng) i 與 j 中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一 個(gè)表中的剩余部分照抄到新表Ck中。08 21 25 25* 49 62 72 93歸并排序算法迭代的歸并排序算法就是利用兩路歸并過(guò)程進(jìn)行排序的。其基本思想是：假設(shè)初始對(duì)象序列有 n 個(gè)對(duì)象，首先把它看成是 n 個(gè)長(zhǎng)度為 1 的有序子序列 (歸并項(xiàng))，先做兩兩歸并，得到 n / 2 個(gè)長(zhǎng)度為 2 的歸

50、并項(xiàng) (如果 n 為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為1)；再做兩兩歸并，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為 n 的有序序列。此算法的關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)均為 (m - l + 1) + (n - m) = n - l + 1。歸并排序算法迭代的歸并排序算法就是利用兩路歸并過(guò)程進(jìn)行排序的兩路歸并算法void Merge(ElemType SR,ElemType TR,int i, int m,int n)for (int j=m+1,k=i;i=m & j=n; +k)if (LQ(SRi.key ,SRj.key) TRk = SRi+;else TRk = SRj+;兩路歸并算法 if

51、(i=m) for (int n1=k,n2=i;n1=n & n2=m;n1+,n2+) TRn1=SRn2;if (j=n) for (int n1=k,n2=j;n1=n & n2=n;n1+,n2+) TRn1=SRn2; if (i=m) void MSort(ElemType SR,ElemType TR1,int s,int t)ElemType TR2MAXSIZE;if (s=t) TR1s=SRs;else int m=(s+t)/2;MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);void MergeS

52、ort(SqList &L)MSort(L.r,L.r,1,L.length);void MSort(ElemType SR,ElemT歸并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16歸并排序算法212525*25*93627208371654算法分析在歸并排序算法中，遞歸深度為O(log2n)，對(duì)象關(guān)鍵字的比較次數(shù)為O(nlog2n)。算法總的時(shí)間復(fù)

53、雜度為O(nlog2n)。歸并排序占用附加存儲(chǔ)較多，需要另外一個(gè)與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個(gè)算法的缺點(diǎn)。歸并排序是一個(gè)穩(wěn)定的排序方法。算法分析在歸并排序算法中，遞歸深度為O(log2n)，對(duì)象關(guān)21 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25 49 21 25* 16 08 25* 16 08 21 25 49 25* 16 08 25* 16 08 21 25 49 16 08 25* 25 49 21 21 25* 16 08 49 25 遞歸回 推21 25 49 25* 16 基數(shù)排序 (Radix Sort)基數(shù)排序

54、是采用“分配”與“收集”的辦法，用對(duì)多關(guān)鍵字進(jìn)行排序的思想實(shí)現(xiàn)對(duì)單關(guān)鍵字進(jìn)行排序的方法。多關(guān)鍵字排序以撲克牌排序?yàn)槔Ｃ繌垞淇伺朴袃蓚€(gè)“關(guān)鍵字”：花色和面值。其有序關(guān)系為： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A如果我們把所有撲克牌排成以下次序： 2, , A, 2, , A, 2, , A, 2, , A基數(shù)排序 (Radix Sort)基數(shù)排序是采用“分配”與“這就是多關(guān)鍵字排序。排序后形成的有序序列叫做詞典有序序列。對(duì)于上例兩關(guān)鍵字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個(gè) n 個(gè)對(duì)象的序列 V0, V

55、1, , Vn-1 ，且每個(gè)對(duì)象Vi 中含有 d 個(gè)關(guān)鍵字如果對(duì)于序列中任意兩個(gè)對(duì)象 Vi 和 Vj ( 0 i j n-1 ) 都滿足：這就是多關(guān)鍵字排序。排序后形成的有序序列叫做詞典有序序列。則稱序列對(duì)關(guān)鍵字 (K1, K2, , Kd) 有序。其中，K1 稱為最高位關(guān)鍵字，Kd 稱為最低位關(guān)鍵字。如果關(guān)鍵字是由多個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)項(xiàng)組，則依據(jù)它進(jìn)行排序時(shí)就需要利用多關(guān)鍵字排序。實(shí)現(xiàn)多關(guān)鍵字排序有兩種常用的方法最高位優(yōu)先MSD (Most Significant Digit first)最低位優(yōu)先LSD (Least Significant Digit first)最高位優(yōu)先法通常是一個(gè)遞

56、歸的過(guò)程： 先根據(jù)最高位關(guān)鍵字K1排序,得到若干對(duì)象組，對(duì)象組中每個(gè)對(duì)象都有相同關(guān)鍵字K1。 則稱序列對(duì)關(guān)鍵字 (K1, K2, , Kd) 有序。其中 再分別對(duì)每組中對(duì)象根據(jù)關(guān)鍵字K2進(jìn)行排序，按K2值的不同，再分成若干個(gè)更小的子組，每個(gè)子組中的對(duì)象具有相同的K1和K2值。 依此重復(fù)，直到對(duì)關(guān)鍵字Kd完成排序?yàn)橹埂?最后，把所有子組中的對(duì)象依次連接起來(lái)，就得到一個(gè)有序的對(duì)象序列。最低位優(yōu)先法首先依據(jù)最低位關(guān)鍵字Kd對(duì)所有對(duì)象進(jìn)行一趟排序，再依據(jù)次低位關(guān)鍵字Kd-1對(duì)上一趟排序的結(jié)果再排序，依次重復(fù)，直到依據(jù)關(guān)鍵字K1最后一趟排序完成，就可以得到一個(gè)有序的序列。使用這種排序方法對(duì)每一個(gè)關(guān)鍵字進(jìn)

57、行排序時(shí)，不需要再分組，而是整個(gè)對(duì)象組都參加排序。 再分別對(duì)每組中對(duì)象根據(jù)關(guān)鍵字K2進(jìn)行排序，按K2值的不同，基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運(yùn)算對(duì)單關(guān)鍵字進(jìn)行排序。在這種方法中，把單關(guān)鍵字 Ki 看成是一個(gè)d元組：其中的每一個(gè)分量 ( 1 j d ) 也可看成是一個(gè)關(guān)鍵字。LSD和MSD方法也可應(yīng)用于對(duì)一個(gè)關(guān)鍵字進(jìn)行的排序。此時(shí)可將單關(guān)鍵字 Ki 看作是一個(gè)子關(guān)鍵字組：鏈?zhǔn)交鶖?shù)排序基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運(yùn)分量 (1 j d ) 有radix種取值，則稱radix為基數(shù)。例如，關(guān)鍵字984可以看成是一個(gè)3元組(9, 8, 4)，每一位有0, 1, , 9等10種取值，基數(shù)radix = 10。關(guān)鍵字data可以看成是一個(gè)4元組(d, a, t, a)，每一位有a, b, , z等26種取值，radix = 26。針對(duì)d元組中的每一位分量，把對(duì)象序列中的所有對(duì)象, 按 的取值，先“分配”到rd個(gè)隊(duì)列中去。然后再按各隊(duì)列的順序，依次把對(duì)象從隊(duì)列中“收集”起來(lái)，這樣所有對(duì)象按取值 排