各種經(jīng)典排序算法

本節(jié)基本內(nèi)容與要求

順序查找、二分查找、二叉樹查找以及散列表上查找及算法思想排序的基本概念以及選擇、插入、交換和歸并四類排序的基本思想和算法要求掌握線性表、樹和散列表(或稱哈希表)的查找方法及算法實(shí)現(xiàn)以及各種查找方法的應(yīng)用熟練掌握選擇、插入、交換和歸并四類排序的基本思想和算法2021/5/911.4內(nèi)部排序一、基本概念二、插入排序三、交換排序四、選擇排序五、歸并排序2021/5/92一、基本概念1.

排序的功能：將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個(gè)按關(guān)鍵字有序的序列。例如：下列是一組記錄對應(yīng)的關(guān)鍵字序列(52,49,80,36,14,58,61,23,97,75)調(diào)整為(14,23,36,49,52,58,61,75,80,97)2021/5/932.

排序的定義假設(shè)含n個(gè)記錄的序列為{R1,R2,…，Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系：

Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將上式記錄序列重新排列為

{Rp1,Rp2,…，Rpn}的操作稱作排序。2021/5/943、排序的基本操作排序的概念：就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。排序過程的組成步驟：首先比較兩個(gè)關(guān)鍵字的大??；然后將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。對記錄的關(guān)鍵字大小進(jìn)行比較將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí)，則排序結(jié)果是唯一的，否則排序的結(jié)果不一定唯一。2021/5/954、排序的穩(wěn)定性若有：

{R1,...,Ri,...,Rj,.....}且關(guān)鍵字：

Ki=Kj

i<>j排序后：

{Ri,Rj,.....}則稱該排序結(jié)果具有穩(wěn)定性。在待排序的文件中，若存在多個(gè)關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。2021/5/96內(nèi)部排序：是指在排序的整個(gè)過程中，數(shù)據(jù)全部存放在計(jì)算機(jī)的內(nèi)存儲器里，并且在內(nèi)存儲器里調(diào)整數(shù)據(jù)的位置；當(dāng)文件很大以致內(nèi)存不足以存放全部數(shù)據(jù)時(shí)，在排序過程中需要對外存進(jìn)行存取訪問，稱這種借助于外存儲器進(jìn)行排序的方法為外部排序。注意：①內(nèi)排序適用于記錄個(gè)數(shù)不很多的小文件②外排序則適用于記錄個(gè)數(shù)太多，不能一次將其全部記錄放入內(nèi)存的大文件。5、排序的分類2021/5/97

每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。把新元素（未排序的元素的關(guān)鍵字）逐個(gè)插入正在增長的順序表中。尋找插入位置的方法：線性插入排序?qū)Π氩迦肱判蛳柵判蚨⒉迦肱判?021/5/98有序序列L.r[1..i-1]L.r[i]無序序列L.r[i..n]有序序列L.r[1..i]無序序列L.r[i+1..n]1、線性插入排序基本思想：每步將一個(gè)待排序的元素按其大小插入到前面已排序的數(shù)據(jù)中的適當(dāng)位置。重復(fù)該工作，直至有序區(qū)包含所有元素。2021/5/99方法：具體方法：先將第一個(gè)數(shù)據(jù)看成是一個(gè)有序的子序列，然后從第2個(gè)數(shù)據(jù)起逐個(gè)插入到這個(gè)有序的子序列中去，相應(yīng)的元素要移動(dòng)。3．將L.r[i]插入到L.r[j+1]的位置上。2．將L.r[j+1..i-1]中的所有記錄均后移一個(gè)位置；1．在L.r[1..i-1]中查找L.r[i]的插入位置，

L.r[1..j]L.r[i]<L.r[j+1..i-1]；2021/5/910該算法適合于n較小的情況，時(shí)間復(fù)雜度為O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

線性插入排序示例對于有n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次例：2021/5/911voidinsertSort(RedTypeL[],intn){inti,j;for(i=2;i<=n;i++){L[0]=L[i];//作為監(jiān)視哨

for(j=i-1;L[0].key<L[j].key;

j) L[j+1]=L[j];//記錄后移

L[j+1]=L[0];//插入

}}插入算法方法:Ki與Ki-1,Ki-2,…K1依次比較,直到找到應(yīng)插入的位置。2021/5/912哨兵(監(jiān)視哨)哨兵(監(jiān)視哨)有兩個(gè)作用作為臨時(shí)變量存放R[i](當(dāng)前要進(jìn)行比較的關(guān)鍵字)的副本；在查找循環(huán)中用來監(jiān)視下標(biāo)變量j是否越界。R[0]R[1]R[2]R[3]R[4]R[5]6 20 6 15 7 315 6 20 15 7 37 6 15 20 7 33 6 7 15 20 3 3 6 7 15 202021/5/913直接插入排序的程序：#include"stdio.h"#definen5intar[n];intc,t;voidd_insort(a)inta[n];{inti,j; for(i=2;i<=n;i++) {t=a[i];j=i-1; while((j>0)&&(t<a[j])) {a[j+1]=a[j];j=j-1;} a[j+1]=t; }}2021/5/914main(){inti;printf("請輸入數(shù)據(jù):");for(i=1;i<=n;i++) scanf("%d",&ar[i]);d_insort(ar);printf("排序后的序列:");for(i=1;i<=n;i++) { printf("%d|",ar[i]); }printf("\n");}運(yùn)行結(jié)果：請輸入數(shù)據(jù):5060204080排序后的序列:20|40|50|60|80|2021/5/915性能分析最好情況（原始記錄按關(guān)鍵字有序排列）：O（n）“比較”的次數(shù)：最壞情況（原始記錄按關(guān)鍵字逆序排列）：O（n2）“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：結(jié)論：適用原始數(shù)據(jù)基本有序或數(shù)據(jù)量不大的情況。2021/5/916

希爾排序（Shell’smethod）又稱為“縮小增量排序”，本質(zhì)上講是插入排序，它是對線性插入排序的改進(jìn)。其基本思想是：

先取一個(gè)小于n的整數(shù)d1并作為第一個(gè)增量，將文件的全部記錄分成d1個(gè)組，所有距離為d1倍數(shù)的記錄放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序；

然后取第二個(gè)增量d2<d1，重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt1<…<d2<d1)為止，此時(shí)，所有的記錄放在同一組中進(jìn)行直接插入排序。2希爾插入排序——算法思想2021/5/917如何選擇增量序列才能產(chǎn)生最好的排序效果，這個(gè)問題至今沒有得到解決。希爾本人最初提出取d1=n/2，di+1=di/2，dt=1，t=log2n。2021/5/918希爾插入排序——步驟（1）首先選取一個(gè)整數(shù)d1<n（n為待排序數(shù)據(jù)的個(gè)數(shù)），作為兩個(gè)數(shù)據(jù)之間的距離，這樣把全部數(shù)據(jù)分成d1個(gè)組，凡是距離為d1的數(shù)據(jù)放在一個(gè)組里，在各組內(nèi)進(jìn)行內(nèi)部排序，直到各組排好序?yàn)橹?。?）從上述的結(jié)果序列出發(fā)，再選擇d2<d1，重復(fù)上面的分組與排序工作。（3）依次取di+1<di，直到dm=1（設(shè)一共需要m次分組），即所有數(shù)據(jù)放在一組中排序?yàn)橹?。此時(shí)，全部數(shù)據(jù)便按次序排好了。2021/5/919設(shè)待排序共有10個(gè)記錄，其關(guān)鍵字分別為47,33,61,82,71,11,25,47,57,02，增量序列取值依次為5,3,1。

希爾插入排序——過程2021/5/920

希爾排序?qū)嵸|(zhì)上還是一種插入排序，其主要特點(diǎn)是：每一趟以不同的增量進(jìn)行排序。在每趟的插入排序中，記錄的關(guān)鍵字是和同一組中的前一個(gè)關(guān)鍵字進(jìn)行比較，所以關(guān)鍵字較小的記錄在排序過程中是作跳躍式的移動(dòng)。另外，由于開始時(shí)增量的取值較大，每組中記錄較少，故排序比較快，隨著增量值的逐步變小，每組中的記錄逐漸變多，但由于此時(shí)記錄已基本有序了，因次在進(jìn)行最后一趟增量為1的插入排序時(shí)，只需作少量的比較和移動(dòng)便可完成排序，從而提高了排序速度。

希爾插入排序——特點(diǎn)

2021/5/921

希爾排序比直接插入排序的平均性能要好：在最好情況（原始記錄按關(guān)鍵字有序排列）下，移動(dòng)次數(shù)為0，比較次數(shù)界于n～n2

之間。在最壞情況（原始記錄按關(guān)鍵字逆序排列）下，移動(dòng)次數(shù)和比較次數(shù)接近n2。在平均情況下，移動(dòng)次數(shù)和比較次數(shù)在O（n1.3）左右，好于直接插入排序。希爾插入排序——性能效率2021/5/922例1.19希爾排序的程序

#include"stdio.h"#definemax10intdata[max+1];intindex[max+1];inti;2021/5/923voidshell_sort(a)inta[max+1];{ inti,j,n,m,skip;intalldone; for(i=1;i<=max;i++) index[i]=i; skip=max; while(skip>1) {skip=skip/2; do{alldone=1; for(j=1;j<=max-skip;j++) {i=j+skip;n=index[i];m=index[j]; if(a[n]<a[m]) { index[i]=m;index[j]=n; alldone=0; } } }while(alldone==0); }}2021/5/924main(){printf("請輸入數(shù)據(jù):");for(i=1;i<=max;i++) scanf("%d",&data[i]);printf("\n");for(i=1;i<=max;i++) printf("%d",data[i]);printf("\n");shell_sort(data);for(i=1;i<=max;i++) printf("%d",data[index[i]]);printf("\n");}2021/5/925運(yùn)行結(jié)果：請輸入數(shù)據(jù):194111174743133731231941111747431337312311131719233137414347

希爾排序的分析較為復(fù)雜，因?yàn)樗臅r(shí)間是所取“增量”序列的函數(shù)，這涉及到一些數(shù)學(xué)上尚未解決的難題。增量序列可以有各種取法，但需注意：應(yīng)使增量序列中的值沒有除1以外的公因子，并且最后一個(gè)增量值必須等于1。2.希爾排序2021/5/926三、交換排序

兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。冒泡排序快速排序2021/5/927假設(shè)在排序過程中，記錄序列L.r[1..n]的狀態(tài)為：第i趟冒泡排序無序序列L.r[1..n-i+1]有序序列L.r[n-i+2..n]n-i+1無序序列L.r[1..n-i]有序序列L.r[n-i+1..n]比較相鄰記錄，將關(guān)鍵字最大的記錄交換到

n-i+1的位置上7.3.1冒泡排序——基本思想和過程2021/5/928voidBubbleSort(SqList*L){for(i=L->length;i>1;--i){

for(j=1;j<i;++j)

if(L->r[j+1]<L->r[j]){Swap(L->r[j],L->r[j+1]);}}}時(shí)間性能分析：比較次數(shù):最壞(n-1)+(n-2)+...+1;最好：n-1

移動(dòng)次數(shù):最壞：3((n-1)+(n-2)+...+1)；最好：07.3.1冒泡排序——算法和性能分析2021/5/9292553157989i=7i=6for(j=1;j<i;j++)if(L->r[j+1]<L->r[j])…13i=27.3.1冒泡排序——改進(jìn)2021/5/930voidBubbleSort(SqList*L){i=L->length;while(i>1){//定位第i個(gè)位置的記錄

lastExchangeIndex=1;

for(j=1;j<i;++j)

if(L->r[j+1]<L->r[j]){Swap(L->r[j],L->r[j+1]);lastExchangeIndex=j;} i=lastExchangeIndex;}}7.3.1冒泡排序——改進(jìn)算法2021/5/931最好情況（記錄按關(guān)鍵字有序排列）：只需進(jìn)行一趟冒泡“比較”的次數(shù)：最壞情況（記錄按關(guān)鍵字逆序排列）：需進(jìn)行n-1趟冒泡“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：n-17.3.1冒泡排序——性能分析2021/5/932

首先對無序的記錄序列進(jìn)行“一次劃分”，通過一趟排序?qū)⒋判蛄蟹殖蓛刹糠郑蛊渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分小，再分別對這兩部分排序，以達(dá)到整個(gè)序列有序。無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進(jìn)行快速排序7.3.2快速排序——基本思想2021/5/933快速排序——目標(biāo)找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄移至該記錄之前，反之，移至該記錄之后。一趟排序之后，無序序列L.r[low..high]將被分割成兩個(gè)部分：L.r[low..i-1]和L.r[i+1..high]

且L.r[j]≤L.r[i]≤L.r[j](low≤j≤i-1)

樞軸

(i+1≤j≤high)。2021/5/934快速排序——方法關(guān)鍵字通常取第一個(gè)記錄的值為基準(zhǔn)值。方法：附設(shè)兩個(gè)指針i和j

，初值分別指向第一個(gè)記錄和最后一個(gè)記錄，設(shè)關(guān)鍵字為

key

，首先從

j所指位置起向前搜索，找到第一個(gè)小于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換，然后從i

所指位置起向后搜索，找到第一個(gè)大于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換，重復(fù)這兩步直至i=j為止。初始值4655134294517702021/5/935快速排序一趟算法初始值465513429451770ij175513429451770175513429455570基準(zhǔn)X=4617513429455570移動(dòng)jij移動(dòng)ij移動(dòng)jiii17513429494557017513429494557046ijiiii2021/5/936第一趟

135174246945570快速排序例初始值465513429451770第二趟

513174246705594第三趟

513174246557094第四趟

5131742465570942021/5/937快速排序——步驟(1)令指針L＝1，R＝n

，即分別指向A1和An；(2)自尾端開始進(jìn)行比較：將AR與AL比較，若AL＜AR，則數(shù)據(jù)就不交換，此時(shí)固定L（即L指針不動(dòng)），調(diào)整尾指針，使R＝R-1。繼續(xù)比較，直至AL＞AR時(shí)為止，將AR與AL交換位置，并修改左指針，使L＝L+1；(3)將AL與AR比較，若AL＜AR，則調(diào)整左指針，使L＝L+1，R指針不動(dòng)。繼續(xù)比較，直至AL＞AR時(shí)為止，將AL與AR交換位置，并修改右指針R，使R＝R-1；(4)重復(fù)(2)(3)步驟，直到從兩邊開始的掃描在中間相遇，即L、R指針重合于中間某一個(gè)元素，此時(shí)該元素即在排序的序列中找到了自己合適的位置，并且此元素將原序列分成了前后兩個(gè)子集。雖然此時(shí)這兩個(gè)子集還是無序的，但前一個(gè)子集的所有元素均小于后一個(gè)子集的所有元素。這稱為一趟。2021/5/938設(shè)L.r[low]=46為樞軸，在調(diào)整過程中，設(shè)立兩個(gè)指針：low和high，之后逐漸減小high或增加low，并保證：將L.r[high]和樞軸的關(guān)鍵字進(jìn)行比較，要求L.r[high]≥樞軸的關(guān)鍵字將L.r[low]和樞軸的關(guān)鍵字進(jìn)行比較，要求L.r[low]≤樞軸的關(guān)鍵字L.r[high]≥樞軸且L.r[low]≤樞軸,否則進(jìn)行記錄的“交換”。2021/5/939快速排序算法voidquicksort(intr[],intleft,intright){ inti=left,j=right; intx=r[i]; while(i<j) {while((r[j]>=x)&&(j>i))j=j-1;//向前比較

r[i]=r[j];//比x小的元素左移

while((r[i]<=x)&&(j>i))i=i+1;//向后比較

r[j]=r[i];}//比x大的元素右移

r[i]=x;//基準(zhǔn)值x歸位

quicksort(r,left,i-1);//遞歸調(diào)用左子區(qū)間

quicksort(r,i+1,right);//遞歸調(diào)用右子區(qū)間}leftrighti2021/5/940快速排序的時(shí)間主要耗費(fèi)在劃分操作上，對長度為k的區(qū)間進(jìn)行劃分，共需k-1次關(guān)鍵字的比較。最壞情況是每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最大)的記錄，劃分的結(jié)果是基準(zhǔn)左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個(gè)非空的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個(gè)數(shù)減少一個(gè)。因此，快速排序必須做n-1次劃分，第i次劃分開始時(shí)區(qū)間長度為n-i+1，所需的比較次數(shù)為n-i(1≤i≤n-1)，故總的比較次數(shù)達(dá)到最大值：n(n-1)/2=O(n2)快速排序——時(shí)間分析2021/5/941在最好情況下，每次劃分所取的基準(zhǔn)都是當(dāng)前無序區(qū)的“中值”記錄，劃分的結(jié)果是基準(zhǔn)的左、右兩個(gè)無序子區(qū)間的長度大致相等?？偟年P(guān)鍵字比較次數(shù)：

O(nlogn)因?yàn)榭焖倥判虻挠涗浺苿?dòng)次數(shù)不大于比較的次數(shù)，所以快速排序：最壞時(shí)間復(fù)雜度應(yīng)為O(n2)

最好時(shí)間復(fù)雜度為O(nlogn)

平均時(shí)間復(fù)雜度為O(nlogn)快速排序——時(shí)間分析2021/5/942

快速排序在系統(tǒng)內(nèi)部需要一個(gè)棧來實(shí)現(xiàn)遞歸。若每次劃分較為均勻，則其遞歸樹的高度為O(logn)，故遞歸后需棧空間為O(logn)。最壞情況下，遞歸樹的高度為O(n)，所需的?？臻g為O(n)。因?yàn)榭焖倥判虻膭澐执螖?shù)在logn～n之間，所以快速排序的：最壞空間復(fù)雜度應(yīng)為O(n)

最好空間復(fù)雜度為O(logn)

平均空間復(fù)雜度為O(logn)快速排序——空間分析2021/5/943若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼嘶癁槊芭菖判?，其時(shí)間復(fù)雜度為O(n2)。因此，快速排序適用于原始數(shù)據(jù)雜亂無章的傾向。輔助空間數(shù)量為遞歸調(diào)用所開辟的棧空間。7.3.2快速排序——適用范圍結(jié)論:快速排序的時(shí)間復(fù)雜度為O(nlogn)且適用于原始數(shù)據(jù)雜亂無章的情況?？焖倥判蚴欠欠€(wěn)定的。

2021/5/944快速排序的程序：#include"stdio.h"#definen10intar[n+1];inti,l1;intquick1(a,l,r)inta[n+1];intl,r;/*指針*/{intl1;intr1,w; l1=l;r1=r;w=a[l1];do{while((a[r1]>=w)&&(l1<r1))r1=r1-1; if(l1<r1) {a[l1]=a[r1];l1=l1+1; while((a[l1]<=w)&&(l1<r1))l1=l1+1; if(l1<r1) {a[r1]=a[l1];r1=r1-1;} } }while(l1!=r1); a[l1]=w;return(l1);}2021/5/945voidq_sort(a,l,r)inta[n+1];intl,r; {intl1; if(l<r) {l1=quick1(a,l,r); q_sort(a,l,l1-1); q_sort(a,l1+1,r); } }2021/5/946main(){printf("請輸入數(shù)據(jù):\n");for(i=1;i<=n;i++)scanf("%d",&ar[i]);q_sort(ar,1,n);printf("排序后的序列:\n");for(i=1;i<=n;i++) { printf("%d",ar[i]); if(i%5==0)printf("\n"); }}運(yùn)行結(jié)果：請輸入數(shù)據(jù):42237411655894369987排序后的序列:112336425865748794992021/5/9472021/5/9482021/5/9492021/5/95023,10,20,36,40,13,27,1111,10,20,13,

23,40,27,3610,

11,20,13,23,40,27,3610,11,13,

20,23,40,27,3610,11,13,20,23,36,27,4010,11,13,20,23,27,

36,4010,11,20,13,

23,40,27,3610,11,13,20,23,40,27,367.3.2快速排序——過程2021/5/9517.4選擇排序簡單選擇排序堆排序2021/5/952假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列L.r[1..i-1]無序序列L.r

[i..n]

第i趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列L.r[1..i]無序序列

L.r[i+1..n]7.4.1簡單選擇排序——基本思想和過程2021/5/953四、選擇排序直接選擇排序又稱為簡單選擇排序，是一種簡單直觀的排序方法。從待排序的所有記錄中，選取關(guān)鍵字最小的記錄，并將它與原始序列中的第一個(gè)記錄交換，然后從去掉了關(guān)鍵字最小記錄的剩余記錄中選擇關(guān)鍵字最小的記錄將它與原始記錄序列的第二個(gè)記錄交換位置，以此類推，直到序列中全部記錄排序完畢。2021/5/9542021/5/955算法：//對記錄序列x[0]~x[n-1]進(jìn)行直接選擇排序

voidselectsort(elemtypex[],intn) { inti,j,small; elemtypeswap; for(i=0;i<n-1;i++) {small=i; for(j=i+1;j<n;j++) { if(x[j].key<x[small].key) small=j;} if(small!=i) { swap=x[i];X[i]=x[small];X[small]=swap;} }}2021/5/956對n個(gè)記錄進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)總計(jì)為：移動(dòng)記錄的次數(shù)，最小值為0,

最大值為3(n-1)。7.4.1簡單選擇排序——算法時(shí)間性能分析2021/5/957堆就是一個(gè)關(guān)鍵字序列：并且這n個(gè)關(guān)鍵字的序列K1,K2...Kn要滿足以下性質(zhì)(堆性質(zhì))，就是: Ki≥K2i且Ki≥K2i+1或者

Ki≤K2i且Ki≤K2i+12、堆排序——堆的定義(正堆)(逆堆){12,36,27,65,40,34,98,81,73,55,49}是正堆{12,36,27,65,40,14,98,81,73,55,49}不是堆12345678910112021/5/958當(dāng)把這個(gè)序列存入一個(gè)向量并把它看作是一棵完全二叉樹的存儲結(jié)構(gòu)時(shí)，堆就是這樣一棵二叉樹：任一非葉結(jié)點(diǎn)的關(guān)鍵字均不小于(或不大于)其左右孩子結(jié)點(diǎn)的關(guān)鍵字。2、堆排序1236276549817355403498是堆14不2021/5/959123456789470174642550513堆最大值2021/5/960897624331510112536497856a)堆頂元素取最大值 大根堆b)堆頂元素取最小值 小根堆2021/5/961堆排序基本思想因?yàn)槎秧斒亲畲蟮臄?shù)，所以當(dāng)把一個(gè)關(guān)鍵字序列排成一個(gè)大根堆時(shí)，就很容易地找到最大的數(shù)，它就在序列的第一個(gè)位置上然后把這個(gè)最大的數(shù)與最后一個(gè)記錄交換，這時(shí)，最后一個(gè)記錄就是關(guān)鍵字最大的記錄了。對于剩下的關(guān)鍵字序列，我們?nèi)匀话阉懦梢粋€(gè)大根堆，然后再把第一個(gè)記錄(當(dāng)前堆中的堆頂)與當(dāng)前堆的最后一個(gè)記錄交換。這時(shí)，在整個(gè)序列后面就有了兩個(gè)有序的關(guān)鍵字(從小到大)。重復(fù)這樣的過程，就可以把有序區(qū)不斷擴(kuò)大直到全部關(guān)鍵字都進(jìn)入有序區(qū)。直到排序完成。9470174642550513初始堆427017469455051313551746944205702021/5/962堆的構(gòu)造無序序列r[1：n]構(gòu)成的完全二叉樹。從它最后一個(gè)非葉子結(jié)點(diǎn)（第n/2個(gè)元素）開始直到根結(jié)點(diǎn)為止，逐步進(jìn)行調(diào)整即可將此完全二叉樹構(gòu)成堆。調(diào)整：與其左右子樹根結(jié)點(diǎn)值比較，取其中大的進(jìn)行交換。2021/5/963堆的構(gòu)造例4655134270940517465513429405177070175944213554612345678123456782021/5/9644655137042940517465513427094051770175944213554612345678對調(diào)對調(diào)42175947013554612345678對調(diào)對調(diào)1313堆的構(gòu)造例46551342940517702021/5/965465517704294051342135947017554612345678對調(diào)5555對調(diào)469417704255051342135557017944612345678對調(diào)4646對調(diào)堆的構(gòu)造例46551342940517702021/5/966944617704255051342135557017469412345678對調(diào)4646對調(diào)947017464255051342135554617709412345678成堆!堆的構(gòu)造例46551342940517702021/5/9674655134270940517初始無序結(jié)點(diǎn),從42開始調(diào)整4655137042940517將以13為根的子樹調(diào)整成堆4655177042940513將以55為根的子樹調(diào)整成堆堆的構(gòu)造例46551342940517702021/5/9684694177042550513將以46為根的子樹調(diào)整成堆9470174642550513成堆2021/5/969調(diào)整成堆算法voidSIFT(intr[],inti,intn)//調(diào)整r[1:n]中結(jié)點(diǎn)r[i],使成為一個(gè)堆{ intj; intT; T=r[i];j=2*i;//j為i結(jié)點(diǎn)的左孩子序號

while(j<n) {if((j<n)&&(r[j]<r[j+1]))j++;//找出i的大孩子

if(T<r[j])//孩子大于雙親

{r[i]=r[j]; i=j;j=2*i;} elsej=n;//退出while r[i]=T; }}ijT2021/5/970堆排序由給定的無序序列構(gòu)造堆將堆頂元素與堆中最后一個(gè)元素交換將最后一個(gè)元素從堆中刪除將余下的元素構(gòu)成完全二叉樹重新調(diào)整成堆反復(fù)進(jìn)行，直到堆空2021/5/971堆排序過程示例9470174642550513初始堆4270174694550513705517469442051394與42交換前7個(gè)元素重新建堆9413555461770422021/5/97213551746944205705546171394420570054617139442557070與13交換前6個(gè)元素重新建堆55與05交換9470542461755139470554213174652021/5/973464217139405557005421713944655704213170594465570前5個(gè)元素重新建堆46與05交換947055461317425前4個(gè)元素重新建堆2021/5/97405131742944655701713054294465570051317429446557042與05交換947055464217135前3個(gè)元素重新建堆17與05交換9470554642171352021/5/97513051742944655700513174294465570前2個(gè)元素重新建堆13與05交換947055464217135堆排序結(jié)果2021/5/976堆排序過程941355546177042947054246175513947055421317465947055461317425947055464217135947055464217135947055464217135第一趟結(jié)果:第二趟結(jié)果:第三趟結(jié)果:第四趟結(jié)果:第五趟結(jié)果:第六趟結(jié)果:第七趟結(jié)果:2021/5/977堆排序算法voidheapsort(intr[],intn)//堆排序{ intt; for(inti=n/2;i>=0;i--)//將r調(diào)整成堆

SIFT(r,i,n); for(i=n-1;i>=0;i--) { t=r[0]; r[0]=r[i]; r[i]=t; SIFT(r,0,i-1);}}i02021/5/978堆排序的程序：#include"stdio.h"#definemm8inta[mm+1];intk;voidshift(a,l,m)voidheapsort(a)inta[mm+1];{ inti,x; for(i=mm/2;i>=1;i--) shift(a,i,mm);/*從第開始進(jìn)行篩選建堆*/ for(i=mm;i>=2;i--) {x=a[1];a[1]=a[i];a[i]=x;

/*將堆頂元素和堆中最后一個(gè)元素交換*/ shift(a,1,i-1);/*調(diào)整第一個(gè)元素使之重又成為堆*/ }}2021/5/979main(){printf("請輸入數(shù)據(jù):\n");for(k=1;k<=mm;k++) scanf("%d",&a[k]);printf("初始數(shù)據(jù):\n");for(k=1;k<=mm;k++) printf("a[%d]=%d",k,a[k]);printf("\n");heapsort(a);printf("排序后的數(shù)據(jù):\n");for(k=1;k<=mm;k++) printf("|a[%d]=%d|",k,a[k]);printf("\n");}2021/5/980五、基數(shù)排序

前面介紹的幾種排序方法都是按數(shù)據(jù)元素（或記錄關(guān)鍵字）值的大小進(jìn)行排序的

而多關(guān)鍵字排序是一種按組成數(shù)據(jù)元素或關(guān)鍵字的各位值進(jìn)行排序的方法，基數(shù)排序借助的就是這種思想，它屬于分布式排序，也稱口袋排序。

基數(shù)排序是把邏輯關(guān)鍵字看成由若干個(gè)子關(guān)鍵字復(fù)合而成的

→假設(shè)有n個(gè)關(guān)鍵字｛r1，r2，…，rn｝需進(jìn)行排序

→每個(gè)關(guān)鍵字由d元組（k1k2k3…kd）子關(guān)鍵字組成，k1是關(guān)鍵字值的最高位，kd是關(guān)鍵字值的最低位，其基數(shù)為rd2021/5/981五、基數(shù)排序

前面介紹的幾種排序方法都是按數(shù)據(jù)元素（或記錄關(guān)鍵字）值的大小進(jìn)行排序的

多關(guān)鍵字排序是一種按組成數(shù)據(jù)元素或關(guān)鍵字的各位值進(jìn)行排序的方法，基數(shù)排序借助的就是這種思想?；鶖?shù)排序?qū)儆诜植际脚判?，也稱口袋排序、“桶子法”

?；鶖?shù)排序法是屬于穩(wěn)定性的排序時(shí)間復(fù)雜度為O(nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的比較性排序法。

2021/5/982基數(shù)排序的方式可以采用：LSD（Leastsignificantdigital）的排序方式由鍵值的最右邊開始MSD（Mostsignificantdigital）由鍵值的最左邊開始。以LSD為例，假設(shè)原來有一串?dāng)?shù)值如下所示：

73,22,93,43,55,14,28,65,39,81

2021/5/98373,22,93,43,55,14,28,65,39,81首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值時(shí)將它們分配至編號0到9的桶子中；接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：

81,22,73,93,43,14,55,65,28,392021/5/98481,22,73,93,43,14,55,65,28,39接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配：接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：整個(gè)數(shù)列已經(jīng)排序完畢。14,22,28,39,43,55,65,73,81,932021/5/985如果排序的對象有三位數(shù)以上，則持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。LSD的基數(shù)排序適用于位數(shù)小的數(shù)列，如果位數(shù)多的話，使用MSD的效率會比較好；MSD的方式恰與LSD相反，是由高位數(shù)為基底開始進(jìn)行分配，其他的演算方式則都相同。2021/5/986基數(shù)排序→排序前先將待排序元素置于一數(shù)組r[1]～r[n]中存儲，每個(gè)結(jié)點(diǎn)除存放排序碼的值外，還有一個(gè)指向下一個(gè)結(jié)點(diǎn)的指針（即下一個(gè)結(jié)點(diǎn)的下標(biāo)值）→排序時(shí)從最低位kd開始，直到最高位k1，把關(guān)鍵字依其子關(guān)鍵字的值分配到rd個(gè)隊(duì)列中去，同一隊(duì)列中的元素用指針鏈接，同時(shí)隊(duì)頭和隊(duì)尾各用一個(gè)指針指示，該頭、尾指針分別存放在兩個(gè)數(shù)組f[ra1]～f[ra2]和e[ra1]～e[ra2]中（ra1和ra2為子關(guān)鍵字ki的取值范圍）→每經(jīng)過一次分配后，都將各隊(duì)列中的元素按次序收集在一起，經(jīng)過d次的分配和收集后即得到了按序排列的序列2021/5/987基數(shù)排序例如，若關(guān)鍵字是十進(jìn)制數(shù)值，將全部數(shù)據(jù)放在數(shù)組r中，然后按下列步驟進(jìn)行：（1）初態(tài)：設(shè)置10個(gè)隊(duì)列，并且使其均為空。（2）分配：依次從數(shù)組r中取出每個(gè)關(guān)鍵字，第i遍處理時(shí)，考察該關(guān)鍵字右起第i位數(shù)字（即第i個(gè)子關(guān)鍵字），設(shè)其值位k，則把該關(guān)鍵字插入第k個(gè)隊(duì)列。數(shù)組r全部處理完后，全部數(shù)據(jù)被分配到隊(duì)列0～隊(duì)列9。（3）收集：從隊(duì)列0開始，依隊(duì)列0～隊(duì)列9的頭、尾指針，修改數(shù)組r中各關(guān)鍵字的指針，即將這次分配完的關(guān)鍵字依邏輯次序再鏈接起來。（4）循環(huán)：重復(fù)以上（1）～（3）步，若關(guān)鍵字有d位數(shù)字，就需要執(zhí)行d遍。2021/5/988基數(shù)排序●考察由3位十進(jìn)制數(shù)字組成的關(guān)鍵字，則其值在0≤k≤999范圍內(nèi)?！砂衙恳粋€(gè)十進(jìn)制數(shù)看成一個(gè)邏輯關(guān)鍵字k，→k由三個(gè)子關(guān)鍵字（k1、k2、k3）組成，其中k1是百位數(shù)，k2是十位數(shù)，k3是個(gè)位數(shù)，由此分解得到的每個(gè)關(guān)鍵字ki都在相同的范圍內(nèi)（0≤ki≤9）?！判蚴窍葟淖畹臀籯3開始，按k3的大小分成若干組，每組中k3值相同，然后將各組數(shù)據(jù)收集在一起；→下次再按k2大小排序，→如此重復(fù)，直到對k1排序后，整個(gè)數(shù)據(jù)集即成為有序序列。2021/5/989基數(shù)排序例1.22基數(shù)排序過程的程序設(shè)有10個(gè)十進(jìn)制數(shù)：179、208、234、056、800、178、651、245、006、958，該數(shù)列數(shù)值范圍在0～999之間，因此子關(guān)鍵字位數(shù)d＝3，個(gè)位數(shù)為低關(guān)鍵字位，百位數(shù)為高關(guān)鍵字位，關(guān)鍵字值得范圍為0～9，基數(shù)為10。進(jìn)行基數(shù)排序過程如圖1.61所示。r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]r[10]→179→208→234→056→800→178→651→245→006→958（a）初始狀態(tài)2021/5/990（b）按最低關(guān)鍵字位值分配→800→651→234→245→056→006→208→178→958→179（c）第一次收集2021/5/991（d）按次低關(guān)鍵字位值分配→800→006→208→234→245→651→056→958→178→179（e）第二次收集2021/5/992（f）按最高關(guān)鍵字位值分配→006→056→178→179→208→234→245→651→800→958（g）第三次收集后得排序結(jié)果圖1.61基數(shù)排序示例2021/5/993基數(shù)排序的程序：

#include"stdio.h"#definera10#definera29#defined3#definen10intkeyval;/*ra1<=keyval<=ra2*/intpn;/*1<=pn<=n*/structrnode{intkey[4];/*keyval*/ intnext;/*0<=next<=n*/};structrnoder[n+1];2021/5/994intrsort(r)structrnoder[n+1];{ intj,k,t,i;intf[10],e[10];/*0..9*/intp;p=1; for(i=d;i>=1;i--) {for(j=ra1;j<=ra2;j++)f[j]=0;/*頭指針初始化*/ while(p!=0)/*分配*/ {k=r[p].key[i]; if(f[k]==0)f[k]=p;elser[e[k]].next=p; e[k]=p;p=r[p].next; } j=0;/*收集*/ while(f[j]==0)j=j+1;p=f[j];t=e[j]; while(j<ra2) {j=j+1;if(f[j]!=0){r[t].next=f[j];t=e[j];}} r[t].next=0; } return(p);}2021/5/995main(){intp;inti,j;printf("請輸入數(shù)據(jù)：");for(i=1;i<=n;i++) {for(j=1;j<=3;j++) {scanf("%d",&r[i].key[j]); printf("%d",r[i].key[j]); } printf(""); scanf("%d",&r[i].next);printf("%d|",r[i].next); }printf("\n");p=rsort(r);printf("排序后的數(shù)據(jù):\n");while(p!=0) {for(j=1;j<=3;j++) printf("%d",r[p].key[j]);printf("");p=r[p].next; }printf("\n");}2021/5/996

基數(shù)排序運(yùn)行結(jié)果：請輸入數(shù)據(jù)：179