常用排序算法精品課件

1、常用排序算法第1頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三內(nèi)部排序: 指的是待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程。外部排序: 指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。內(nèi)部排序與外部排序第2頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三假設(shè) Ki = Kj ，且排序前序列中 Ri 領(lǐng)先于 Rj ；若在排序后的序列中 Ri 仍領(lǐng)先于 Rj ，則稱排序方法是穩(wěn)定的。若在排序后的序列中 Rj 仍領(lǐng)先于 Ri ，則稱排序方法是不穩(wěn)定的。例，序列 3 15 8 8 6 9若排序后得 3 6 8 8 9 15穩(wěn)定

2、的若排序后得 3 6 8 8 9 15不穩(wěn)定的排序衡量指標(biāo)穩(wěn)定性第3頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三排序衡量指標(biāo)時間復(fù)雜度排序過程主要是對記錄的排序碼進(jìn)行比較和記錄的移動過程。排序的時間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動次數(shù)來衡量。當(dāng)一種排序方法使排序過程在最壞或平均情況下所進(jìn)行的比較和移動次數(shù)越少，則認(rèn)為該方法的時間復(fù)雜性就越好，分析一種排序方法，不僅要分析它的時間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性等。第4頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三按照排序過程中所依據(jù)的原則的不同可以分類為: 插入排序 交換排序(快速排序) 選擇排序 歸并

3、排序 基數(shù)排序 二叉排序樹排序內(nèi)部排序第5頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三思想: 利用有序表的插入操作進(jìn)行排序有序表的插入: 將一個記錄插入到已排好序的有序表中，從而得到一個新的有序表。例，序列 13 27 38 65 76 97 插入 4913 27 38 49 65 76 97插入排序直接插入排序第6頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三直接插入排序算法描述例，序列 49 38 65 97 76 13 27 初始，S = 49 ； 38 49 初始，令第 1 個元素作為初始有序表；依次插入第 2 , 3 , , k 個元素構(gòu)造新的有序表；直至最后一

4、個元素； 38 49 65 38 49 65 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要應(yīng)用比較和移動兩種操作。第7頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三void Insert(ArrNode * pnum) for (i = 1; i 0 & tmp.key pnumj - 1.key; j-) pnumj = pnumj - 1;pnumj = tmp;直接插入排序算法描述第8頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三時間復(fù)雜度分析：外層循環(huán)要進(jìn)行n-1次插入，每次插

5、入最少比較一次（正序），移動兩次；最多比較i次，移動i2次（逆序）（i=1,2,n-1）。Cmin=n-1 M min=2（n-1）Cmax=1+2+n-1=（n2-n）/2 M max=3+4+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4 M max=（n2+7n-8）/4因此，直接插入排序的時間復(fù)雜度為O（n2）。直接插入算法的元素移動是順序的，該方法是穩(wěn)定的。直接插入排序的效率分析第9頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三由于直接插入排序算法利用了有序表的插入操作，故順序查找操作可以替換為折半查找操作。例，序列 49 38 65 97 76 13 27

6、設(shè)已形成有序表 38 49 65 97 76 插入元素 13折半插入排序第10頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三void BinaryInsertSort( ArrNode *pnum ，int L) for(int i=1; iL; i+) /共進(jìn)行n-1次插入 int left=0,right=i-1; temp=pnumi; while(left=right) int middle=(left+right)/2; /取中點(diǎn) if(temp=left;j-) pnumj+1=pnumj; /元素后移空出插入位 pnumleft=temp; 折半插入排序算法描述第11頁

7、，共56頁，2022年，5月20日，5點(diǎn)41分，星期三折半插入效率分析二分插入算法與直接插入算法相比，需要輔助空間與直接插入排序基本一致；時間上，前者的比較次數(shù)比直接插入查找的最壞情況好，最好的情況壞，兩種方法的元素的移動次數(shù)相同，因此二分插入排序的時間復(fù)雜度仍為O(n2)。二分插入算法與直接插入算法的元素移動一樣是順序的，因此該方法也是穩(wěn)定的。第12頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三直接插入排序1. 若待排序記錄序列按關(guān)鍵字基本有序，則排序效率可大大提高；2. 待排序記錄總數(shù)越少，排序效率越高；希爾(shell)排序第13頁，共56頁，2022年，5月20日，5點(diǎn)41分

8、，星期三將待排序記錄序列分割成為若干子序列分別進(jìn)行直接插入排序；待整個序列中的記錄基本有序后，再全體進(jìn)行一次直接插入排序。例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序49 13 1938 2765 4897 5576 413 19 4927 3848 6555 974 76希爾(shell)排序算法思想第14頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三第二趟排序13 19 4927 3848 6555 974 7613 55 38 7627 4 65 4948 19 9713 38 55 764 27 49 6519 48 97第三趟排序4

9、13 19 27 38 48 49 55 65 76 97第15頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三void Hill(ArrNode * pnum, int increment) /初始值為Lens printf(nThe Hill Sort list is n); for (h = increment; h 0; h = h / 2) for (j = h; j = 0 & t.key pnumk.key); k = k - h)*(pnum + k + h) = *(pnum + k); *(pnum + k + h) = t; 希爾(shell)排序算法思想第16頁

10、，共56頁，2022年，5月20日，5點(diǎn)41分，星期三希爾排序效率分析希爾排序的時間復(fù)雜性在O（nlog2n）和O（n2 ）之間，大致為O（n1.3）。第17頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三思想: 通過不斷比較相鄰元素大小，進(jìn)行交換來實(shí)現(xiàn)排序。首先將第一個元素與第二個元素比較大小，若為逆序，則交換；然后比較第二個元素與第三個元素的大小，若為逆序，則交換；. . .直至比較第 n-1 個元素與第 n 個元素的大小，若為逆序，則交換；第一趟排序:結(jié)果:關(guān)鍵字最大的記錄被交換至最后一個元素位置上。交換排序冒泡排序第18頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三例

11、，序列 49 38 76 13 2749 38 76 13 2738 49 13 27 38 4913 7627 76初始第一趟排序后最大值13 4927 49次大值第二趟排序后38 13 2713 2713 3827 38第三趟排序后第四趟排序后第19頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三void Bubble(ArrNode * pnum) for (i = 0; i i; j-) if (pnumj - 1.key pnumj.key) tmp = pnumj;pnumj = pnumj - 1;pnumj - 1 = tmp; 冒泡排序的算法實(shí)現(xiàn)第20頁，共56頁，2

12、022年，5月20日，5點(diǎn)41分，星期三從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進(jìn)行一趟排序，比較次數(shù)為（n-1）次，移動元素次數(shù)為0；若待排序的元素為逆序，則需進(jìn)行n-1趟排序，比較次數(shù)為(n2-n)/2，移動次數(shù)為3(n2-n )/2，因此冒泡排序算法的時間復(fù)雜度為O（n2）。由于其中的元素移動較多，所以屬于內(nèi)排序中速度較慢的一種。因?yàn)槊芭菖判蛩惴ㄖ贿M(jìn)行元素間的順序移動，所以是一個穩(wěn)定的算法。冒泡排序的效率分析第21頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三冒泡排序的一種改進(jìn)算法。思想:以首記錄作為軸記錄，從前、后雙向掃描序列，通過交換，實(shí)現(xiàn)大值記錄后移，小值記

13、錄前移，最終將軸記錄安置在一個適當(dāng)?shù)奈恢谩?小值記錄在前、大值記錄在后)軸記錄將原序列分割成兩部分，依次對前后兩部分重新設(shè)定軸記錄，繼而分別再進(jìn)行快速排序。直至整個序列有序。交換排序快速排序第22頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三快速排序算法思想第23頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三38 65 97 76 13 27 4949lowhighpivot = 49 0 1 2 3 4 5 6 7high38 65 97 76 13 4927low27 38 97 76 13 4965high27 38 97 76 65 4913low27 38 13

14、76 65 4997high49快速排序算法思想第24頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三 void Quick(ArrNode * pnum, int low, int high) int i = low, j = high; ArrNode key; key = pnumi; if (i = j) return; while (i j) while (i key.key) j-; if (i j) pnumi = pnumj; i+;快速排序算法思想第25頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三while (i j & pnumi.key key.key

15、) i+;if (i j) pnumj = pnumi; j-; pnumi = key; printf(n); Quick(pnum, low, j - 1); Quick(pnum, j + 1, high);快排序-分割過程偽碼第26頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三快速排序的效率分析若快速排序出現(xiàn)最好的情形（左、右子區(qū)間的長度大致相等），則結(jié)點(diǎn)數(shù)n與二叉樹深度h應(yīng)滿足log2nhlog2n+1 ，所以總的比較次數(shù)不會超過(n+1) log2n。因此，快速排序的最好時間復(fù)雜度應(yīng)為O（nlog2n）。而且在理論上已經(jīng)證明，快速排序的平均時間復(fù)雜度也為O（nlog2n）

16、。若快速排序出現(xiàn)最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，得到的非空子區(qū)間包含有n-i個(i代表二叉樹的層數(shù)（1in）元素，每層劃分需要比較n-i+2次，所以總的比較次數(shù)為（n2+3n-4）/2。因此，快速排序的最壞時間復(fù)雜度為O(n2)?？焖倥判蛩加玫妮o助空間為棧的深度，故最好的空間復(fù)雜度為O（log2n），最壞的空間復(fù)雜度為O(n)?？焖倥判蚴且环N不穩(wěn)定的排序方法。 第27頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三思想: 每一趟都選出一個最大或最小的元素，并放在合適當(dāng)?shù)奈恢谩?簡單選擇排序 樹形選擇排序 堆排序選擇排序第28頁，

17、共56頁，2022年，5月20日，5點(diǎn)41分，星期三思想: 第 1 趟選擇:從 1n 個記錄中選擇關(guān)鍵字最小的記錄，并和第 1 個記錄交換。第 2 趟選擇:從 2n 個記錄中選擇關(guān)鍵字最小的記錄，并和第 2 個記錄交換。第n-1趟選擇:從 n-1n 個記錄中選擇關(guān)鍵字最小的記錄，并和第 n-1 個記錄交換。. . .簡單選擇排序第29頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三例，序列 49 38 97 65 76第 1 趟選擇:min38 49 97 65 76第 2 趟選擇:min38 49 97 65 76第 3 趟選擇:min38 49 65 97 76第 4 趟選擇:mi

18、n38 49 65 76 97第30頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三void Choise(ArrNode * pnum)for (i = 0; i Len - 1; i+) minLoc = i;for (j = i + 1; j pnumj.key)minLoc = j;if (i != minLoc) tmp = pnumminLoc; pnumminLoc = pnumi; pnumi = tmp;直接選擇排序的偽碼描述第31頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三選擇排序的主要操作是進(jìn)行關(guān)鍵字間的比較。在 n 個關(guān)鍵字中選出最小值，至少需要 n

19、-1 次比較。在剩余的 n-1 個關(guān)鍵字中選出最小值，至少需要 n-2 次比較？如果能利用前 n-1 次比較所得信息，可以減少后面選擇的比較次數(shù)。第32頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三例，序列 49 38 65 97 76 13 27 50第一趟選擇133813493865977613275038651327最小值樹形選擇排序第33頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三第二趟選擇2738274938659776275038657627次小值第三趟選擇38385049386597765038657650次次小值4938659776132750493865

20、97762750缺點(diǎn): 需要大量輔助存儲空間，最大值多余比較第34頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三堆: 一棵完全二叉樹，任一個非終端結(jié)點(diǎn)的值均小于等于(或大于等于)其左、右子樹結(jié)點(diǎn)的值。1285473053362491963811 98324小頂堆大頂堆堆排序第35頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三2. 把這棵普通的完全二叉樹改造成堆，便可獲取最小值 ；堆排序算法思想:3. 輸出最小值 ；4. 刪除根結(jié)點(diǎn)，繼續(xù)改造剩余樹成堆，便可獲取次小值 ；5. 輸出次小值 ；6. 重復(fù)改造，輸出次次小值、次次次小值，直至所有結(jié)點(diǎn)均輸出，便得到一個排序 。1.

21、將序列構(gòu)造成一棵完全二叉樹 ；盡可能減少存儲空間開銷，讓待排序的記錄僅占最小的空間（1個）第36頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三例，序列 49 38 65 97 76 13 27 501. 按順序依次構(gòu)造成完全二叉樹的結(jié)點(diǎn)；49386597761327502. 把完全二叉樹改造成堆；從下向上，父子交換；50971365134949273. 取得最小值 134. 刪除 13 ，重新改造成新堆；1397279797495. 取得次小值 27；6. 刪除 27 ，重新改造成新堆；9727973897507. 取得次次小值 38；第37頁，共56頁，2022年，5月20日，5點(diǎn)

22、41分，星期三堆排序算法思想:void Heap(ArrNode * pnum, int L) int i, k; ArrNode t; for (i = L / 2 - 1; i = 0; i-)createheap(pnum, i, L);/The basic heap for (k = L - 1; k 0; k-) t = *pnum;*pnum = *(pnum + k);*(pnum + k) = t;createheap(pnum, 0, k);第38頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三堆排序算法思想:void createheap(ArrNode * pnu

23、m, int i, int nLens) int nChild, nTemp; for (nTemp = pnumi.key; 2 * i + 1 pnumnChild.key) +nChild;if (nTemp pnumnChild.key) pnumi = pnumnChild;else break; pnumi.key = nTemp;第39頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三歸并排序（Merge Sort)歸并-合并兩個有序的序列假設(shè)有兩個已排序好的序列A（長度為n1），B（長度為n2），將它們合并為一個有序的序列C（長度為n=n1+n2)方法：把A，B兩個序列的

24、最小元素進(jìn)行比較，把其中較小的元素作為C的第一個元素；在A，B剩余的元素中繼續(xù)挑最小的元素進(jìn)行比較，確定C的第二個元素，依次類推，就可以完成對A和B的歸并， 其復(fù)雜度為O(n)第40頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三歸并-合并兩個有序的序列A: 1 3 8 9 11B: 2 5 7 10 13歸并排序（Merge Sort)C: 1 2 3 5 7 8 9 10 11 13第41頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三void merge(T A, int Alen, T B, int Blen, T C) int i=0,j=0,k=0; while(i

25、 Alen & j Blen) if(Ai Bj) Ck+ = Ai+; else Ck+ = Bj+;while(i Alen)Ck+ = Ai+; while(j Blen)Ck+ = Bj+;歸并排序（Merge Sort)第42頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三歸并-合并一個序列中的兩個有序的數(shù)據(jù)段void merge(T A, int l, int m, int h) int i=l,j=m+1,k=0; T *C = new Th-l+1; while(i = m & j = h) if(Ai Aj) Ck+ = Ai+; else Ck+ = Aj+; wh

26、ile(i =m) Ck+ = Ai+;while(j =h) Ck+ = Bj+; for(k=0;kh-l+1;k+) Ai+k=Ck; /將排好序的元素寫回A數(shù)組 delete C;第43頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三歸并排序（Merge Sort)歸并排序歸并排序是一個分治遞歸算法遞歸基礎(chǔ)：若序列只有一個元素，則它是有序的，不執(zhí)行任何操作遞歸步驟：先把序列劃分成長度基本相等的兩個序列對每個子序列遞歸排序把排好序的子序列歸并成最后的結(jié)果第44頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三歸并排序（Merge Sort)初始序列： 8，4，5，6，2，1

27、，7，3分解： 8 4 5 6 2 1 7 3歸并： 4，8 5，6 1，2 3，7歸并： 4，5，6， 8 1，2，3，7歸并： 1，2，3， 4，5，6，7，8分解： 8，4，5，6 2，1，7，3分解： 8，4 5，6 2，1 7，3第45頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三歸并排序（Merge Sort)算法分析最壞情況：歸并排序是一個遞歸算法，所以很容易得到算法計(jì)算量的遞推公式 所以算法最壞情況的復(fù)雜度為算法需要 的輔助空間第46頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三以比較為基礎(chǔ)的排序算法的下界根據(jù)數(shù)據(jù)結(jié)構(gòu)中關(guān)于二叉樹的性質(zhì)，有：最壞情況：任何排

28、序算法至少要做次比較平均情況：任何排序算法的平均比較次數(shù)的下界是結(jié)論：具有O(nlgn)復(fù)雜度的比較排序算法在漸進(jìn)意義下是最優(yōu)的算法歸并排序（Merge Sort)第47頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序的方法 1. 多關(guān)鍵字排序撲克牌問題 :已知撲克牌中52張牌面的次序關(guān)系定義為: 花色:面值:2 3 A. . .例， 8 3花色優(yōu)先級更高，為主關(guān)鍵字，面值為次關(guān)鍵字基數(shù)排序第48頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三2. 52張牌排序方法 :最高位優(yōu)先法(MSDF) :先按不同“花色”分成有次序的4堆，

29、每一堆均具有相同的花色；然后分別對每一堆按“面值”大小整理有序。最低位優(yōu)先法(LSDF) :先按不同“面值”分成 13 堆 ；然后將這 13 堆牌自小至大疊在一起( 2 , 3 , . . . , A ) ；然后將這付牌整個顛倒過來再重新按不同的“花色”分成 4 堆 ；最后將這 4 堆牌按自小至大的次序合在一起 。收集分配第49頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三3. 基數(shù)排序基數(shù)排序就是借助于“分配”和“收集”兩種操作實(shí)現(xiàn)對單邏輯關(guān)鍵字的排序。首先，單邏輯關(guān)鍵字通常都可以看作是由若干關(guān)鍵字復(fù)合而成。其次，利用 LSDF 法實(shí)現(xiàn)對若干關(guān)鍵字的排序。例，若關(guān)鍵字是數(shù)值，且值域?yàn)?0K999 ，故可以將 K 看作是由 3 個關(guān)鍵字 K0 K1 K2 組成，例，603是由 6 0 3 組成。第50頁，共56頁，2022年，5月20日，5點(diǎn)41分，星期三例，序列 278 109 063 930 589 184 505 269 008 083第一趟分配0 1 2 3 4