第十章排序ppt課件

1、新辦公地點(diǎn)：新辦公樓計(jì)算中心新辦公地點(diǎn)：新辦公樓計(jì)算中心805第十章第十章 內(nèi)部排序內(nèi)部排序10.1 排序排序設(shè)設(shè) n 個(gè)記錄的序列為個(gè)記錄的序列為 R1 , R2 , R3 , . . . , Rn 其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為 K1 , K2 , K3 , . . . , Kn 假設(shè)規(guī)定假設(shè)規(guī)定 1 , 2 , 3 , . . . , n 的一個(gè)陳列的一個(gè)陳列 p1 , p2 , p3 , . . . , pn ，使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系，使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系:Kp Kp Kp . . . Kp123n那么原序列變?yōu)橐粋€(gè)按關(guān)鍵字有序的序列那么原序列變?yōu)橐?/p>

2、個(gè)按關(guān)鍵字有序的序列:Rp , Rp , Rp , . . . , Rp123n 此操作過程稱為排序。此操作過程稱為排序。 排序分類排序分類 按待排序記錄所在位置按待排序記錄所在位置 內(nèi)部排序：待排序記錄存放在內(nèi)存內(nèi)部排序：待排序記錄存放在內(nèi)存 外部排序：排序過程中需對外存進(jìn)展訪問的外部排序：排序過程中需對外存進(jìn)展訪問的排序排序 按排序根據(jù)原那么按排序根據(jù)原那么 插入排序：直接插入排序、折半插入排序、插入排序：直接插入排序、折半插入排序、希爾排序希爾排序 交換排序：冒泡排序、快速排序交換排序：冒泡排序、快速排序 選擇排序：簡單項(xiàng)選擇擇排序、堆排序選擇排序：簡單項(xiàng)選擇擇排序、堆排序 歸并排序：歸

3、并排序：2-2-路歸并排序路歸并排序 基數(shù)排序基數(shù)排序 按排序后關(guān)鍵字相等的記錄的相對位置按排序后關(guān)鍵字相等的記錄的相對位置 穩(wěn)定排序穩(wěn)定排序 不穩(wěn)定排序不穩(wěn)定排序 按排序所需任務(wù)量按排序所需任務(wù)量 簡單的排序方法：簡單的排序方法：T(n)=O(n) 先進(jìn)的排序方法：先進(jìn)的排序方法：T(n)=O(logn) 基數(shù)排序：基數(shù)排序：T(n)=O(d.n) 排序根本操作排序根本操作 比較兩個(gè)關(guān)鍵字大小比較兩個(gè)關(guān)鍵字大小 將記錄從一個(gè)位置挪動(dòng)到另一個(gè)位置將記錄從一個(gè)位置挪動(dòng)到另一個(gè)位置穩(wěn)定排序穩(wěn)定排序 與與 不穩(wěn)定排序不穩(wěn)定排序假設(shè)假設(shè) Ki = Kj ，且排序前序列中，且排序前序列中 Ri 領(lǐng)先于領(lǐng)

4、先于 Rj ；假設(shè)在排序后的序列中假設(shè)在排序后的序列中 Ri 仍領(lǐng)先于仍領(lǐng)先于 Rj ，那么稱排序方法是，那么稱排序方法是穩(wěn)定的。穩(wěn)定的。假設(shè)在排序后的序列中假設(shè)在排序后的序列中 Rj 仍領(lǐng)先于仍領(lǐng)先于 Ri ，那么稱排序方法，那么稱排序方法是不穩(wěn)定的。是不穩(wěn)定的。例，序列例，序列 3 15 8 8 6 9假設(shè)排序后得假設(shè)排序后得 3 6 8 8 9 15穩(wěn)定的穩(wěn)定的假設(shè)排序后得假設(shè)排序后得 3 6 8 8 9 15不穩(wěn)定的不穩(wěn)定的內(nèi)部排序內(nèi)部排序 與與 外部排序外部排序內(nèi)部排序內(nèi)部排序: 指的是待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲指的是待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲器中進(jìn)展的排序過程。器中進(jìn)展的排

5、序過程。外部排序外部排序: 指的是待排序記錄的數(shù)量很大，以致內(nèi)存指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能包容全部記錄，在排序過程中尚需對外存進(jìn)一次不能包容全部記錄，在排序過程中尚需對外存進(jìn)展訪問的排序過程。展訪問的排序過程。內(nèi)部排序內(nèi)部排序按照排序過程中所根據(jù)的原那么的不同可以分類按照排序過程中所根據(jù)的原那么的不同可以分類為為: 插入排序插入排序 交換排序交換排序(快速排序快速排序) 選擇排序選擇排序 歸并排序歸并排序 基數(shù)排序基數(shù)排序 二叉排序樹排序二叉排序樹排序10.2 插入排序插入排序插入排序是將當(dāng)前無序區(qū)中最前端的記錄插入到有序區(qū)插入排序是將當(dāng)前無序區(qū)中最前端的記錄插入到有序區(qū)中，

6、逐漸擴(kuò)展有序區(qū)，直到一切記錄都插入到有序區(qū)中，逐漸擴(kuò)展有序區(qū)，直到一切記錄都插入到有序區(qū)中為止。中為止。 直接插入排序直接插入排序1 1過程：在有序區(qū)中進(jìn)展順序查找以確定插入的位過程：在有序區(qū)中進(jìn)展順序查找以確定插入的位置，然后挪動(dòng)記錄騰出空間，以便相應(yīng)關(guān)鍵字的記錄置，然后挪動(dòng)記錄騰出空間，以便相應(yīng)關(guān)鍵字的記錄插入。插入。在有序區(qū)的前端在有序區(qū)的前端r0r0中設(shè)一個(gè)監(jiān)視哨，存放當(dāng)前要插中設(shè)一個(gè)監(jiān)視哨，存放當(dāng)前要插入的關(guān)鍵字。入的關(guān)鍵字。例，序列例，序列 49 38 65 97 76 13 27 初始，初始，S = 49 ； 38 49 算法描畫算法描畫:初始，令第初始，令第 1 個(gè)元素作為初始

7、有序表；個(gè)元素作為初始有序表；依次插入第依次插入第 2 , 3 , , k 個(gè)元素構(gòu)造新的有序表；個(gè)元素構(gòu)造新的有序表；直至最后一個(gè)元素；直至最后一個(gè)元素； 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ùn)用比較和挪動(dòng)兩種操作。直接插入排序算法主要運(yùn)用比較和挪動(dòng)兩種操作。算法：算法：InsertSort(r,n)InsertSort(r,n) for (i=2;i=n;i+)for (i=2;i=n;i+)r0=ri; j=i-1;r0=ri; j=i-1;while (

8、r0rj)while (r0rj)rj+1=rj;rj+1=rj;j-;j-; rj+1=r0;rj+1=r0; 舉例：有序列：舉例：有序列：20,6,15,7,320,6,15,7,3，過稱為：，過稱為：r0r1r2r3r4r5 6 20 6 15 7 3 15 6 20 15 7 3 7 6 15 20 7 3 3 6 7 15 20 3 3 6 7 15 20 算法評價(jià)算法評價(jià) 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 假設(shè)待排序記錄按關(guān)鍵字從小到大陳列假設(shè)待排序記錄按關(guān)鍵字從小到大陳列(正序正序) 關(guān)鍵字比較次數(shù)：關(guān)鍵字比較次數(shù)：112nniY記錄挪動(dòng)次數(shù)：記錄挪動(dòng)次數(shù)：)1(222nni 假設(shè)待排序記錄

9、按關(guān)鍵字從大到小陳列假設(shè)待排序記錄按關(guān)鍵字從大到小陳列(逆序逆序) 關(guān)鍵字比較次數(shù)：關(guān)鍵字比較次數(shù)：2)1)(2(2nniniY記錄挪動(dòng)次數(shù)：記錄挪動(dòng)次數(shù)：2)1)(4()1(2nnini 假設(shè)待排序記錄是隨機(jī)的，取平均值假設(shè)待排序記錄是隨機(jī)的，取平均值 關(guān)鍵字比較次數(shù)約為：關(guān)鍵字比較次數(shù)約為：42nY記錄挪動(dòng)次數(shù)約為：記錄挪動(dòng)次數(shù)約為：42nT(n)=O(n) 空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)如何改良直接插入排序算法如何改良直接插入排序算法1. 從比較次數(shù)改良從比較次數(shù)改良: 折半插入排序折半插入排序由于直接插入排序算法利用了有序表的插入操作，由于直接插入排序算法利用了有序表的插入

10、操作，故順序查找操作可以交換為折半查找操作。故順序查找操作可以交換為折半查找操作。例，序列例，序列 49 38 65 97 76 13 27 設(shè)已構(gòu)成有序表設(shè)已構(gòu)成有序表 38 49 65 97 76 插入元素插入元素 13算法算法BinSort(r,n)BinSort(r,n) for (i=2;i=n;i+)for (i=2;i=n;i+)r0=ri; low=1; hig=i-1;r0=ri; low=1; hig=i-1; while (lowhig) while (lowhig) mid=(low+hig)/2; mid=(low+hig)/2; if (r0rmid) hig=mi

11、d-1; if (r0=low;j-)for (j=i-1;j=low;j-) rj+1=rj; rj+1=rj;rlow=r0;rlow=r0; 從挪動(dòng)次數(shù)上改良從挪動(dòng)次數(shù)上改良: 2-路插入排序路插入排序主要目的是減少排序過程中挪動(dòng)記錄的次數(shù)。主要目的是減少排序過程中挪動(dòng)記錄的次數(shù)。思想思想:以第一個(gè)元素為基準(zhǔn)，將元素分為兩個(gè)序列；以第一個(gè)元素為基準(zhǔn)，將元素分為兩個(gè)序列；比第一個(gè)元素小的元素構(gòu)造前序列；比第一個(gè)元素小的元素構(gòu)造前序列；比第一個(gè)元素大的元素構(gòu)造后序列；比第一個(gè)元素大的元素構(gòu)造后序列；例，序列例，序列 49 38 65 97 76 13 27 以以 49 為基準(zhǔn)為基準(zhǔn) 13 2

12、7 38 前序列前序列 65 76 97 后序列后序列算法描畫算法描畫初始，取第一個(gè)元素為基準(zhǔn)元素；初始，取第一個(gè)元素為基準(zhǔn)元素；構(gòu)造前序列構(gòu)造前序列 S1，后序列，后序列 S2 ；與基準(zhǔn)元素比較與基準(zhǔn)元素比較:假設(shè)小，插入到前序列假設(shè)小，插入到前序列 S1 中；中；假設(shè)大，插入到后序列假設(shè)大，插入到后序列 S2 中；中；對第對第 2 , 3 , , n 個(gè)元素依次執(zhí)行個(gè)元素依次執(zhí)行:S1 + 基準(zhǔn)元素基準(zhǔn)元素 + S2 可得最終有序表?？傻米罱K有序表。例，序列例，序列 49 38 65 97 76 13 27 以以 49 為基準(zhǔn)為基準(zhǔn)前序列前序列后序列后序列 38 65 65 97 65 7

13、6 97 13 38 13 27 38 13 27 38 + 49 + 65 76 97 10.2.2 希爾希爾(shell)排序排序分析直接插入排序分析直接插入排序1. 假設(shè)待排序記錄序列按關(guān)鍵字根本有序，那么排假設(shè)待排序記錄序列按關(guān)鍵字根本有序，那么排序效率可大大提高；序效率可大大提高；2. 待排序記錄總數(shù)越少，排序效率越高；待排序記錄總數(shù)越少，排序效率越高；希爾排序希爾排序(減少增量法減少增量法)排序過程：先取一個(gè)正整數(shù)排序過程：先取一個(gè)正整數(shù)d1n，把一切相隔，把一切相隔d1的記的記錄放一組，組內(nèi)進(jìn)展直接插入排序；然后取錄放一組，組內(nèi)進(jìn)展直接插入排序；然后取d20)while (f0)

14、k=f-1; f=0;k=f-1; f=0;for (j=1;j=k;j+)for (j=1;jrj+1) if (rjrj+1) t=rj; rj=rj+1; rj+1=t; t=rj; rj=rj+1; rj+1=t; f-; f-; 算法也可寫成：算法也可寫成：BubbSort(r,n)BubbSort(r,n) for (i=0;in-1;i+)for (i=0;in-1;i+) for (j=i+1;jn;j+) for (j=i+1;jrj) if (rirj) t=ri; ri=rj; rj=t; t=ri; ri=rj; rj=t; 算法評價(jià)算法評價(jià) 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 最好

15、情況正序最好情況正序 比較次數(shù)：比較次數(shù)：n-1 挪動(dòng)次數(shù)：挪動(dòng)次數(shù)：0 最壞情況逆序最壞情況逆序 比較次數(shù)：比較次數(shù)：)(21)(211nninniY挪動(dòng)次數(shù)：挪動(dòng)次數(shù)：)(23)(321nninni 空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)T(n)=O(n) 10.3.2 10.3.2 快速排序快速排序1 1根本思想：快速排序是對冒泡排序的一種改根本思想：快速排序是對冒泡排序的一種改良。經(jīng)過一趟排序?qū)⒁粋€(gè)無序區(qū)分割成兩個(gè)獨(dú)立良。經(jīng)過一趟排序?qū)⒁粋€(gè)無序區(qū)分割成兩個(gè)獨(dú)立的無序子區(qū)，其中前一部分子區(qū)中一切元素關(guān)鍵的無序子區(qū)，其中前一部分子區(qū)中一切元素關(guān)鍵字均不大于后一部分子區(qū)中元素關(guān)鍵字，然后

16、對字均不大于后一部分子區(qū)中元素關(guān)鍵字，然后對每一子區(qū)再進(jìn)展分割，直到整個(gè)序列有序?yàn)橹?。每一子區(qū)再進(jìn)展分割，直到整個(gè)序列有序?yàn)橹埂? 2分割過程：分割過程： 選取表中一個(gè)元素選取表中一個(gè)元素rkrk普通選取第一個(gè)普通選取第一個(gè)元素，令元素，令x=rkx=rk，稱為控制關(guān)鍵字，稱為控制關(guān)鍵字，用用控制關(guān)鍵字和無序區(qū)中其他元素關(guān)鍵字進(jìn)展比較。控制關(guān)鍵字和無序區(qū)中其他元素關(guān)鍵字進(jìn)展比較。 設(shè)置兩個(gè)指示器設(shè)置兩個(gè)指示器i,ji,j，分別表示線性表第，分別表示線性表第一個(gè)和最后一個(gè)元素位置。一個(gè)和最后一個(gè)元素位置。 將將j j逐漸減小，逐次比較逐漸減小，逐次比較rjrj與與x x，直到出現(xiàn)一個(gè)，直到出現(xiàn)一

17、個(gè)rjxrjxrix，然后將，然后將riri移到移到rj rj 位置。如此反復(fù)進(jìn)展，直到位置。如此反復(fù)進(jìn)展，直到i=ji=j為止，為止，最后將最后將x x移到移到rjrj位置，完成一趟排序。此時(shí)以位置，完成一趟排序。此時(shí)以x x為為界分割成兩個(gè)子區(qū)。界分割成兩個(gè)子區(qū)。舉例：設(shè)序列為舉例：設(shè)序列為46,55,13,42,94,5,17,7046,55,13,42,94,5,17,70j ji i46 55 13 42 94 5 17 70 46 55 13 42 94 5 17 70 起始形狀，起始形狀，46x46x，4646為控制關(guān)鍵為控制關(guān)鍵字字j ji i17 55 13 42 94 5

18、17 70 17 55 13 42 94 5 17 70 挪動(dòng)挪動(dòng)j j，17ri17rij ji i17 55 13 42 94 5 55 70 17 55 13 42 94 5 55 70 挪動(dòng)挪動(dòng)i i，55rj55rjj ji i17 5 13 42 94 5 55 70 17 5 13 42 94 5 55 70 挪動(dòng)挪動(dòng)j j，5ri5rij ji i17 5 13 42 94 94 55 70 17 5 13 42 94 94 55 70 挪動(dòng)挪動(dòng)i i，94rj94rjj ji i17 5 13 42 46 94 55 70 17 5 13 42 46 94 55 70 挪動(dòng)挪

19、動(dòng)j j，i=ji=j，xrixri，一趟排序，一趟排序終了終了算法：算法：QkSort(r,low,hig)QkSort(r,low,hig) x=rlow; i=low; j=hig;x=rlow; i=low; j=hig;while (ij)while (ij)while (i=x) j-;while (i=x) j-;t=ri; ri=rj; rj=t;t=ri; ri=rj; rj=t;while (ij&ri=x) i+;while (ij&ri=x) i+;t=ri; ri=rj; rj=t;t=ri; ri=rj; rj=t; ri=x;ri=x;QkSort

20、(r,low,i-1); QkSort(r,low,i-1); QkSort(r,i+1,hig);QkSort(r,i+1,hig); 算法評價(jià)算法評價(jià) 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 最好情況每次總是選到中間值作樞軸最好情況每次總是選到中間值作樞軸T(n)=O(nlog2n) 最壞情況每次總是選到最小或最大元素作樞軸最壞情況每次總是選到最小或最大元素作樞軸T(n)=O(n) 空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸 最壞情況：最壞情況：S(n)=O(n) 普通情況：普通情況：S(n)=O(log2n)T(n)=O(n)10.4 選擇排序選擇排序思想思想: 每一趟都選出一個(gè)最大或最

21、小的元素，并放在每一趟都選出一個(gè)最大或最小的元素，并放在適宜的位置。適宜的位置。 簡單項(xiàng)選擇擇排序簡單項(xiàng)選擇擇排序 樹形選擇排序樹形選擇排序 堆排序堆排序10.4.1 簡單項(xiàng)選擇擇排序簡單項(xiàng)選擇擇排序思想思想: 第第 1 趟選擇趟選擇: 從從 1n 個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第 1 個(gè)個(gè)記錄交換。記錄交換。第第 2 趟選擇趟選擇: 從從 2n 個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第 2 個(gè)個(gè)記錄交換。記錄交換。第第n-1趟選擇趟選擇:從從 n-1n 個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第個(gè)記錄中選擇關(guān)鍵字最小的記錄，并

22、和第 n-1 個(gè)記錄交換。個(gè)記錄交換。. . .舉例：設(shè)有序列：舉例：設(shè)有序列： 5,4,12,20,27,3,1 5,4,12,20,27,3,1 ，排序，排序過稱為：過稱為：i=0i=0： 5 5，4 4，1212，2020，2727，3 3，1 1 i=1i=1： 1 1，4 4，1212，2020，2727，3 3，5 5 i=2i=2： 1 1，3 3，1212，2020，2727，4 4，5 5 i=3i=3： 1 1，3 3，4 4，2020，2727，1212，5 5 i=4i=4： 1 1，3 3，4 4，5 5，2727，1212，20 20 i=5i=5： 1 1，3 3

23、，4 4，5 5，1212，2727，20 20 結(jié)果：結(jié)果： 1 1，3 3，4 4，5 5，1212，2020，27 27 算法算法SelSort(r,n)SelSort(r,n) for (i=0;in-1;i+)for (i=0;in-1;i+)j=i;j=i;for (k=i+1;kn;k+)for (k=i+1;kn;k+)if (rjrk) j=k;if (rjrk) j=k;if (j!=i)if (j!=i)t=ri; ri=rk; rk=t;t=ri; ri=rk; rk=t; 算法分析：算法由兩層循環(huán)構(gòu)成，外層循環(huán)表示共需算法分析：算法由兩層循環(huán)構(gòu)成，外層循環(huán)表示共需進(jìn)展

24、進(jìn)展n-1n-1趟排序，內(nèi)層循環(huán)表示每進(jìn)展一趟排序需趟排序，內(nèi)層循環(huán)表示每進(jìn)展一趟排序需求進(jìn)展的記錄關(guān)鍵字間的比較。求進(jìn)展的記錄關(guān)鍵字間的比較。 比較次數(shù)：比較次數(shù)：n(n-1)/2n(n-1)/2 挪動(dòng)次數(shù)：最壞情況下為挪動(dòng)次數(shù)：最壞情況下為3(n-1)3(n-1)所以總的時(shí)間復(fù)雜度為：所以總的時(shí)間復(fù)雜度為：O(n2)O(n2)空間復(fù)雜度為：空間復(fù)雜度為：O(1) O(1) 交換記錄用交換記錄用選擇排序的主要操作是進(jìn)展關(guān)鍵字間的比較。選擇排序的主要操作是進(jìn)展關(guān)鍵字間的比較。在在 n 個(gè)關(guān)鍵字中選出最小值，至少需求個(gè)關(guān)鍵字中選出最小值，至少需求 n-1 次比較。次比較。在剩余的在剩余的 n-1

25、 個(gè)關(guān)鍵字中選出最小值，至少需求個(gè)關(guān)鍵字中選出最小值，至少需求 n-2 次比較？次比較？假設(shè)能利用前假設(shè)能利用前 n-1 次比較所得信息，可以減少后面選擇的比較次數(shù)。次比較所得信息，可以減少后面選擇的比較次數(shù)。體育競賽中的錦標(biāo)賽體育競賽中的錦標(biāo)賽:例，例，8 名運(yùn)發(fā)動(dòng)要決出名運(yùn)發(fā)動(dòng)要決出 冠、亞、季軍。冠、亞、季軍。按簡單項(xiàng)選擇擇排序需求競賽按簡單項(xiàng)選擇擇排序需求競賽 7+6+5 = 18 場。場。假設(shè)可以利用以前的競賽結(jié)果，競賽場次實(shí)踐可以減少為假設(shè)可以利用以前的競賽結(jié)果，競賽場次實(shí)踐可以減少為 11 場。場。前提前提: 假設(shè)假設(shè) 甲甲 勝勝 乙乙 ，乙，乙 勝勝 丙丙 ，那么，那么 甲甲

26、必能勝必能勝 丙丙 。ZhaoxiaLiuBaoDiYangXueWangBaoBaoDixiaBaoDiWang冠軍冠軍如何求如何求 亞軍？亞軍？ZhaoChaLiuDiYangXueWangxiaDixia亞軍亞軍可以利用前面的競賽結(jié)果！可以利用前面的競賽結(jié)果！xiaLiuDiWang如何求如何求 季軍？季軍？ZhaoLiuDiYangXueWangLiuDiDi季軍季軍同樣可以利用前面的競賽結(jié)果！同樣可以利用前面的競賽結(jié)果！LiuDiWangZhao10.4.2 樹形選擇排序樹形選擇排序又稱錦標(biāo)賽排序，是一種按照錦標(biāo)賽的思想進(jìn)展選擇排序的方法。又稱錦標(biāo)賽排序，是一種按照錦標(biāo)賽的思想進(jìn)展選

27、擇排序的方法。例，序列例，序列 49 38 65 97 76 13 27 50第一趟選擇第一趟選擇133813493865977613275038651327最小值最小值第二趟選擇第二趟選擇2738274938659776275038657627次小值次小值第三趟選擇第三趟選擇38385049386597765038657650次次小值次次小值493865977613275049386597762750缺陷缺陷: 需求需求大量輔助存大量輔助存儲空間儲空間 堆排序堆排序 堆的定義：堆的定義：n個(gè)元素的序列個(gè)元素的序列(k1,k2,kn)，當(dāng)且，當(dāng)且僅當(dāng)滿足以下關(guān)系時(shí)，稱之為堆僅當(dāng)滿足以下關(guān)系時(shí)，

28、稱之為堆或或(i=1,2,.n/2 )kik2ikik2i+1kik2ikik2i+1例例 96，83，27，38，11，9 例例 13，38，27，50，76，65，49，97962791138831327384965765097可將堆序列看成完全二叉樹，那么堆頂元素完全二叉樹的根可將堆序列看成完全二叉樹，那么堆頂元素完全二叉樹的根必為序列中必為序列中n個(gè)元素的最小值或最大值個(gè)元素的最小值或最大值 堆排序：將無序序列建成一個(gè)堆，得到關(guān)鍵字最小或最堆排序：將無序序列建成一個(gè)堆，得到關(guān)鍵字最小或最大的記錄；輸出堆頂?shù)淖钚〈笾岛?，使剩余的大的記錄；輸出堆頂?shù)淖钚〈笾岛?，使剩余的n-1個(gè)個(gè)元素重又建

29、成一個(gè)堆，那么可得到元素重又建成一個(gè)堆，那么可得到n個(gè)元素的次小值；反個(gè)元素的次小值；反復(fù)執(zhí)行，得到一個(gè)有序序列，這個(gè)過程叫復(fù)執(zhí)行，得到一個(gè)有序序列，這個(gè)過程叫 堆排序需處理的兩個(gè)問題：堆排序需處理的兩個(gè)問題： 如何由一個(gè)無序序列建成一個(gè)堆？如何由一個(gè)無序序列建成一個(gè)堆？ 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？新的堆？ 第二個(gè)問題處理方法第二個(gè)問題處理方法挑選挑選 方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)展比較，并與然后將根結(jié)點(diǎn)

30、值與左、右子樹的根結(jié)點(diǎn)值進(jìn)展比較，并與其中小者進(jìn)展交換；反復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得其中小者進(jìn)展交換；反復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“挑選挑選例例13273849657650979727384965765013輸出：輸出：132749389765765013輸出：輸出：139749382765765013輸出：輸出：13 273849502765769713輸出：輸出：13 276549502738769713輸出：輸出：13 27 384965502738769713輸出：輸出：13 27 38766550

31、2738499713輸出：輸出：13 27 38 495065762738499713輸出：輸出：13 27 38 499765762738495013輸出：輸出：13 27 38 49 506597762738495013輸出：輸出：13 27 38 49 509765762738495013輸出：輸出：13 27 38 49 50 657665972738495013輸出：輸出：13 27 38 49 50 659765762738495013輸出：輸出：13 27 38 49 50 65 769765762738495013輸出：輸出：13 27 38 49 50 65 76 97算法為

32、：算法為：Typedef SqList HeapTypeTypedef SqList HeapType；/堆采用順序構(gòu)造存儲堆采用順序構(gòu)造存儲, ,數(shù)組數(shù)組r rVoid HeapAdjust(HeapType r,int s,int m)Void HeapAdjust(HeapType r,int s,int m) t=rs;t=rs; for(j=2 for(j=2* *s;j=m;js;j=m;j* *=2)=2) if (jrj+1) j+; if (jrj+1) j+; if (trj) rs=rj; s=j; if (trj) rs=rj; s=j; else break;else

33、 break; ri=t;ri=t; R1.7=97,38,27,50,76,65,49R1.7=97,38,27,50,76,65,49S=1,m=7S=1,m=7 第一個(gè)問題處理方法第一個(gè)問題處理方法 方法：從無序序列的第方法：從無序序列的第n/2 個(gè)元素即此無序序列對個(gè)元素即此無序序列對應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)起，至第一個(gè)應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)起，至第一個(gè)元素止，進(jìn)展反復(fù)挑選元素止，進(jìn)展反復(fù)挑選97273849657650例例 含含8個(gè)元素的無序序列個(gè)元素的無序序列49，38，65，97，76，13，27，504965382713769750496538271376

34、5097491338276576509749133827657650971327384965765097 算法為：HeapSort(HeapType r,n) for (i=n/2;i=1;i-) HeapAdjust(r,n,i); /初始建堆 for (i=n;i=2;i-) r1=ri; HeapAdjust(r,i-1,1); 算法評價(jià)算法評價(jià) 時(shí)間復(fù)雜度：最壞情況下時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn) 空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)10.5 歸并排序歸并排序歸并歸并: 將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。

35、有序線性表、有序鏈表的歸并；有序線性表、有序鏈表的歸并；利用歸并的思想實(shí)現(xiàn)排序利用歸并的思想實(shí)現(xiàn)排序 :初始，初始，n 個(gè)記錄看作是個(gè)記錄看作是 n 個(gè)有序的子序列，長度為個(gè)有序的子序列，長度為 1 ；兩兩歸并，得到兩兩歸并，得到 n/2 個(gè)長度為個(gè)長度為 2 或或 1 的有序的子序列的有序的子序列 ；再兩兩歸并再兩兩歸并 ；反復(fù)執(zhí)行直至得到一個(gè)長度為反復(fù)執(zhí)行直至得到一個(gè)長度為 n 的有序序列為止的有序序列為止 。這種排序方法稱為這種排序方法稱為 2路歸并排序。路歸并排序。例，序列例，序列 49 , 38 , 65 , 97 , 76 , 13 , 27 初始初始 49 38 65 97 76

36、 13 27 一趟歸并一趟歸并38 4965 9713 7627二趟歸并二趟歸并38 49 65 9713 27 76三趟歸并三趟歸并13 27 38 49 65 76 97void mergesort(JD r,int n) int i,s=1; JD tM; while(sn) tgb(s,n,r,t); s*=2; if(sn) tgb(s,n,t,r); s*=2; else i=1; while(i=n) ri=ti+; void tgb(int s,int n,JD r,JD t) int i=1; while(i=(n-2*s+1) merge(r,i,i+s-1,i+2*s-1

37、,t); i=i+2*s; if(i(n-s+1) merge(r,i,i+s-1,n,t); else while(i=n) ti=ri+;void merge(JD r,int h,int m,int w,JD t) int i,j,k; i=h; j=m+1; k=h-1; while(i=m)&(j=w) k+; if(ri.keym) while(j=w) t+k=rj+; else while(i=m) t+k=ri+; 算法評價(jià)算法評價(jià) 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：T(n)=O(nlog2n) 空間復(fù)雜度：空間復(fù)雜度：S(n)=O(n)10.6 基數(shù)排序基數(shù)排序是一種借助多關(guān)

38、鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)展排序的方法。是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)展排序的方法。10.6.1 多關(guān)鍵字排序多關(guān)鍵字排序撲克牌問題撲克牌問題 :知撲克牌中知撲克牌中52張牌面的次序關(guān)系定義為張牌面的次序關(guān)系定義為: 花樣花樣:面值面值:2 3 A. . .例，例， 8 3花樣優(yōu)先級更高，花樣優(yōu)先級更高，為主關(guān)鍵字，面為主關(guān)鍵字，面值為次關(guān)鍵字值為次關(guān)鍵字52張牌排序方法張牌排序方法 :最高位優(yōu)先法最高位優(yōu)先法(MSDF) :先按不同先按不同“花樣分成有次序的花樣分成有次序的4堆，每一堆均具有一樣的花樣；堆，每一堆均具有一樣的花樣；然后分別對每一堆按然后分別對每一堆按“面值大

39、小整理有序。面值大小整理有序。最低位優(yōu)先法最低位優(yōu)先法(LSDF) :先按不同先按不同“面值分成面值分成 13 堆堆 ；然后將這然后將這 13 堆牌自小至大疊在一同堆牌自小至大疊在一同( 2 , 3 , . . . , A ) ；然后將這付牌整個(gè)顛倒過來再重新按不同的然后將這付牌整個(gè)顛倒過來再重新按不同的“花樣分成花樣分成 4 堆堆 ；最后將這最后將這 4 堆牌按自小至大的次序合在一同堆牌按自小至大的次序合在一同 。搜集搜集分配分配10.6.2 基數(shù)排序基數(shù)排序基數(shù)排序就是借助于基數(shù)排序就是借助于“分配和分配和“搜集兩種操作實(shí)現(xiàn)對單邏輯關(guān)鍵搜集兩種操作實(shí)現(xiàn)對單邏輯關(guān)鍵字的排序。字的排序。首先，

40、單邏輯關(guān)鍵字通常都可以看作是由假設(shè)干關(guān)鍵字復(fù)合而成。首先，單邏輯關(guān)鍵字通常都可以看作是由假設(shè)干關(guān)鍵字復(fù)合而成。其次，利用其次，利用 LSDF 法實(shí)現(xiàn)對假設(shè)干關(guān)鍵字的排序。法實(shí)現(xiàn)對假設(shè)干關(guān)鍵字的排序。例，假設(shè)關(guān)鍵字是數(shù)值，且值域?yàn)槔?，假設(shè)關(guān)鍵字是數(shù)值，且值域?yàn)?0K999 ，故可以將故可以將 K 看作是由看作是由 3 個(gè)關(guān)鍵字個(gè)關(guān)鍵字 K0 K1 K2 組成，組成，例，例，603是由是由 6 0 3 組成。組成。例，序列例，序列 278 109 063 930 589 184 505 269 008 083第一趟分配第一趟分配0 1 2 3 4 5 6 7 8 9278 109063930589184505269008083第一趟搜集第一趟搜集930063 083184505278 008109 589 269第二趟分配第二趟分配0 1 2 3 4 5 6 7 8 9930063083184505278008109589269第二趟搜集第二趟搜集505 008 109930063 269278083 184 589第二趟搜集第二趟搜集505 008 109930063 269278083 184 589第三趟分配第三趟分配0 1 2 3 4 5 6 7 8