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

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

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

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

5、向后順移。插入排序的基本方法是：每步將一個待排序的對象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。直接插入排序 (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 時的排序過程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è)待排序的對象個數(shù)為L.length

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

9、)/4分析：若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵字比較次數(shù)和對象移動次數(shù)約為 n2/4。因此，直接插入排序的時間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好折半插入排序 (Binary Insertsort)折半插入排序基本思想是：設(shè)在順序表中有一 個對象序列 V0, V1, , vn-1。其中，v0, V1, , vi-1 是已經(jīng)排好序的對象。在插入 vi 時，利用折半搜索法尋找 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;說明：low 或者 high+1為插入點 穩(wěn)定排序 折半插入排序的算法算法分析二分查找比順序查找快，所以二分插入排序就平均性能來說比直接插入排序要快。它所需要的關(guān)鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對象個數(shù)。在插入第 i 個對象時，需要經(jīng)過 log2

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

12、況要好希爾排序 (Shell Sort)希爾排序方法又稱為“縮小增量”排序。該方法的基本思想是：先將整個待排對象序列按照一定間隔分割成為若干子序列，分別進(jìn)行直接插入排序，然后縮小間隔，對整個對象序列重復(fù)以上的劃分子序列和分別排序工作，直到最后間隔為1，此時整個對象序列已 “基本有序”，進(jìn)行最后一次直接插入排序。希爾排序 (Shell Sort)希爾排序方法又稱為“縮小增21254925*16080 1 2 3 4 52125*i = 10849gap = 32516492516084925*0821252125*16希爾排序過程示例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*開始時 gap（間隔值） 的值較大，子序列中的對象較少，排序速度較快；隨著排序進(jìn)展，gap 值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。21254925*16080 1 希爾排序的算法void ShellSort(SqList &L, int dlta,int t)for (int k=

14、0;kt;+k)ShellInsert(L,dltak);說明：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劃分子序列算法分析對特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)鍵字的比較次數(shù)和對象移動次數(shù)。但想要弄清關(guān)鍵字比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。gap的取法有

15、多種。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。后來Knuth 提出取gap = gap/3 +1。還有人提出都取奇數(shù)為好，也有人提出各gap互質(zhì)為好。其他取法：教材p272 倒數(shù)第二段算法分析對特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)鍵字的比較次Knuth利用大量的實驗統(tǒng)計資料得出，當(dāng) n 很大時，關(guān)鍵字平均比較次數(shù)和對象平均移動次數(shù)大約在 n1.25 到 1.6n1.25 的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。Knuth利用大量的實驗統(tǒng)計資料得出，當(dāng) n 很大時，關(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ū)ο笮蛄兄械膶ο髠€數(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ā)生逆序(即排列順序與排序后的次序正好相反)，則交換之，直到所有對象都排好序為止。起泡排序 (Bubble Sort)交換排序 ( Exchange Sort )起泡排序的基本方21254925*16080 1 2 3 4 52125*i = 149251649chang=10825*chang=1i = 2i = 30816chang=125*25214921251608起泡排序過程示例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)起泡排序特 點至少比較1次，至多比較n-1次；一次確定位置；可實現(xiàn)部分排序穩(wěn)定排序特 點至少比較1次，至多比較n-1次；算法分析在對象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時，此算法只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵字比較，不移動對象。這是最好的情形。最壞的情形是算法執(zhí)行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次關(guān)鍵字比較，執(zhí)行了n-i 次對象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對象移動次數(shù)RMN為：算法分析在對象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時，此算法 起泡排序需要一個附加對象以實現(xiàn)對象值的對換。起泡排序是

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

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

22、uickSort ( RightList ); 將兩個子序列 LeftList 和 RightList 合并為一個序列List; 然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的對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是一個遞歸的算法，其遞歸樹如圖所示。算法partition利用序列第一個對象作為樞軸

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

26、兩個子序列，此時，總的計算時間為：算法分析從快速排序算法的遞歸樹可知，快速排序的趟數(shù)取決于遞歸 T(n) cn + 2 t(n/2 ) / c是一個常數(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的平均計算時間也是o(nlog2n)。實驗結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個。 T(n) cn + 2 t(n/2 ) 快速排序是遞歸的，需要

27、有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 log2(n+1) 。因此，要求存儲開銷為 o(log2n)。在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵字從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經(jīng)過 n-1 趟才能把所有對象定位，而且第 i 趟需要經(jīng)過 n-i 次關(guān)鍵字比較才能找到第 i 個對象的安放位置，總的關(guān)鍵字比較次數(shù)將達(dá)到快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)其排序速度退化到簡單排序的水平，比直接插入排序還慢。占用附加存儲(即棧)將達(dá)到o(n)。若能更合理地選擇基

28、準(zhǔn)對象，使得每次劃分所得的兩個子序列中的對象個數(shù)盡可能地接近，可以加速排序速度，但是由于對象的初始排列次序是隨機的，這個要求很難辦到。有一種改進(jìn)辦法：取每個待排序?qū)ο笮蛄械牡谝粋€對象、最后一個對象和位置接近正中的3個對象，取其關(guān)鍵字居中者作為基準(zhǔn)對象。其排序速度退化到簡單排序的水平，比直接插入排序還慢。占用附加用第一個對象作為基準(zhǔn)對象 快速排序退化的例子 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用第一個對象作為基準(zhǔn)對象 快速排序退化的例子 08用居中關(guān)鍵字對象作為基準(zhǔn)對象快速排序是一種不穩(wěn)定的排序方法。對于 n 較大的平均情況而言，快速排序是“快速”的，但是當(dāng) 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)鍵字對象作為基準(zhǔn)對象快速排序是一種不穩(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相等時，樞軸元素確定了位置i，結(jié)束本次劃分快速排序中的一趟劃分(續(xù))382713499749*5512 選擇排序的基本思想是：每一趟 (例如第 i 趟，i = 1, , n-1) 在后面的

34、n-i+1 個待排序?qū)ο笾羞x出關(guān)鍵字最小的對象, 作為有序?qū)ο笮蛄械牡?i 個對象。待到第 n-1 趟作完，待排序?qū)ο笾皇Ｏ?個，就不用再選了。選擇排序(Selection Sort)基本步驟為：i從1開始，直到n-1，進(jìn)行n-1趟排序，第i 趟的排序過程為： 在一組對象rirn (i=1,2,n-1)中選擇具有最小關(guān)鍵字的對象；并和第 i 個對象進(jìn)行交換；簡單選擇排序 (Simple Selection Sort) 選擇排序的基本思想是：每一趟 (例如第 i 趟，i 簡單選擇排序的算法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; 簡單選擇排序的算法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、無交換最小者 25無交換25211608各趟排序后的結(jié)果4925*0 1 20 1 2 3 4 549160825*49210825*2521i =2時選擇排序的過程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與對象的初始排列無關(guān)。第 i 趟選擇具有最小關(guān)鍵字對象所需的比較次數(shù)總是 n-i-1 次，此處假定整個待排序?qū)ο笮蛄杏?n 個對象。因此，總的關(guān)鍵字比較次數(shù)為49250825*162

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

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

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

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

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

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

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

45、Heap Sort)給定一組關(guān)鍵字，初始態(tài)存儲時是建立初始的最大堆212525*491608123456i212525*164908136542i21 25 49 25* 16 08初始關(guān)鍵字集合21 25 49 25* 16 08i = 3 時的局部調(diào)整建立初始的最大堆212525*491608123456i21212525*491608123456i492525*16210813654221 25 49 25* 16 0849 25 21 25* 16 08i = 1 時的局部調(diào)整形成大頂堆i = 2 時的局部調(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 個結(jié)點，且 2k-1 n 2k，則對應(yīng)的完全二叉樹有 k 層。在第 i 層上的結(jié)點數(shù) 2i-1 (i = 1, , k)。在第一個形成初始堆的for循環(huán)中對每一個非

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

48、(歸并排序 (Merge Sort)歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。對象序列 initList 中有兩個有序表Vl Vm和Vm+1 Vn。它們可歸并成一個有序表，存于另一對象序列 mergedList 的Vl Vn中。這種歸并方法稱為2-路歸并 (2-way merging)。其基本思想是：設(shè)兩個有序表A和B的對象個數(shù)(表長)分別為 al 和 bl，變量 i 和 j 分別是表A和表B的當(dāng)前檢測指針。設(shè)表C是歸并后的新有序表，變量 k 是它的當(dāng)前存放指針。歸并排序 (Merge Sort)歸并，是將兩個或兩個以上的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 都在兩個表的表長內(nèi)變化時，根據(jù)Ai與Bj的關(guān)鍵字的大小，依次把關(guān)鍵字小的對象排放到新表Ck中；當(dāng) i 與 j 中有一個已經(jīng)超出表長時，將另一 個表中的剩余部分照抄到新表Ck中。08 21 25 25* 49 62 72 93歸并排序算法迭代的歸并排序算法就是利用兩路歸并過程進(jìn)行排序的。其基本思想是：假設(shè)初始對象序列有 n 個對象，首先把它看成是 n 個長度為 1 的有序子序列 (歸并項)，先做兩兩歸并，得到 n / 2 個長度為 2 的歸

50、并項 (如果 n 為奇數(shù)，則最后一個有序子序列的長度為1)；再做兩兩歸并，如此重復(fù)，最后得到一個長度為 n 的有序序列。此算法的關(guān)鍵字比較次數(shù)和對象移動次數(shù)均為 (m - l + 1) + (n - m) = n - l + 1。歸并排序算法迭代的歸并排序算法就是利用兩路歸并過程進(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)，對象關(guān)鍵字的比較次數(shù)為O(nlog2n)。算法總的時間復(fù)

53、雜度為O(nlog2n)。歸并排序占用附加存儲較多，需要另外一個與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。歸并排序是一個穩(wěn)定的排序方法。算法分析在歸并排序算法中，遞歸深度為O(log2n)，對象關(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、是采用“分配”與“收集”的辦法，用對多關(guān)鍵字進(jìn)行排序的思想實現(xiàn)對單關(guān)鍵字進(jìn)行排序的方法。多關(guān)鍵字排序以撲克牌排序為例。每張撲克牌有兩個“關(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)鍵字排序。排序后形成的有序序列叫做詞典有序序列。對于上例兩關(guān)鍵字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個 n 個對象的序列 V0, V

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

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

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