第十章排序

1、第十章 排序,⒈教學(xué)內(nèi)容 10.1        基本概念 10.2        插入排序 10.3        交換排序 10.4 &#

2、160;      選擇排序 10.5        二路歸并排序 10.6        基數(shù)排序 10.7       

3、外排序⒉教學(xué)目的及要求⑴領(lǐng)會排序的基本思想和基本概念；⑵理解并掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟、算法及時空效率分析；⑶了解外排序的定義和基本方法。,3、教學(xué)重點⑴排序基本概念及內(nèi)排序和外排序、穩(wěn)定排序和非穩(wěn) 定排序的區(qū)別；⑵插入排序的基本思想、基本步驟和算法；⑶冒泡排序的基本思想、基本步驟、算法和算法分析；⑷快速排序的基本思想、基本步驟和算法；⑸直接選擇排序

4、的基本思想、基本步驟、算法和算法 分析；⑹堆排序的基本思想、基本步驟和算法；⑺歸并排序的思想；⑻兩個有序文件合并的方法和算法；⑼二路歸并排序的算法和時空性能 4、教學(xué)難點 ⑴快速排序算法； ⑵堆排序方法,10.1 基本概念,排序(Sorting)是計算機程序設(shè)計中的一種重要操作，其功能是對一個數(shù)據(jù)元素集合或序列重新排列成一個按數(shù)據(jù)元素某個項值有序的序列。作為排序依據(jù)的數(shù)據(jù)項稱為“排序碼”，也即數(shù)據(jù)元素的關(guān)鍵

5、碼。為了便于查找，通常希望計算機中的數(shù)據(jù)表是按關(guān)鍵碼有序的。如有序表的折半查找，查找效率較高。還有，二叉排序樹、B-樹和B+樹的構(gòu)造過程就是一個排序過程。若關(guān)鍵碼是主關(guān)鍵碼，則對于任意待排序序列，經(jīng)排序后得到的結(jié)果是唯一的；若關(guān)鍵碼是次關(guān)鍵碼，排序結(jié)果可能不唯一，這是因為具有相同關(guān)鍵碼的數(shù)據(jù)元素，這些元素在排序結(jié)果中，它們之間的的位置關(guān)系與排序前不能保持。,若對任意的數(shù)據(jù)元素序列，使用某個排序方法，對它按關(guān)鍵碼進行排序：若相同關(guān)鍵碼元素

6、間的位置關(guān)系，排序前與排序后保持一致，稱此排序方法是穩(wěn)定的；而不能保持一致的排序方法則稱為不穩(wěn)定的。 排序分為兩類：內(nèi)排序和外排序。 內(nèi)排序：指待排序列完全存放在內(nèi)存中所進行的排序過程，適合不太大的元素序列。 外排序：指排序過程中還需訪問外存儲器，足夠大的元素序列，因不能完全放入內(nèi)存，只能使用外排序。,10.2 插入排序,10.2.1 直接插入排序 設(shè)有n個記錄，存放在數(shù)組r

7、中，重新安排記錄在數(shù)組中的存放順序，使得按關(guān)鍵碼有序。即r[1].key≤r[2].key≤……≤r[n].key 先來看看向有序表中插入一個記錄的方法： 設(shè)１<ｊ≤ｎ，r[1].key≤r[2].key≤……≤r[j-1].key，將r[j]插入，重新安排存放順序，使得r[1].key≤r[2].key≤……≤r[j].key，得到新的有序表，記錄數(shù)增１。,【算法10.1】 ① r[0]=

8、r[j]； //r[j]送r[0]中，使r[j]為待插入記錄空位 i=j-1； //從第i個記錄向前測試插入位置，用r[0]為輔助單元， 可免去測試i<1。 ② 若r[0].key≥r[i].key，轉(zhuǎn)④。 //插入位置確定 ③ 若r[0].key < r[i].key時， r[i+1]=r[i]；i=i-1；轉(zhuǎn)②。 //調(diào)整待插入

9、位置 ④ r[i+1]=r[0]；結(jié)束。 //存放待插入記錄,【例10.1】向有序表中插入一個記錄的過程如下： r[1] r[2] r[3] r[4] r[5] 存儲單元 2 10 18 25 9 將r[5]插入四個記錄的有序表中，j=5r[0]=r[j]；i=j-1；

10、 初始化，設(shè)置待插入位置 2 10 18 25 □ r[i+1]為待插入位置i=4，r[0] < r[i]，r[i+1]=r[i]；i--； 調(diào)整待插入位置 2 10 18 □ 25 i=3，r[0] < r[i]，r[i+1]=r[i]；i-

11、-； 調(diào)整待插入位置 2 10 □ 18 25 i=2，r[0] < r[i]，r[i+1]=r[i]；i--； 調(diào)整待插入位置 2 □ 10 18 25 i=1，r[0] ≥r[i]，r[i+1]=r[0]； 插入位置確定，向空位填入插

12、入記錄 2 9 10 18 25 向有序表中插入一個記錄的過程結(jié)束,直接插入排序方法：僅有一個記錄的表總是有序的，因此，對n個記錄的表，可從第二個記錄開始直到第n個記錄，逐個向有序表中進行插入操作，從而得到n個記錄按關(guān)鍵碼有序的表。,【算法10.2】void InsertSort(S_TBL &p){for(i=2；ilength；i++)if(p-

13、>elem[i].key elem[i-1].key) /*小于時，需將elem[i]插入有序表*/{p->elem[0]=p->elem[i]； /*為統(tǒng)一算法設(shè)置監(jiān)測*/for(j=i-1；p->elem[0].key elem[j].key；j--)p->elem[j+1]=p->elem[j]； /*記錄后移*/p->elem[j+1]=p-&g

14、t;elem[0]；/*插入到正確位置*/}},【效率分析】 空間效率：僅用了一個輔助單元。 時間效率：向有序表中逐個插入記錄的操作，進行了n-1趟，每趟操作分為比較關(guān)鍵碼和移動記錄，而比較的次數(shù)和移動記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列。 最好情況下：即待排序列已按關(guān)鍵碼有序，每趟操作只需1次比較2次移動。 總比較次數(shù)=n-1次

15、 總移動次數(shù)=2(n-1)次 最壞情況下：即第j趟操作，插入記錄需要同前面的j個記錄進行j次關(guān)鍵碼比較，移動記錄的次數(shù)為j+2次。,平均情況下：即第j趟操作，插入記錄大約同前面的j/2個記錄進行關(guān)鍵碼比較，移動記錄的次數(shù)為j/2+2次。,由此，直接插入排序的時間復(fù)雜度為O(n2)。是一個穩(wěn)定的排序方法。,10.2.1 折半插入排序 直接插入排序的基本操作是向有序表中插入一個記錄，插入位置的

16、確定通過對有序表中記錄按關(guān)鍵碼逐個比較得到的。平均情況下總比較次數(shù)約為n2/4。既然是在有序表中確定插入位置，可以不斷二分有序表來確定插入位置，即一次比較，通過待插入記錄與有序表居中的記錄按關(guān)鍵碼比較，將有序表一分為二，下次比較在其中一個有序子表中進行，將子表又一分為二。這樣繼續(xù)下去，直到要比較的子表中只有一個記錄時，比較一次便確定了插入位置。,二分判定有序表插入位置方法：① low=1；high=j-1；r[0]=r[j]；

17、// 有序表長度為j-1，第j個記錄為待插入記錄 //設(shè)置有序表區(qū)間，待插入記錄送輔助單元② 若low>high，得到插入位置，轉(zhuǎn)⑤③ low≤high，m=(low+high)/2； // 取表的中點，并將表一分為二，確定待插入?yún)^(qū)間*/④ 若r[0].key<r[m].key，high=m-1； //插入位置在低半?yún)^(qū) 否則，low=m+1； // 插入位置在

18、高半?yún)^(qū)轉(zhuǎn)②⑤ high+1即為待插入位置，從j-1到high+1的記錄，逐個后移，r[high+1]=r[0]；放置待插入記錄。,【算法10.3】void InsertSort(S_TBL *s){/* 對順序表s作折半插入排序 */for(i=2；ilength；i++){s->elem[0]=s->elem[i]； /* 保存待插入元素 */low=i；high=i-1； /* 設(shè)置初始區(qū)間

19、*/while(lowelem[0].key>s->elem[mid].key)low=mid+1； /* 插入位置在高半?yún)^(qū)中 */else high=mid-1； /* 插入位置在低半?yún)^(qū)中 */}/* while */for(j=i-1；j>=high+1；j--) /* high+1為插入位置 */s->elem[j+1]=s->elem[j]； /* 后移元素

20、，留出插入空位 */s->elem[high+1]=s->elem[0]； /* 將元素插入 */}/* for */}/* InsertSort */,【時間效率】 確定插入位置所進行的折半查找，關(guān)鍵碼的比較次數(shù)至多為 ，次，移動記錄的次數(shù)和直接插入排序相同，故時間復(fù)雜度仍為O(n2)。是一個穩(wěn)定的排序方法。10.2.3表插入排序 直接插入排序

21、、折半插入排序均要大量移動記錄，時間開銷大。若要不移動記錄完成排序，需要改變存儲結(jié)構(gòu)，進行表插入排序。所謂表插入排序，就是通過鏈接指針，按關(guān)鍵碼的大小，實現(xiàn)從小到大的鏈接過程，為此需增設(shè)一個指針項。操作方法與直接插入排序類似，所不同的是直接插入排序要移動記錄，而表插入排序是修改鏈接指針。用靜態(tài)鏈表來說明。,#define SIZE 200typedef struct{ ElemType elem；

22、 /*元素類型*/ int next； /*指針項*/ }NodeType； /*表結(jié)點類型*/typedef struct{ NodeType r[SIZE]； /*靜態(tài)鏈表*/ int length； /*表長度*/ }L_TBL；

23、 /*靜態(tài)鏈表類型*/ 假設(shè)數(shù)據(jù)元素已存儲在鏈表中，且0號單元作為頭結(jié)點，不移動記錄而只是改變鏈指針域，將記錄按關(guān)鍵碼建為一個有序鏈表。首先，設(shè)置空的循環(huán)鏈表，即頭結(jié)點指針域置0，并在頭結(jié)點數(shù)據(jù)域中存放比所有記錄關(guān)鍵碼都大的整數(shù)。接下來，逐個結(jié)點向鏈表中插入即可。,【例10.2】表插入排序示例,初始狀態(tài),key域,next域,i=1,i=2,i=3,key域,next域,key域,next域,key域,next域,i=4

24、,i=7,i=8,key域,next域,key域,next域,key域,next域,i=5,key域,next域,i=6,key域,next域,表插入排序得到一個有序的鏈表，查找則只能進行順序查找，而不能進行隨機查找，如折半查找。為此，還需要對記錄進行重排。 重排記錄方法：按鏈表順序掃描各結(jié)點，將第i個結(jié)點中的數(shù)據(jù)元素調(diào)整到數(shù)組的第i個分量數(shù)據(jù)域。因為第i個結(jié)點可能是數(shù)組的第j個分量，數(shù)據(jù)元素調(diào)整僅需將兩個數(shù)組分量中數(shù)據(jù)元

25、素交換即可，但為了能對所有數(shù)據(jù)元素進行正常調(diào)整，指針域也需處理。,【算法10.3】1. j=l->r[0].next；i=1； //指向第一個記錄位置，從第一個記錄開始調(diào)整2. 若i=l->length時，調(diào)整結(jié)束；否則，a. 若i=j，j=l->r[j].next；i++；轉(zhuǎn)(2) //數(shù)據(jù)元素應(yīng)在這分量中，不用調(diào)整，處理下一個結(jié)點b. 若j>i，l->r[i].eleml->r[j

26、].elem； //交換數(shù)據(jù)元素 p=l->r[j].next； // 保存下一個結(jié)點地址 l->r[j].next=l->[i].next；l->[i].next=j； // 保持后續(xù)鏈表不被中斷 j=p；i++；轉(zhuǎn)(2) // 指向下一個處理的結(jié)點c. 若jr[j].next；//j分量中原記錄已移走，沿j的指針域找尋原記錄的

27、位置 轉(zhuǎn)到(a),【例10.3】對表插入排序進行重排示例,初始狀態(tài),key域,next域,i=1,i=2,i=3,key域,next域,key域,next域,key域,next域,j=6,j=7,i=(2),7,i=4,i=7,key域,next域,key域,next域,i=5,key域,next域,i=6,key域,next域,j=(1),6,j=8,j=(3),7,j=(5),8,【時效分析】 表插入排序的基本操作是將

28、一個記錄插入到已排好序的有序鏈表中，設(shè)有序表長度為i，則需要比較至多i+1次，修改指針兩次。因此，總比較次數(shù)與直接插入排序相同，修改指針總次數(shù)為2n次。所以，時間復(fù)雜度仍為O(n2)。,10.2.3 希爾排序(Shell’s Sort) 希爾排序又稱縮小增量排序，是1959年由D.L.Shell提出來的，較前述幾種插入排序方法有較大的改進。 直接插入排序算法簡單，在n值較小時，效率比較高，在n值很大時，若序列

29、按關(guān)鍵碼基本有序，效率依然較高，其時間效率可提高到O(n)。希爾排序即是從這兩點出發(fā)，給出插入排序的改進方法。 希爾排序方法： 1. 選擇一個步長序列t1，t2，…，tk，其中ti>tj，tk=1； 2. 按步長序列個數(shù)k，對序列進行k趟排序； 3. 每趟排序，根據(jù)對應(yīng)的步長ti，將待排序列分割成若干長度為m的子序列，分別對各子表進行直接插入排序。僅步長因子為1時，整個序列作為一個

30、表來處理，表長度即為整個序列的長度。,【例10.4】待排序列為 39，80，76，41，13，29，50，78，30，11，100，7，41，86。步長因子分別取5、3、1，則排序過程如下：,P=5,,,,,,,,,,,,,,,,,,,,,子序列分別為{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}。,第一趟排序結(jié)果：,P=3,,,,,,,,,,,,,,,,,,,子序列分別為{29

31、，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。第二趟排序結(jié)果：,P=1,此時，序列基本“有序”，對其進行直接插入排序，得到最終結(jié)果： ：,【算法10.5】void ShellInsert(S_TBL &p，int dk){/*一趟增量為dk的插入排序，dk為步長因子*/for(i=dk+1；ilength；i++)if(p->elem[i].key elem

32、[i-dk].key) /*小于時，需elem[i]將插入有序表*/{p->elem[0]=p->elem[i]； /*為統(tǒng)一算法設(shè)置監(jiān)測*/for(j=i-dk；j>0&&p->elem[0].key elem[j].key；j=j-dk)p->elem[j+dk]=p->elem[j]； /*記錄后移*/p->elem[j+

33、dk]=p->elem[0]； /*插入到正確位置*/}},void ShellSort(S_TBL *p，int dlta[]，int t){/*按增量序列dlta[0，1…，t-1]對順序表*p作希爾排序*/for(k=0；k<t；k++)ShellInsert(p，dlta[k])； /*一趟增量為dlta[k]的插入排序*/}【時效分析】 希爾排序時效分析很難，關(guān)鍵碼

34、的比較次數(shù)與記錄移動次數(shù)依賴于步長因子序列的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出選取最好的步長因子序列的方法。步長因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：步長因子中除1外沒有公因子，且最后一個步長因子必須為1。希爾排序方法是一個不穩(wěn)定的排序方法。,10.3 交換排序,交換排序主要是通過兩兩比較待排記錄的關(guān)鍵碼，若發(fā)生與排序要求相逆，則交換之。 10.3.1冒泡排序(

35、Bubble Sort) 先來看看待排序列一趟冒泡的過程：設(shè)1<j≤n，r[1],r[2],···,r[j]為待排序列， 通過兩兩比較、交換，重新安排存放順序，使得r[j]是序列中關(guān)鍵碼最大的記錄。一趟冒泡方法為： ① i=1； //設(shè)置從第一個記錄開始進行兩兩比較 ② 若i≥j，一趟冒泡結(jié)束。,③比較r[i].key與r[i+1].key，若r[i]

36、.key≤r[i+1].key，不交換，轉(zhuǎn)⑤ ④ 當(dāng)r[i].key>r[i+1].key時， r[0]=r[i]；r[i]=r[i+1]；r[i+1]=r[0]； 將r[i]與r[i+1]交換 ⑤ i=i+1； 調(diào)整對下兩個記錄進行兩兩比較，轉(zhuǎn)② 冒泡排序方法：對n個記錄的表，第一趟冒泡得到一個關(guān)鍵碼最大的記錄r[n]，第二趟冒泡對n-1個記錄的表，再得到一個關(guān)鍵碼最大的記錄r

37、[n-1]，如此重復(fù)，直到n個記錄按關(guān)鍵碼有序的表。,【算法10.6】 ① j=n； //從n記錄的表開始 ② 若jr[i+1].key時， r[i]r[i+1]； 將r[i]與r[i+1]交換 ⑦ i=i+1； 調(diào)整對下兩個記錄進行兩兩比較，轉(zhuǎn)④,【效率分析】空間效率：僅用了一個輔助單元。時間效率：總共要進行n-1趟冒泡，對j個記錄的表進行一趟冒泡需要j-1次關(guān)鍵碼比較。,總比較次數(shù),移動次數(shù)：最好情況下：

38、待排序列已有序，不需移動。最壞情況下：每次比較后均要進行三次移動。,移動次數(shù),10.3.2 快速排序 快速排序是通過比較關(guān)鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點)，將待排序列分成兩部分。其中，一部分所有記錄的關(guān)鍵碼大于等于支點記錄的關(guān)鍵碼，另一部分所有記錄的關(guān)鍵碼小于支點記錄的關(guān)鍵碼。我們將待排序列按關(guān)鍵碼以支點記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個序列按關(guān)鍵碼有序。 一次劃分

39、方法： 設(shè)1≤p<q≤n，r[p],r[p+1],...,r[q]為待排序列 ① low=p；high=q； //設(shè)置兩個搜索指針，low是向后搜索指針，high是向前搜索指針 r[0]=r[low]； //取第一個記錄為支點記錄，low位置暫設(shè)為支點空位 ② 若low=high，支點空位確定，即為low。 r[low]=r[0]；

40、 //填入支點記錄，一次劃分結(jié)束 否則，low<high，搜索需要交換的記錄，并交換之,③ 若low<high且r[high].key≥r[0].key //從high所指位置向前搜索，至多到low+1位置 high=high-1；轉(zhuǎn)③ //尋找r[high].key<r[0].key r[low]=r[high]； //找到r[high].key<r[0]

41、.key，設(shè)置high為新支點位置，小于支點記錄關(guān)鍵碼的記錄前移。 ④ 若low<high且r[low].key<r[0].key //從low所指位置向后搜索，至多到high-1位置 low=low+1；轉(zhuǎn)④ //尋找r[low].key≥r[0].key r[high]=r[low]； //找到r[low].key≥r[0].key，設(shè)置low為新支點位置，大于等于支點記錄關(guān)鍵

42、碼的記錄后移。 轉(zhuǎn)② //繼續(xù)尋找支點空位,【算法10.7】int Partition(S_TBL *tbl,int low,int high) /*一趟快排序*/{ /*交換順序表tbl中子表tbl->[low…h(huán)igh]的記錄，使支點記錄到位，并反回其所在位置，此時，在它之前(后)的記錄均不大(小)于它*/tbl->r[0]=tbl->r[low]; /*以子

43、表的第一個記錄作為支點記錄*/pivotkey=tbl->r[low].key; /*取支點記錄關(guān)鍵碼*/while(lowr[high].key>=pivotkey) high--;tbl->r[low]=tbl->r[high]; /*將比支點記錄小的交換到低端*/while(lowr[high].keyr[low]=tbl->r[high]; /*將比支點記錄大的交換到低端*/

44、}tbl->r[low]=tbl->r[0]; /*支點記錄到位*/return low; /*反回支點記錄所在位置*/},【例10.5】一趟快排序過程示例 r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] r[10] 存儲單元 49 14 38 74 96 65 8 49 55 27 記錄中關(guān)

45、鍵碼low=1；high=10； 設(shè)置兩個搜索指針， r[0]=r[low]； 支點記錄送輔助單元， □ 14 38 74 96 65 8 49 55 27 ↑ ↑ low

46、 high第一次搜索交換 從high向前搜索小于r[0].key的記錄，得到結(jié)果 27 14 38 74 96 65 8 49 55 □ ↑ ↑ low

47、 high,從low向后搜索大于r[0].key的記錄，得到結(jié)果 27 14 38 □ 96 65 8 49 55 74 ↑ ↑ low

48、 high第二次搜索交換 從high向前搜索小于r[0].key的記錄，得到結(jié)果 27 14 38 8 96 65 □ 49 55 74 ↑ ↑ low high 從low向

49、后搜索大于r[0].key的記錄，得到結(jié)果 27 14 38 8 □ 65 96 49 55 74 ↑ ↑ low high,第三次搜索交換 從high向前搜索小于r[0].key的記錄，得到結(jié)果 27

50、14 38 8 □ 65 96 49 55 74 ↑↑ low high 從low向后搜索大于r[0].key的記錄，得到結(jié)果 27 14 38 8 □ 65 96 49 55 74

51、 ↑↑ low highlow=high，劃分結(jié)束，填入支點記錄 27 14 38 8 49 65 96 49 55 74,【算法10.8】void QSort(S_TBL *tbl,int low,int high) /*遞歸形式的快排序*/{/*對順序表tbl中的子序列tbl->[low

52、…h(huán)igh]作快排序*/if(low<high){ pivotloc=partition(tbl,low,high);/*將表一分為二*/ QSort(tbl,low,pivotloc-1); /*對低子表遞歸排序*/ QSort(tbl,pivotloc+1,high); /*對高子表遞歸排序*/}},快速排序的遞歸過程可用生成一棵二叉樹形象地給出，圖10.4為例10.5中待排序列對

53、應(yīng)遞歸調(diào)用過程的二叉樹。,38,74,96,8,49,27,55,49,65,,,,,,14,,,,,【效率分析】 空間效率：快速排序是遞歸的，每層遞歸調(diào)用時的指針和參數(shù)均要用棧來存放，遞歸調(diào)用層次數(shù)與上述二叉樹的深度一致。因而，存儲開銷在理想情況下為O(log2n)，即樹的高度；在最壞情況下，即二叉樹是一個單鏈，為O(n)。 時間效率：在n個記錄的待排序列中，一次劃分需要約n次關(guān)鍵碼比較，時效為O(n)，若設(shè)T(n)為對n個記

54、錄的待排序列進行快速排序所需時間。 理想情況下：每次劃分，正好將分成兩個等長的子序列，則  T(n)≤cn+2T(n/2) c是一個常數(shù) ≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4) ≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8) ····&

55、#183;· ≤cnlog2n+nT(1)=O(nlog2n),最壞情況下：即每次劃分，只得到一個子序列，時效為O(n2)。 快速排序是通常被認(rèn)為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取支點記錄，即將排序區(qū)間的兩個端點與中點三個記錄關(guān)鍵碼居中的調(diào)整為支點記錄?？焖倥判蚴且?/p>

56、個不穩(wěn)定的排序方法。,10.4 選擇排序,選擇排序主要是每一趟從待排序列中選取一個關(guān)鍵碼最小的記錄，也即第一趟從n個記錄中選取關(guān)鍵碼最小的記錄，第二趟從剩下的n-1個記錄中選取關(guān)鍵碼最小的記錄，直到整個序列的記錄選完。這樣，由選取記錄的順序，便得到按關(guān)鍵碼有序的序列。10.4.1 簡單選擇排序 操作方法：第一趟，從n個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的n-1個記錄中再選出關(guān)鍵碼最小的記錄與

57、第二個記錄交換；如此，第i趟，則從第i個記錄開始的n-i+1個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄交換，直到整個序列按關(guān)鍵碼有序。,【算法10.9】void SelectSort(S_TBL *s){for(i=1；ilength；i++){/* 作length-1趟選取 */for(j=i+1，t=i；jlength；j++){ /* 在i開始的length-n+1個記錄中選關(guān)鍵碼最小的記錄 */

58、if(s->elem[t].key>s->elem[j].key)t=j； /* t中存放關(guān)鍵碼最小記錄的下標(biāo) */} s->elem[t]s->elem[i]； /* 關(guān)鍵碼最小的記錄與第i個記錄交換 */}} 從程序中可看出，簡單選擇排序移動記錄的次數(shù)較少，但關(guān)鍵碼的比較次數(shù)依然是 ((n*(n+1))/2，所以時間復(fù)雜度仍為O(n2)。,10.4

59、.2樹形選擇排序 按照錦標(biāo)賽的思想進行，將n個參賽的選手看成完全二叉樹的葉結(jié)點，則該完全二叉樹有2n-2或2n-1個結(jié)點。首先，兩兩進行比賽(在樹中是兄弟的進行，否則輪空，直接進入下一輪)，勝出的再兄弟間再兩兩進行比較，直到產(chǎn)生第一名；接下來，將作為第一名的結(jié)點看成最差的，并從該結(jié)點開始，沿該結(jié)點到根路徑上，依次進行各分枝結(jié)點子女間的比較，勝出的就是第二名。因為和他比賽的均是剛剛輸給第一名的選手。如此，繼續(xù)進行下去，直到所有選

60、手的名次排定。,83,91,【例10.6】16個選手的比賽(n=24),91,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,91,,67,72,83,47,47,13,80,91,67,51,62,29,72,46,31,47,25,83,79,69,91,67,62,72,47,83,79,在上圖中，從葉結(jié)點開始的兄弟間兩兩比賽，勝者上升到父結(jié)點；勝者兄弟間再兩兩比賽

61、，直到根結(jié)點，產(chǎn)生第一名91。比較次數(shù)為 23+22+21+20=24-1=n-1。,83,80,83,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,80,,67,72,83,47,47,13,80,0,67,51,62,29,72,46,31,47,25,83,79,69,80,67,62,72,47,83,79,在上圖中，將第一名的結(jié)點置為最差的，與其兄弟比賽，

62、勝者上升到父結(jié)點，勝者兄弟間再比賽，直到根結(jié)點，產(chǎn)生第二名83。比較次數(shù)為4，即log2n次。其后各結(jié)點的名次均是這樣產(chǎn)生的，所以，對于n個參賽選手來說，即對n個記錄進行樹形選擇排序，總的關(guān)鍵碼比較次數(shù)至多為(n?1)log2n?n?1，故時間復(fù)雜度為O(nlog2n)。該方法占用空間較多，除需輸出排序結(jié)果的n個單元外，尚需n-1個輔助單元。,,,,,10.4.3 堆排序(Heap Sort) 設(shè)有n個元素的序列 k1，k

63、2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。,,,,,,,91,47,24,36,53,30,85,,16,,,,,,,12,36,85,47,30,53,24,,91,兩個堆示例,若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點的值均不大于(或不小于)其子女的值，根結(jié)點的值是最小(或最大)的。,設(shè)有n個元素，將其按關(guān)鍵碼排序。首先將這n個元素按關(guān)鍵碼建成堆，將堆頂元素輸出，得到n個元素中關(guān)鍵碼最小(或最大)的元素

64、。然后，再對剩下的n-1個元素建成堆，輸出堆頂元素，得到n個元素中關(guān)鍵碼次小(或次大)的元素。如此反復(fù)，便得到一個按關(guān)鍵碼有序的序列。稱這個過程為堆排序。 因此，實現(xiàn)堆排序需解決兩個問題： 1. 如何將n個元素的序列按關(guān)鍵碼建成堆； 2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1個元素，使其按關(guān)鍵碼成為一個新堆。 首先，討論輸出堆頂元素后，對剩余元素重新建成堆的調(diào)整過程。,調(diào)整方法：設(shè)有

65、m個元素的堆，輸出堆頂元素后，剩下m-1個元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結(jié)點不滿足堆的性質(zhì)。將根結(jié)點與左、右子女中較小(或小大)的進行交換。若與左子女交換，則左子樹堆被破壞，且僅左子樹的根結(jié)點不滿足堆的性質(zhì)；若與右子女交換，則右子樹堆被破壞，且僅右子樹的根結(jié)點不滿足堆的性質(zhì)。繼續(xù)對不滿足堆性質(zhì)的子樹進行上述交換操作，直到葉子結(jié)點，堆被建成。稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選。,【例10.6】,,,,,,,12,3

66、6,85,47,30,53,24,,91,,,,,,,91,36,85,47,30,53,24,自堆頂?shù)饺~子的調(diào)整過程,再討論對n個元素初始建堆的過程。,,,,,,,24,36,85,47,30,53,91,,,,,,,24,36,85,47,91,53,30,,,,a.輸出堆頂12，將堆低91送入堆頂,b.堆被破壞，根結(jié)點與右子女交換,c.右子樹不滿足堆，其根與左子女交換,d.堆已建成,,建堆方法：對初始序列建堆的過程，就是一個反復(fù)進

67、行篩選的過程。n個結(jié)點的完全二叉樹，則最,后一個結(jié)點是第,個結(jié)點的子女。對第,個結(jié)點,為根的子樹篩選，使該子樹成為堆，之后向前依次對各結(jié)點為根的子樹進行篩選，使之成為堆，直到根結(jié)點。,【例10.7】,,,,,,,53,36,91,47,12,24,30,,85,建堆示例,,a. 8個結(jié)點的初始狀態(tài),,,,,,,,53,36,91,47,12,24,30,,85,,,,,,,53,36,85,47,12,24,30,,91,,b.從第4個

68、結(jié)點開始篩選,c.對第3個結(jié)點開始篩選,,,,,,,,,建堆示例,,,,,,,,53,36,85,47,30,24,12,,91,d.第2個結(jié)點為根的子樹已是堆,,,,,,,,53,36,85,47,30,24,12,,91,e.對整棵樹進行篩選,,,,,,,12,36,85,47,30,24,53,,91,,,,,,,,,堆排序：對n個元素的序列進行堆排序，先將其建成堆，以根結(jié)點與第n個結(jié)點交換；調(diào)整前n-1個結(jié)點成為堆，再以根結(jié)點與

69、第n-1個結(jié)點交換；重復(fù)上述操作，直到整個序列有序。,【算法10.10】void HeapAdjust(S_TBL *h，int s，int m){/*r[s…m]中的記錄關(guān)鍵碼除r[s]外均滿足堆的定義，本函數(shù)將對第s個結(jié)點為根的子樹篩選，使其成為大頂堆*/rc=h->r[s]；for(j=2*s；jr[j].keyr[j+1].key)j=j+1； /* 為關(guān)鍵碼較大的元素下標(biāo)*/if(rc.keyr

70、[j].key) break； /* rc應(yīng)插入在位置s上*/h->r[s]=h->r[j]； s=j； /* 使s結(jié)點滿足堆定義 */}h->r[s]=rc； /* 插入 */},void HeapSort(S_TBL *h){for(i=h->length/2；i>0；i--) /* 將r[1..length]建成堆 */HeapAdjust(h，i