數(shù)據(jù)結(jié)構(gòu)與算法實踐指導(dǎo) 課件 8-排序

第8章

排序8.1知識簡介

排序是按照關(guān)鍵字的非遞減或非遞增順序?qū)σ唤M記錄重新排列的操作。當(dāng)排序記錄中的關(guān)鍵字Ki都不相同時，則任何一個記錄的無序序列經(jīng)排序后得到的結(jié)果唯一；反之，當(dāng)待排序的序列中存在兩個或兩個以上關(guān)鍵字相等的記錄時，則排序所得的結(jié)果不唯一。假設(shè)Ki≠Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri領(lǐng)先于Rj（即i<j）。若在排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中Rj領(lǐng)先于Ri，則稱所用的排序方法是不穩(wěn)定的。8.1.1排序的基本概念8.1知識簡介

根據(jù)在排序過程中記錄所占用的存儲設(shè)備，可將排序方法分為內(nèi)部排序和外部排序。本實驗掌握內(nèi)部排序。8.1.1排序的基本概念

內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。根據(jù)逐步擴大記錄有序序列長度的原則不同，內(nèi)部排序可分為插入類、交換類、選擇類、歸并類和分配類。

插入類排序主要有直接插入排序、折半插入排序、希爾排序。

交換類排序主要有冒泡排序和快速排序。

選擇類排序主要有簡單選擇排序、樹型選擇排序和堆排序。

最常見的歸并類排序是2路歸并排序。

基數(shù)排序是主要的分配類排序方法。8.1知識簡介

在線性表的查找中，順序查找既適用于線性表的順序存儲結(jié)構(gòu)，用適用于線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，折半查找要求線性表必須是順序存儲結(jié)構(gòu)，分塊查找的表可以是順序存儲結(jié)構(gòu)也可以是鏈?zhǔn)酱鎯Y(jié)構(gòu)，但索引表必須是順序存儲結(jié)構(gòu)。8.1.2待排序記錄的存儲方式

待排序記錄的主要存儲方式有：

第一種是順序表：記錄之間的次序關(guān)系由其存儲位置決定，排序時需要移動記錄；

第二種是鏈表：記錄之間的次序關(guān)系由指針表示，排序時不需要移動記錄，只需修改指針；8.1知識簡介

在線性表的查找中，順序查找既適用于線性表的順序存儲結(jié)構(gòu)，用適用于線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，折半查找要求線性表必須是順序存儲結(jié)構(gòu)，分塊查找的表可以是順序存儲結(jié)構(gòu)也可以是鏈?zhǔn)酱鎯Y(jié)構(gòu)，但索引表必須是順序存儲結(jié)構(gòu)。8.1.2待排序記錄的存儲方式

第三種是將待排序記錄存儲在一組地址連續(xù)的存儲單元中，同時另設(shè)一個指示各個記錄存儲位置的地址向量，在排序過程中不移動記錄本身，而是移動地址向量中的地址。

待排序記錄的主要存儲方式有：8.1知識簡介

本次實驗主要掌握直接插入排序、希爾排序、直接選擇排序、冒泡排序、快速排序和2路歸并排序。采用順序表存儲方式存儲待排序表，順序表定義如下：8.1.2待排序記錄的存儲方式#defineMAXLEN30//空間的最大長度typedefstruct{ElemTypeR[MAXLEN+1];//順序表中存放元素的數(shù)組，0號單元不存儲數(shù)據(jù)intlength;//順序表的長度，即元素個數(shù)}SqList;//順序表的類型ElemType為數(shù)據(jù)元素的類型，在不同的問題中數(shù)據(jù)元素的類型不同，具體類型根據(jù)問題而定。8.2實驗?zāi)康?/p>

通過本章的實驗，更深入理解各種排序算法的原理和實現(xiàn)過程，通過直觀地分析不同算法的效率，能夠根據(jù)實際需求選擇最合適的排序方法，同時提升編程能力與實踐技巧。8.3實驗范例

已知n個學(xué)生的信息，每個學(xué)生的信息由姓名和分數(shù)組成，要求用直接插入排序?qū)W(xué)生按分數(shù)從高到低排序。8.3.1范例18.3實驗范例1、問題分析8.3.1范例1

先需要定義順序表L，表中各元素（也就是記錄）包括兩個部分：姓名和分數(shù)，需定義結(jié)構(gòu)體類型表示元素類型，結(jié)構(gòu)體成員有兩個，假設(shè)用score存儲分數(shù)，為int類型，name存儲姓名，為char數(shù)組。然后輸入n個學(xué)生的姓名和分數(shù)，存入順序表L中，將順序表的長度length賦值n。接著利用直接插入排序按照分數(shù)從高到低排序。8.3實驗范例1、問題分析8.3.1范例1

直接插入排序的基本步驟：設(shè)第一個元素就是一個有序序列，循環(huán)n-1次，每次使用順序查找法，查找第i個（i=2,…,n）在已排好序的序列中（前i-1個元素）的插入位置，然后將第i個元素插入長度為i-1的有序序列中，直到將第n個元素插入長度為n-1的有序序列中，最后得到一個長度為n的有序序列。8.3實驗范例2、算法描述8.3.1范例1根據(jù)前面的分析，先定義順序表類型，定義如下：#defineMAXLEN30//順序表的最大長度typedefstruct{intscore;charname[20];}ElemType;//數(shù)據(jù)元素類型typedefstruct{//順序表中存放元素的數(shù)組，0號單元不存儲數(shù)據(jù)ElemTypeR[MAXLEN+1];intlength;//順序表的長度，即元素個數(shù)}SqList;//順序表的類型8.3實驗范例2、算法描述8.3.1范例1

順序表類型定義好之后，接著設(shè)計函數(shù)建立長度為n的待排序順序表L，輸入n個學(xué)生的信息存入順序表L的R數(shù)組中，將當(dāng)前長度length設(shè)置為n。函數(shù)可以定義如下：voidcreateSqList(SqList&L,intn){inti;printf("輸入%d個學(xué)生信息（姓名，分數(shù)）：",n);for(i=1;i<=n;i++){fflush(stdin);gets(L.R[i].name);scanf("%d",&L.R[i].score);//輸入各元素}L.length=n;//設(shè)置當(dāng)前長度}8.3實驗范例2、算法描述8.3.1范例1

設(shè)計直接插入排序函數(shù)，對待排序序列中的元素按照分數(shù)進行非遞增排序。函數(shù)可以定義如下：voidinsertSort(SqList&L){inti,j;for(i=2;i<=L.length;++i)if(L.R[i].score>L.R[i-1].score){L.R[0]=L.R[i];//index[0]具有監(jiān)視哨的作用for(j=i-1;L.R[0].score>L.R[j].score;--j)L.R[j+1]=L.R[j];//記錄后移L.R[j+1]=L.R[0];}}8.3實驗范例2、算法描述8.3.1范例1

為了檢驗是否按要求排序，在排序后可以將順序表中的數(shù)據(jù)輸出，需定義函數(shù)用來輸出順序表中的值，函數(shù)可以定義如下：voidprintInfor(SqListL){inti;for(i=1;i<=L.length;i++){printf("%20s%5d\n",L.R[i].name,L.R[i].score);}}8.3實驗范例2、算法描述8.3.1范例1

在main()函數(shù)中定義順序表L，然后調(diào)用createSqList()函數(shù)將n個學(xué)生信息輸入到順序表中，接著調(diào)用insertSort(SqlistL)函數(shù)對順序表中的元素按照分數(shù)從高到低進行排序，然后調(diào)用printfInfo(SqListL)將排序后的順序表中的值輸出。8.3實驗范例2、算法描述8.3.1范例1#include<stdio.h>//在main()之前加入類型定義和函數(shù)定義intmain(){SqListL;//定義順序表Linti;createSqList(L,10);//建立長度為10的順序表insertSort(L);//對順序表L進行排序printf("after:\n");printInfor(L);//輸出排序后的順序表return0;}8.3實驗范例3、算法分析8.3.1范例1

在平均情況下，直接插入排序關(guān)鍵字的比較次數(shù)和移動次數(shù)均為n2/4，因此直接插入排序的時間復(fù)雜度為O(n2)。排序過程中只需要一個記錄的輔助空間，所以空間復(fù)雜度為O(1)。8.3實驗范例

給出n個學(xué)生的考試成績表，每條信息由姓名和分數(shù)組成。用快速排序?qū)W(xué)生按分數(shù)從高到低排序。8.3.2范例28.3實驗范例1、問題分析8.3.2范例2

排序序列中的數(shù)據(jù)元素和范例1中的類型相同。

快速排序的過程為：首先在待排序的記錄序列（r1,r2,…,rn）中選第一個記錄r1，以其作為樞軸，經(jīng)過比較和移動，將所有關(guān)鍵字大于樞軸關(guān)鍵字的記錄均移動至該記錄之前，反之，將所有關(guān)鍵字小于樞軸關(guān)鍵字的記錄均移動至該記錄之后。致使一趟排序之后，樞軸就放到最后排序結(jié)果應(yīng)該在的位置上，并且將待排序的記錄分割成了兩個子序列，對這兩個子序列又遞歸進行快速排序，如此繼續(xù)下去，使每個子序列長度為1為止。8.3實驗范例1、問題分析8.3.2范例2一趟快速排序的步驟為：①

選擇待排序序列中的第一個記錄作為樞軸。將樞軸記錄暫存在下標(biāo)為0的位置。low和high分別存儲待排序表的下界和上屆。②

從表的右邊開始依次向左搜索，找到第一個關(guān)鍵字大于樞軸關(guān)鍵字的記錄，將其移到下標(biāo)為low的位置。③

從表的左邊開始依次向右搜索，找到第一個關(guān)鍵字小于樞軸關(guān)鍵字的記錄，將其移到下標(biāo)為high的位置。④

重復(fù)第②步和第③步，直到low與high相等為止。此時low或high的位置就是樞軸記錄的最終位置，排序序列分成了兩個字表。8.3實驗范例2、算法描述8.3.2范例2

本題中順序表類型的定義和范例1相同，同樣利用函數(shù)createSqList(SqList&L,intn)建立長度為n的待排序表L，輸入n個學(xué)生的信息存入待排序表L的R數(shù)組中，將當(dāng)前長度length設(shè)置為n。利用printfInfo(SqListL)函數(shù)輸出排序后順序表中的值。8.3實驗范例2、算法描述8.3.2范例2

設(shè)計函數(shù)Partition(SqList&L,intlow,inthigh)，將順序表L下標(biāo)從low到high的記錄進行一趟快速排序，并返回此趟樞軸元素的位置。該函數(shù)定義如下：intPartition(SqList&L,intlow,inthigh){//將子表的第一個元素為樞軸，并將關(guān)鍵字值存儲在pivotkey中L.R[0]=L.R[low];intpivotScore=L.R[low].score;while(low<high){//循環(huán)直到low等于highwhile(low<high&&L.R[high].score<=pivotScore)--high;L.R[low]=L.R[high];//將比樞軸大的記錄前移8.3實驗范例2、算法描述8.3.2范例2

設(shè)計函數(shù)Partition(SqList&L,intlow,inthigh)，將順序表L下標(biāo)從low到high的記錄進行一趟快速排序，并返回此趟樞軸元素的位置。該函數(shù)定義如下：L.R[low]=L.R[high];//將比樞軸大的記錄前移while(low<high&&L.R[low].score>=pivotScore)++low;L.R[high]=L.R[low];//將比樞軸小的記錄后移}L.R[low]=L.R[0];returnlow;}8.3實驗范例2、算法描述8.3.2范例2

設(shè)計遞歸函數(shù)qSort(Sqlist&L，intlow,inthigh)對順序表L中的元素按照分數(shù)進行非遞增排序。insertSort(Sqlist&L，intlow,inthigh)函數(shù)的定義如下：voidqSort(SqList&L,intlow,inthigh){if(low<high){

//待排序序列長度大于1//對序列進行一趟排序，確定樞軸的位置pivotlocintpivotloc=Partition(L,low,high);qSort(L,low,pivotloc-1);//對左邊的子表進行排序qSort(L,pivotloc+1,high);//對右邊的子表進行排序}}8.3實驗范例2、算法描述8.3.2范例2

在main()函數(shù)中定義順序表L，然后調(diào)用createSqList()函數(shù)將n個學(xué)生信息輸入到順序表中，接著調(diào)用qSort(SqlistL)函數(shù)對順序表中的元素按照分數(shù)從高到低進行排序，然后調(diào)用printfInfo(SqListL)函數(shù)將排序后的順序表中的值輸出。8.3實驗范例2、算法描述8.3.2范例2#include<stdio.h>//在main()之前加入類型定義和函數(shù)定義intmain(){SqListL;//定義順序表Linti;createSqList(L,10);//建立長度為10的順序表qSort(L);//對順序表L進行排序printf("after:\n");printInfor(L);//輸出排序后的順序表return0;}8.3實驗范例3、算法分析8.3.2范例2

平均情況下，快速排序的時間復(fù)雜度為O(nlog2n)。快速排序是遞歸的，最大遞歸調(diào)用次數(shù)與遞歸樹的深度一致，最好情況下的空間復(fù)雜度為O(log2n)，最壞情況下為O(n)。8.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)1：建立順序表，輸入n個學(xué)生的姓名和成績，將該順序表作為待排序序列，利用直接選擇排序?qū)Υ判蛐蛄邪闯煽儚母叩降瓦M行排序，并輸出排序后的結(jié)果，并分析算法的時間和空間復(fù)雜度。任務(wù)2：建立順序表，輸入n個學(xué)生的姓名和成績，將該順序表作為待排序序列，利用希爾排序?qū)Υ判蛐蛄邪闯煽儚母叩降瓦M行排序，并輸出排序后的結(jié)果，并分析算法的時間和空間復(fù)雜度。任務(wù)3：建立順序表，輸入n個學(xué)生的姓名和成績，將該順序表作為待排序序列，利用2路歸并排序?qū)Υ判蛐蛄邪闯煽儚母叩降瓦M行排序，并輸出排序后的結(jié)果，并分析算法的時間和空間復(fù)雜度。8.5任務(wù)提示

都采用順序表存儲方式，記錄的類型和范例中的類型一致，創(chuàng)建順序表函數(shù)和輸出順序表函數(shù)的定義是一樣的。任務(wù)1提示8.5任務(wù)提示

直接選擇排序的過程為每一趟從待排序的記錄中選出關(guān)鍵字值最大的記錄，按順序放在已排序的記錄序列的后面，直到全部排序完為止。任務(wù)1提示8.5任務(wù)提示任務(wù)1提示voidselectsort(Sqlist&L){

//直接選擇排序//在下標(biāo)為i到L.length的元素中選擇關(guān)鍵字值最大的記錄for(i=1;i<=L.length-1;++i)

{k=i;for(j=i+1;j<=L.length;++j)if(L.R[j].score<L.R[k].score)k=j;//k始終“指向”關(guān)鍵字最大的記錄if(k!=i){temp=L.R[i];L.R[i]=L.R[k];L.R[k]=temp;}}}8.5任務(wù)提示任務(wù)2提示

希爾排序?qū)嵸|(zhì)上是采用分組插入的方法排序。具體做法為：將記錄序列分成若干子序列，分別對每個子序列進行插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。具體做法是：先將n個記錄分成d（d<n）個子序列：{r[1]，r[1+d]，r[1+2d]，…，r[1+kd]}；{r[2]，r[2+d]，r[2+2d]，…，r[2+kd]}；……；{r[d]，r[2d]，r[3d]，…，r[kd]，r[(k+1)d]}。其中，d

稱為增量，它的值在排序過程中從大到小逐漸縮小，一般情況，第一個增量d1取值為n/2，然后依次取di=di-1/2，直至取值為1，由此，希爾排序也叫“縮小增量排序”。然后對每組進行直接插入排序，再對每個增量重復(fù)上述過程，直到增量為1時，最后對全體記錄再做一次直接插入排序。8.5任務(wù)提示任務(wù)2提示voidshellSort(SqList&L){d=L.length/2;//增量賦初始值while(d>0){for(i=1+d;i<=L.length;i+=d)if(L.R[i].score<L.R[i-d].score){L.R[0]=L.R[i];//暫存在R[0]for(j=i-d;j>0&&(L.R[0].score>L.R[j].score);j-=d)L.R[j+d]=L.R[j];//記錄后移，查找插入位置L.R[j+d]=L.R[0];//插入}d=d/2;//增量遞減}}8.5任務(wù)提示

2路歸并排序是將兩個有序子序列“歸并”為一個有序序列。具體做法是：先將n個待排序記錄看成是n個長度為1的有序子表，把相鄰的有序子表進行兩兩歸并，便得到[n/2]個有序表，再將[n/2]個有序的子表兩兩歸并，如此重復(fù)，直到最后得到一個長度為n的有序表為止。任務(wù)3提示8.5任務(wù)提示voidmerge(ElemTyper[],ElemTyper1[],ints,intm,intt)

{i=s;j=m+1;k=s;/*i,j分別指示兩個有序子表中待比較的記錄位置，i的取值范圍是s到m,j的取值范圍是m+1到t,k指示歸并過程中r1的記錄位置*/while(i<=m&&j<=t)if(r[i].score>r[j].score)r1[k++]=r[i++];elser1[k++]=r[j++];任務(wù)3提示

將兩個相鄰的有序子表r[s...m]和r[m+1...t]進行歸并形成一個有序表r1。函數(shù)可以定義如下：8.5任務(wù)提示voidmerge(ElemTyper[],ElemTyper1[],ints,intm,intt)

{任務(wù)3提示……

while(i<=m)//將前一子表的剩余部分復(fù)制到r1r1[k++]=r[i++];while(j<=t)//將后一子表的剩余部分復(fù)制到r1r