數(shù)據結構-第10章-內排序

數(shù)據結構李云清楊慶紅揭安全人民郵電出版社高等學校精品課程（省級）國家十二五規(guī)劃教材高等學校精品課程（省級）國家十二五規(guī)劃教材揭安全jieanquan@163.com江西師范大學計算機信息工程學院第10章內排序交換排序

冒泡排序快速排序直接選擇排序堆排序第十章內排序插入排序直接插入排序二分插入排序希爾排序選擇排序歸并排序基數(shù)排序排序是數(shù)據處理過程中經常使用的一種重要的運算，排序的方法有很多種，本章主要討論內排序的各種算法，并對每個排序算法的時間和空間復雜性以及算法的穩(wěn)定性等進行了討論。10.1排序的基本概念

假設一個文件是由n個記錄R1，R2，…，Rn組成，所謂排序就是以記錄中某個(或幾個)字段值不減(或不增)的次序將這n個記錄重新排列，稱該字段為排序碼。能唯一標識一個記錄的字段稱為關鍵碼，關鍵碼可以作為排序碼，但排序碼不一定要是關鍵碼。

按排序過程中使用到的存儲介質來分，可以將排序分成兩大類:內排序和外排序。

內排序是指在排序過程中所有數(shù)據均放在內存中處理，不需要使用外存的排序方法。而對于數(shù)據量很大的文件，在內存不足的情況下，則還需要使用外存，這種排序方法稱為外排序。

排序碼相同的記錄，若經過排序后，這些記錄仍保持原來的相對次序不變，稱這個排序算法是穩(wěn)定的。否則，稱為不穩(wěn)定的排序算法。評價排序算法優(yōu)劣的標準：首先考慮算法執(zhí)行所需的時間，這主要是用執(zhí)行過程中的比較次數(shù)和移動次數(shù)來度量；其次考慮算法執(zhí)行所需要的附加空間。當然，保證算法的正確性是不言而喻的，可讀性等也是要考慮的因素。/****************************************//*常見排序算法的頭文件，文件名table.h*//***************************************/#defineMAXSIZE100 /*文件中記錄個數(shù)的最大值*/typedefintkeytype; /*定義排序碼類型為整數(shù)類型*/typedefstruct{keytypekey;intother; /*此處還可以定義記錄中除排序碼外的其他域*/}recordtype; /*記錄類型的定義*/typedefstruct{recordtyper[MAXSIZE+1];intlength; /*待排序文件中記錄的個數(shù)*/}table; /*待排序文件類型*/voidinit(table*L)/*順序表初始化函數(shù)*/{inti;srand(time(NULL)); L->length=10; for(i=1;i<=10;i++) L->r[i].key=rand(i)%100;}voidprint(tableL)/*順序表輸出函數(shù)*/{inti,k=0;for(i=1;i<=L.length;i++){printf("%4d",L.r[i].key);if(++k%10==0)printf("\n");}printf("\n");}/*順序表文件輸入函數(shù)*/voidinput(table*L,char*f){inti;FILE*fp;fp=fopen(f,"r");if(fp){fscanf(fp,"%d",&L->length);for(i=1;i<=L->length;i++)fscanf(fp,"%d",&L->r[i].key);}elseL->length=0;}10503020901070804060100一個輸入文件的例子10.2插入排序插入排序的基本方法是:將待排序文件中的記錄，逐個地按其排序碼值的大小插入到目前已經排好序的若干個記錄組成的文件中的適當位置，并保持新文件有序。10.2.1直接插入排序直接插入排序算法的思路是:初始可認為文件中的第1個記錄己排好序，然后將第2個到第n個記錄依次插入已排序的記錄組成的文件中。在對第i個記錄Ri進行插入時，R1，R2，…，Ri-1已排序，將記錄Ri的排序碼keyi與已經排好序的排序碼從右向左依次比較，找到Ri應插入的位置，將該位置以后直到Ri-1各記錄順序后移，空出該位置讓Ri插入。直接插入排序演示012345621254925*1608i=321254925*16080123456初態(tài)490123456212525*1608i=249250123456i=6i=52125080123456214925*160801234564925*1621254925*1608i=425*160825214925*1608完成25習題：給出初始數(shù)列{47，28，32，15，94，33，14，16}在直接插入排序下的狀態(tài)變化過程。4728321594331416初態(tài)：i=2i=3i=4i=5i=6i=72847321594331416283247159433141615283247943314161528324794331416152832334794141614152832334797161415162832334797i=8voidinsertsort(table*L)/*直接插入排序*/{inti,j;for(i=2;i<=L->length;i++){j=i-1;L->r[0]=L->r[i];/*放置哨兵*/while(L->r[j].key>L->r[0].key){ L->r[j+1]=L->r[j]; j--;}L->r[j+1]=L->r[0];}}算法10.1直接插入排序算法直接插入排序算法執(zhí)行時間的分析：最好的情況：即初始排序碼開始就是有序的情況下，直接插入排序算法的比較次數(shù)為(n-1)次，移動次數(shù)為2*(n-1)次。最壞情況：即初始排序碼開始是逆序的情況下，因為當插入第i個排序碼時，該算法內循環(huán)while要執(zhí)行i次條件判斷，循環(huán)體要執(zhí)行i-l次，每次要移動1個記錄，外循環(huán)共執(zhí)行n-1次，其循環(huán)體內不含內循環(huán)每次循環(huán)要進行2次移動操作，所以在最壞情況下，比較次數(shù)為(1+2+…+n)。直接插入排序算法的時間復雜度為O(n2)。10.2.2二分法插入排序二分法插入排序的思想：根據插入排序的基本思想，在找第i個記錄的插入位置時，前i-l個記錄已排序，將第i個記錄的排序碼key[i]和已排序的前i-1個的中間位置記錄的排序碼進行比較，如果key[i]小于中間位置記錄排序碼，則可以在前半部繼續(xù)使用二分法查找，否則在后半部繼續(xù)使用二分法查找，直到查找范圍為空，即可確定key[i]的插入位置。voidbinarysort(table*L)/*折半插入排序*/{intleft,right,mid,i,j;for(i=2;i<=L->length;i++){L->r[0]=L->r[i];/*保存待插入的元素*/left=1;right=i-1;/*設置查找范圍的左、右位置值*/while(left<=right)/*查找第i個元素的插入位置*/{mid=(left+right)/2;/*取中點位置*/if(L->r[i].key<L->r[mid].key)right=mid-1;elseleft=mid+1;}/*插入位置為left*/for(j=i-1;j>=left;j--)/*后移留空*/L->r[j+1]=L->r[j];L->r[left]=L->r[0];/*插入第i個元素的副本*/}}算法10.2二分法插入排序算法二分法插入排序算法，在查找第i個記錄的插入位置時，每執(zhí)行一次while循環(huán)體，查找范圍縮小一半，和直接插入排序的比較次數(shù)對比，二分法插入的比較次數(shù)少于直接插入排序的最多比較次數(shù)，而一般要多于直接插入排序的最少比較次數(shù)?？傮w上講，當n較大時，二分法插入排序的比較次數(shù)遠少于直接插入排序的平均比較次數(shù)，但二者所要進行的移動次數(shù)相等，故二分法插入排序的時間復雜度也是O(n2)，所需的附加存儲空間為一個記錄空間。10.2.3表插入排序二分法插入排序比較次數(shù)通常比直接插入排序的比較次數(shù)少，但移動次數(shù)相等。表插入排序將在不進行記錄移動的情況下，利用存儲結構有關信息的改變來達到排序的目的。給每個記錄附設一個所謂的指針域link，它的類型為整型，表插入排序的思路：在插入第i個記錄Ri時，R1，R2，…，Ri-1已經通過各自的指針域link按排序碼不減的次序連接成一個（靜態(tài)鏈）表，將記錄Ri的排序碼keyi與表中已經排好序的排序碼從表頭向右、或稱向后依次比較，找到Ri應插入的位置，將其插入在表中，使表中各記錄的排序碼仍然有序。/*表插入排序定義的頭文件，文件名為：table2.h*/#defineMAXSIZE100/*文件中記錄個數(shù)的最大值*/typedefintkeytype;/*定義排序碼類型為整數(shù)類型*/typedefstruct{keytypekey;intlink;}recordtype;/*記錄類型的定義*/typedefstruct{recordtyper[MAXSIZE+1];intlength;/*待排序文件中記錄的個數(shù)*/}table2;/*待排序文件類型*/表插入排序算法的示意如圖10.4所示keylink

31212627222628165123

下標

01234567（a）初始存儲狀態(tài)下標

01234567（b）由第1個記錄構成的有序表下標

01234567（c）插入第2個記錄構成的有序表keylink

31212627222628165123

1

0

keylink

31212627222628165123

2

0

1

表插入排序算法：初始時，r[0].Link用于存放表中第1個記錄的下標，r[0].Link的值為1，排序結束時，r[0].Link中存放的是所有排序碼中值最小的對應記錄的下標，其它的排序碼通過各自的指針域link按不減的次序連接成一個（靜態(tài)鏈）表，最大的排序碼對應的link為0。keylink

31212627222628165123

5

0

6

1

3

7

4

2下標

01234567（d）所有記錄都插入后的結束狀態(tài)（下標為5的記錄的key值最小）圖10.4表插入排序算法示意圖voidtableinsertsort(table2*tab){inti,p,q;tab->r[0].link=1;tab->r[1].link=0;/*第1個元素為有序靜態(tài)表*/for(i=2;i<=tab->length;i++)/*依次插入從第2個開始的所有元素*/{q=0;p=tab->r[0].link;/*p指向表中第1個元素，q指向p的前驅元素位置*/while(p!=0&&tab->r[i].key>=tab->r[p].key)/*找插入位置*/{q=p;p=tab->r[p].link;/*繼續(xù)查找*/}tab->r[i].link=p;tab->r[q].link=i;}}算法10.3表插入排序算法基本思想：對待排記錄序列先作“宏觀”調整，再作“微觀”調整，它是由D.L.shell在1959年提出來的。所謂“宏觀”調整，指的是，“跳躍式”的插入排序。即：將記錄序列分成若干子序列，每個子序列分別進行插入排序。關鍵是，這種子序列不是由相鄰的記錄構成的。假設將n個記錄分成d個子序列，則這d個子序列分別為：10.2.4Shell插入排序{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]}10.2.4Shell插入排序21254925*16080123456i=1d=32125*2516084949d=208162125*25組內排序得：組內排序得：210825164925*jj+d21254925*1608

12345621254925*1608012345d=1210825164925*開始時d的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，d值逐漸變小(一般可以按d=d/2的規(guī)律變化)，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎，大多數(shù)對象已基本有序，所以排序速度仍然很快。設待排序的7記錄的排序碼為{312，126，272，226，28，165，123}，初始讓d=7/2=3，以后每次讓d縮小一半，其排序過程如圖所示。31228123126165226272

01234567(c)完成31212328165226126272

01234567(b)d=112331212627222628165

01234567(a)初始狀態(tài)d=3習題：給出初始數(shù)列{47，28，32，15，94，33，14，16}在shell排序下的狀態(tài)變化過程。d=44728321594331416472814159433321614153216472894331415162832334794d=2d=1結果voidshellsort(table*L)/*希爾排序*/{inti,j,d;d=L->length/2;while(d>=1){for(i=d+1;i<=L->length;i++)/*從第d+1個元素開始,將所有元素依次有序插入到相應的分組中*/{L->r[0]=L->r[i]; /*保存第i個元素*/

j=i-d; /*向前找插入位置*/while(j>0&&L->r[0].key<L->r[j].key)/*找插入位置并后移*/

{L->r[j+d]=L->r[j];/*后移*/

j=j-d;/*繼續(xù)向前查找*/

}L->r[j+d]=L->r[0];/*插入第i個元素的副本*/}

d=d/2;}}算法10.4Shell插入排序算法10.3選擇排序選擇排序的基本思想是：每次從待排序的文件中選擇出排序碼最小的記錄，將該記錄放于已排序文件的最后一個位置，直到已排序文件記錄個數(shù)等于初始待排序文件的記錄個數(shù)為止。10.3.1直接選擇排序

首先從所有n個待排序記錄中選擇排序碼最小的記錄，將該記錄與第1個記錄交換，再從剩下的n-l個記錄中選出排序碼最小的記錄和第2個記錄交換。重復這樣的操作直到剩下2個記錄時，再從中選出排序碼最小的記錄和第n-1個記錄交換。剩下的那1個記錄肯定是排序碼最大的記錄，這樣排序即告完成。直接選擇排序演示2125*i=12516490825160825*4921i=221254925*1608

123456初始最小者

08交換21,08最小者

16交換25,1625160825*4921結果4925*i=408162521最小者

25*無交換最小者

25無交換25*i=54925211608

12345649i=3081625*2521最小者

21交換49,21voidselectsort(table*L)/*簡單選擇排序算法*/{int

i,j,k;for(i=1;i<L->length;i++){k=i;for(j=i+1;j<=L->length;j++)/*找最小元素所在位置*/if(L->r[j].key<L->r[k].key)k=j;if(k!=i){L->r[0]=L->r[i];/*將第i次找到的最小元素放到第i個位置*/L->r[i]=L->r[k];L->r[k]=L->r[0];}}}直接選擇排序算法執(zhí)行過程如圖10.6所示（見書本）10.3.3堆排序為了既要保存中間比較結果，減少后面的比較次數(shù)，又不占用大量的附加存儲空間，使排序算法具有較好的性能，Willioms和Floyd在1964年提出的稱為堆排序的算法實現(xiàn)了這一想法。堆是一個序列{k1,k2,…,kn}，它滿足下面的條件：

ki≤k2i并且ki≤k2i+1，當i=1,2,…,

n/2

采用順序方式存儲這個序列，就可以將這個序列的每一個元素ki看成是一顆有n個結點的完全二叉樹的第i個結點，其中k1是該二叉樹的根結點。堆形：元素序列{a1,a2,…,an}的如下層次關系：a1a2a4a3a5a6123456堆關系：若j=2i或j=2i+1則稱<ai,aj>有堆關系，這時稱ai為此堆關系的頂，aj為此堆關系的基。堆：滿足以下條件的堆形：對堆形中的所有堆關系<ai,aj>均有ai<=aj或ai>=aj

。把堆對應的一維數(shù)組(即該序列的順序存儲結構)看作一棵完全二叉樹的順序存儲，那么堆的特征可解釋為，完全二叉樹中任一分支結點的值都小于或等于它的左、右兒子結點的值。堆的元素序列中的第一個元素k1，，即對應的完全二叉樹根結點的值是所有元素中值最小的。堆排序方法就是利用這一點來選擇最小元素。在堆中結點序號>n/2的結點沒有基，實際上堆關系滿足完全二叉樹的結構特征。34752012123456152778（a）一個最小堆的例子91882342241612345651378（b）一個最大堆的例子一個序列和相應的完全二叉樹：312272

165

123126

28

226

8

12

12812316528226272126312下標0123456789123456789以下我們討論最大堆：最大堆的重要性質：1）堆頂元為堆中最大元2）堆具有部分有序性。即具有存儲比較結果的功能，遭受破壞時易于調整成新的堆。堆的存儲實現(xiàn)——一維數(shù)組。

918842232416513

12345678a0層1層2層3層堆排序的基本思想：——基本操作1）建堆（將待排序部分調整成堆）2）取最大元（堆頂元）3）并入（將最大元并入已排序部分）建堆算法（R.W.Floyd）1964年提出---篩選法1）將待排序的數(shù)組隨意地組成一個堆形2）沿堆形自下向上，自右向左依次進行篩選。設當前要篩選ai，這時：若ai>=max(a2i,a2i+1)，即滿足堆條件，則對ai的篩選結束；若ai<max(a2i,a2i+1)，則ai與大者交換，即沿大基下降。42132391241612345658878(a)i=4,23篩下一層i42138891241612345652378i(b)i=3,91>16不調整42138891241612345652378i(c)i=2,13下沉兩級42882391241612345651378i(d)i=1,42篩下一層91882342241612345651378

918842232416513

12345678a（e）建成的堆最大元在堆頂建堆的關鍵一步：篩選L[k]若r[low]的右孩子存在且大于左兄弟，則令j指向它，讓它沿大基下沉voidsift(table*L,intk,intm){int

i,j,finished;

/*初始化*/i=k;j=2*i;L->r[0]=L->r[k];finished=0;

/*確定下沉位置*/

while((j<=m)&&(!finished)){if((j<m)&&(L->r[j+1].key>L->r[j].key))j++;

if(L->r[0]>=L->r[j])finished=1;

else{L->r[i]=L->r[j];i=j;j=2*j;}}

/*被篩數(shù)下沉*/L->r[i]=L->r[0];}建堆總體控制：

for(i=L->length/2;i>=1;i--)sift(L,i,L->length);/*對所有元素建堆*/堆排序過程：1）建初始堆（大根堆）2）重復以下工作，一直到排序結束交換截尾重新建堆

for(i=L->length;i>=2;i--)voidheapsort(table*L){}

inti;

for(i=L->length/2;i>=1;i--)

sift(L,i,L->length); /*對所有元素建堆*/for(i=L->length;i>=2;i--)/*i表示當前堆的大小，即等待排序的元素的個數(shù)*/{}

L->r[0]=L->r[i];L->r[i]=L->r[1];L->r[1]=L->r[0];/*上述3條語句為將堆中最小元素和最后一個元素交換*/

sift(L,1,i-1);若設堆中有n個結點，且2k-1

n

2k，則對應的完全二叉樹有k層。在第i層上的結點數(shù)

2i(i=0,1,…,k-1)。在第一個形成初始堆的for循環(huán)中對每一個非葉結點調用了一次堆調整算法sift()，因此該循環(huán)所用的計算時間為：算法分析：其中，i是層序號，2i是第i層的最大結點數(shù)，(k-i-1)是第i層結點能夠移動的最大距離。在第二個for循環(huán)中，調用了n-1次sift()算法，該循環(huán)的計算時間為O(nlog2n)。因此，堆排序的時間復雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該算法的空間復雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。練習：1、給出初始數(shù)列{47、28、32、15、94、33、14、16}在堆排序下的建堆過程及示意圖。2、下列四個選項中，哪一個序列組成一個最小堆？a）20、76、35、23、80、54b）20、54、23、80、35、76c）80、23、35、76、20、54d）20、35、23、80、54、76答案：d算法設計題：1、寫一個Heapinsert(r,key)算法，將關鍵字插入到堆r中，并保證插入后r后仍是堆。2、寫一個建堆算法：從空堆開始，依次讀入元素調用上題中堆插入算法將其插入堆中。3、寫一個堆刪除算法heapdelete(r,i)，將r[i]從堆r中刪去。10.4交換排序交換排序的基本思路：對待排序記錄兩兩進行排序碼比較，若不滿足排序順序則交換這對記錄，直到任何兩個記錄的排序碼都滿足排序要求為止?？焖倥判蛎芭菖判虻?趟，對所有記錄從左到右每相鄰兩個記錄的排序碼進行比較，如果這兩個記錄的排序碼不符合排序要求，則進行交換，這樣一趟做完，將排序碼最大者放在最后一個位置；第2趟對剩下的n-l個待排序記錄重復上述過程，又將一個排序碼放于最終位置，反復進行n-l次，可將n-l個排序碼對應的記錄放至最終位置，剩下的即為排序碼最小的記錄，它在第1的位置處。如果在某一趟中，沒有發(fā)生交換，則說明此時所有記錄已經按排序要求排列完畢，排序結束。10.4.1冒泡排序一趟冒泡：對數(shù)列中指定的起點到終點間的數(shù)據進行連續(xù)冒泡。4728321594331416例：2847321594331416324728159433141615472832943314161547283294331416339415472832141614941547283233161694154728323314voidbubblesort(table*L)/*冒泡排序*/{inti,j,flag;

i=L->length;/*變量i記錄參與冒泡排序的元素個數(shù)＊/while(i>1){flag=0;for(j=0;j<i;j++)if(L->r[j].key>L->r[j+1].key)/＊逆序則交換＊／

{L->r[0]=L->r[j];L->r[j]=L->r[j+1];L->r[j+1]=L->r[0];

flag=1;}

if(flag==0)break;

i--;

/＊元素個數(shù)減１＊/}}/*算法10.8冒泡排序算法*/二、快速排序基本思想：1）找一個記錄，以它的關鍵字作為“樞軸”，（通常為第一個數(shù)t）2）劃分——其關鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關鍵字大于樞軸的記錄均移動至該記錄之后。3）對上步分成的兩個無序數(shù)組段重復1）、2）操作直到段長為1。t<t>=tpivot2125*i=125164908pivot21254925*16080123456pivot例：211608i=225*pivot4925i=3081621254925*關鍵問題：如何劃分？事實：劃分過程也是當前選出數(shù)t的最后定位過程。方法：從外向內來回比較法。1）將當前選擇的數(shù)保存到t中，以空出左端。2）從右向左依次比較，放過那些大于t的數(shù)，一直找到第一個小于等于t的數(shù)；將此數(shù)放入空左端，并令其空出的位置為新右端，原左端的右鄰為新左端。3）從左向右依次地放過那些<=t的各數(shù)，直找到第一個>=t的數(shù)；將此數(shù)放入空右端，并令其空出的位置為新左端，原右端的左鄰為新右端。4）重復2）3）步，直至t進入最終位置。例：

123456t=a[1]初始序列如下：21254925*1608從右向左找第一個小于t的數(shù)21rightleft例：

123456t=a[1]初始序列如下：254925*1608rightleft例：

123456t=a[1]初始序列如下：254925*1608rightleft21例：

123456t=a[1]初始序列如下：254925*1608rightleft從左向右找第一個大于t的數(shù)例：

123456t=a[1]初始序列如下：254925*1608rightleft例：

123456t=a[1]初始序列如下：254925*1608rightleft21從右向左掃描例：

123456t=a[1]初始序列如下：254925*1608leftright21例：

123456t=a[1]初始序列如下：254925*1608leftright例：

123456t=a[1]初始序列如下：254925*1608leftright從左向右掃描21例：

123456t=a[1]初始序列如下：254925*1608rightleft例：

123456t=a[1]初始序列如下：254925*1608rightleft一次劃分結束條件：left=right21快速排序就是不斷地對原始數(shù)據段及劃分中分出的新數(shù)據段作劃分。關鍵一步：對L->r[left..right]作一次來回比較。1）從右向左找第一個不大于t的數(shù)。

while(left<right&&t.key<L->r[right].key)right--;2）將r[right]填入空左端，并設置新左端。

if(left<right){}3）從左向右找第一個大于t的數(shù)。

while()left++;4）將r[left]填入空右端，并設置新右端。if(left<right){L->r[right]=L->r[left];right--;}L->r[left]=L->r[right];left++;left<right&&t.key>L->r[left].keyright快速排序的總體控制：quicksort(&L,low,high)1）初始化：left=low;right=high;t=r[left];2）對當前數(shù)據段作劃分：

do{一次來回比較；}while(left!=right);3）將t填入最終位置:L->r[]=t;4）遞歸地對L[low..left-1]，L[left+1..high]作快速排序。

quicksort();leftquicksort();L,low,left-1L,left+1,highvoidquicksort(table*L,intlow,inthigh){intleft,right;recordtypet;if(low<high){/*初始化*/left=low;right=high;t=L->r[left];do{while(left<right&&t.key<L->r[right].key)right--;/*從右往左找第一個小于等于t的元素*/if(left<right){L->r[left]=L->r[right];left++;}/*將r[right]的值填入左端，并設新左端*/while(left<right&&t.key>L->r[left].key)left++;/*從左往右找第一個大于t的元素*/快速排序遞歸出口條件一次劃分初始化工作來回比較進行一次劃分

if(left<right){L->r[right]=L->r[left];right--;}/*將r[left]的值填入右端，并設新右端*/}while(left!=right);

L->r[left]=t;/*t存入相應位置*/

/*遞歸對左段和右段進行快速排序*/

quicksort(L,low,left-1);quicksort(L,left+1,high);}}一次劃分結束條件劃分元放最終位置遞歸地對左、右區(qū)間進行快速排序算法分析：快速排序被認為是在所有同數(shù)量級O(nlogn)的排序方法中，其平均性能是最好的。例但是，若待排記錄的初始狀態(tài)為按關鍵字有序時，快速排序將蛻化為冒泡排序，其時間復雜度為O(n2)。初始序列：2030405060708090100什么樣的初始序列具有最佳的快速排序時間效率？

？練習：1、給定初始序列{31，68，45，90，23，39，54，12、87、76}，請寫出以31為樞軸的劃分結果。2、試設計一個算法，使得在O(n)的時間內重排數(shù)組，將所有取負值的關鍵字放在所有取非負值的關鍵字之前。思考題：采用鏈式存儲的線性表如何進行快速排序。

？（一）雙鏈表∧∧head4010608020（二）單鏈表（帶頭結點）∧head

4010806030tail=NULLpqpresp指示當前用于劃分的樞軸q指示當前與p結點進行比較的結點；pre指示q的前驅結點；s用于指示被移動的結點。（二）單鏈表（帶頭結點）∧head

4010806030tail=NULLpqpres將s指示的結點取下插入到當前的鏈首由以下步驟完成：pre->next=q;（二）單鏈表（帶頭結點）∧head

4010806030tail=NULLpqpres將s指示的結點取下插入到當前的鏈首由以下步驟完成：pre->next=q;s->next=head->next;（二）單鏈表（帶頭結點）∧head

4010806030tail=NULLpqpres將s指示的結點取下插入到當前的鏈首由以下步驟完成：pre->next=q;s->next=head->next;head->next=s;（二）單鏈表（帶頭結點）∧head

4010806030tail=NULLpqpres將s指示的結點取下插入到當前的鏈首由以下步驟完成：pre->next=q;s->next=head->next;head->next=s;（二）單鏈表（帶頭結點）將s指示的結點取下插入到當前的鏈首由以下步驟完成：pre->next=q;s->next=head->next;head->next=s;∧head

1040806030tail=NULLpqpres（二）單鏈表（帶頭結點）若q指示的結點值比p指示的結點值大，則該結點的位置保留不動，處理下一個結點。即：∧head

1040806030tail=NULLpqprespre=q;q=q->next;（二）單鏈表（帶頭結點）若q指示的結點值比p指示的結點值大，則該結點的位置保留不動，處理下一個結點。即：∧head

1040806030tail=NULLpqprespre=q;q=q->next;（二）單鏈表（帶頭結點）若q指示的結點值比p指示的結點值大，則該結點的位置保留不動，處理下一個結點。即：∧head

1040806030tail=NULLpqprespre=q;q=q->next;（二）單鏈表（帶頭結點）∧head

1040806030tail=NULLpqpres（二）單鏈表（帶頭結點）∧head

3010804060tail=NULLpqpres（二）單鏈表（帶頭結點）∧head

3010804060tail=NULLpq=NULLpres劃分結束條件：q==tail;遞歸地對前半部分和后半部分進行快速鏈式排序：quicksort(head,p)quicksort(&p,tail)歸并排序的基本思路是：一個待排序記錄構成的文件，可以看作是有多個有序子文件組成的，對有序子文件通過若干次使用歸并的方法，得到一個有序文件。歸并是指將兩個（或多個）有序子表合并成一個有序表的過程。將兩個有序子文件歸并成一個有序文件的方法簡單，只要將兩個有序子文件的當前記錄的排序碼進行比較，較小者放入目標——有序文件，重復這一過程直到兩個有序子文件中的記錄都放入同一個有序文件為止。10.5歸并排序歸并排序最常用的方法是兩兩進行歸并，稱為二路歸并。二路歸并基本思想：1）將n個數(shù)看成n個長度為1的有序表。2）將兩兩相鄰的表依次進行歸并3）重復2），直到歸并成單個有序表歸并排序需要調用兩個操作，一個稱之為一次歸并，另一個稱之為一趟歸并。一次歸并是指將一個數(shù)組中兩個相鄰的有序數(shù)組段歸并為一個有序數(shù)組段，其結果存儲于另一個數(shù)組中的操作。77771948例如：初始序列如下：265771611159154819ab52617711661559a1526771115596619481948b151115265966a1511151926485966關鍵操作：1）一次歸并：把首尾相接的兩個有序表l1->r[u..m]、l1->r[m+1..v]歸并成為有序表l2.r[u..v]。2）一趟歸并：把一些相互鄰接的有序表（在數(shù)組a中）依次兩兩歸并成一些更大的有序表。一次歸并可按以下步驟進行：1）初始化：i=u;j=m+1;k=u;i指向數(shù)組段l1->r[u..m]的當前位置；j指向l1->r[m+1..v]的當前位置；K指向l2.r[u..v]的當前數(shù)組元素（空位）2）數(shù)組段l1->r[i..m]與l1->r[j..v]均為非空時的處理

while(i<=m&&j<=v){if(l1->r[i].key<=l1->r[j].key){l2.r[k]=l1->r[i];i++;}else{l2.r[k]=l1->r[j];j++;}k++;}3）數(shù)組段r[i..m]與r[j..v]之一為空時的處理//將剩余部分直接復制到l2->r[k..v]if(i>m)for(t=j;t<=v;t++)l2.r[k+t-j]=l1->r[t];elsefor(t=i;t<=m;t++)l2.r[k+t-i]=l1->r[t];//本語句執(zhí)行后，數(shù)組段l2.r[u..v]為合并結果。voidmerge(table*l1,intu,intm,intv){inti,j,k,t; tablel2;

i=u;j=m+1;k=u;while(i<=m&&j<=v){if(l1->r[i].key<=l1->r[j].key){l2.r[k]=l1->r[i];i++;}else{ l2.r[k]=l1->r[j]; j++;}k++;}if(i>m)for(t=j;t<=v;t++)l2.r[k+t-j]=l1->r[t];elsefor(t=i;t<=m;t++)l2.r[k+t-i]=l1->r[t];

/*將l2表中的內容拷貝回表l1*/

for(i=u;i<=v;i++) l1->r[i]=l2.r[i];}一趟歸并（mergepass(&l1,n,len)）的實現(xiàn)1）初始化：i=1;//i是第一對有序表的起點2）依次對各相鄰的有序表對進行一次歸并

while(i<=n-2*len+1)//剩余部分有2len長

{merge(l1,i,i+len-1,i+2*len-1);i=i+2*len;//i指向下一對待歸并表起點

}

if(i+len-1<n)//剩余部分大于len小于2len

merge(l1,i,i+len-1,n);3）對長度不足2len的剩余部分和處理一趟歸并算法如下：

voidmergepass(table*l1,intn,intlen){inti,t;i=1;while(i<=n-2*len+1){ merge(l1,i,i+len-1,i+2*len-1); i=i+2*len;}if(i+len-1<n) merge(l1,i,i+len-1,n);}二路歸并總體控制：mergesort.cvoidmergesort(table*l1){intlen,n;tablel2;n=l1->length;len=1;while(len<n){mergepass(l1,n,len);len=len*2;}}二路歸并遞歸算法：mergesort.cvoidmergesortdc(table*l1,intlow,inthigh){intmid;if(low<high){mid=(low+high)/2;mergesortdc(l1,low,mid);mergesortdc(l1,mid+1,high);merge(l1,low,mid,high);}}算法分析在迭代的歸并排序算法中，函數(shù)MergePass()做一趟兩路歸并排序，要調用merge()函數(shù)

n/(2*len)

O(n/len)次，函數(shù)MergeSort()調用MergePass()正好

log2n

次，而每次merge()要執(zhí)行比較O(len)次，所以算法總的時間復雜度為O(nlog2n)。歸并排序占用附加存儲較多，需要另外一個與原待排序對象數(shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。歸并排序是一個穩(wěn)定的排序方法。10.6基數(shù)排序(RadixSort)基數(shù)排序是采用“分配”與“收集”的辦法，用對多關鍵碼進行排序的思想實現(xiàn)對單關鍵碼進行排序的方法。多關鍵碼排序以撲克牌排序為例。每張撲克牌有兩個“關鍵碼”：花色和面值。其有序關系為：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A如果我們把所有撲克牌排成以下次序：

2,…,

A,

2,…,

A,

2,…,

A,

2,…,

A這就是多關鍵碼排序。排序后形成的有序序列叫做詞典有序序列。對于上例兩關鍵碼的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個n個對象的序列{V0,V1,…,Vn-1}，且每個對象Vi中含有d個關鍵碼。如果對于序列中任意兩個對象Vi

和Vj(0

i<j

n-1)都滿足：則稱序列對關鍵碼(K1,K2,…,Kd)有序。其中，K1稱為最高位關鍵碼，Kd

稱為最低位關鍵碼。如果關鍵碼是由多個數(shù)據項組成的數(shù)據項組，則依據它進行排序時就需要利用多關鍵碼排序。實現(xiàn)多關鍵碼排序有兩種常用的方法最高位優(yōu)先MSD(MostSignificantDigitfirst)最低位優(yōu)先LSD(LeastSignificantDigitfirst)最高位優(yōu)先法通常是一個遞歸的過程：先根據最高位關鍵碼K1排序,得到若干對象組，對象組中每個對象都有相同關鍵碼K1。

再分別對每組中對象根據關鍵碼K2進行排序，按K2值的不同，再分成若干個更小的子組，每個子組中的對象具有相同的K1和K2值。依此重復，直到對關鍵碼Kd完成排序為止。最后，把所有子組中的對象依次連接起來，就得到一個有序的對象序列。最低位優(yōu)先法首先依據最低位關鍵碼Kd對所有對象進行一趟排序，再依據次低位關鍵碼Kd-1對上一趟排序的結果再排序，依次重復，直到依據關鍵碼K1最后一趟排序完成，就可以得到一個有序的序列。使用這種排序方法對每一個關鍵碼進行排序時，不需要再分組，而是整個對象組都參加排序。LSD和MSD方法也可應用于對一個關鍵碼進行的排序。此時可將單關鍵碼Ki看作是一個子關鍵碼組：鏈式基數(shù)排序基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運算對單關鍵碼進行排序。在這種方法中，把單關鍵碼Ki

看成是一個d元組：其中的每一個分量(1

j

d)也可看成是一個關鍵碼。分量(1

j

d)有radix種取值，則稱radix為基數(shù)。例如，關鍵碼984可以看成是一個3元組(9,8,4)，每一位有0,1,…,9等10種取值，基數(shù)radix=10。關鍵碼‘data’可以看成是一個4元組(d,a,t,a)，每一位有‘a’,‘b’,…,‘z’等26種取值，radix=26。針對d元組中的每一位分量，把對象序列中的所有對象,按的取值，先“分配”到rd個隊列中去。然后再按各隊列的順序，依次把對象從隊列中“收集”起來，這樣所有對象按取值排序完成。如果對于所有對象的關鍵碼K0,K1,…,Kn-1，依次對各位的分量，讓j=d,d-1,…,1，分別用這種“分配”、“收集”的運算逐趟進行排序，在最后一趟“分配”、“收集”完成后，所有對象就按其關鍵碼的值從小到大排好序了。各隊列采用鏈式隊列結構，分配到同一隊列的關鍵碼用鏈接指針鏈接起來。每一隊列設置兩個隊列指針：intfront[radix]指示隊頭，intrear[radix]指向隊尾。為了有效地存儲和重排

n

個待排序對象，以靜態(tài)鏈表作為它們的存儲結構。在對象重排時不必移動對象，只需修改各對象的鏈接指針即可。基數(shù)排序的“分配”與“收集”過程第一趟614921485637738101215530790306第一趟分配（按最低位i=3）re[0]re[1]re[2]re[3]re[4]re[5]re[6]re[7]re[8]re[9]614738921485637101215530790306fr[0]fr[1]fr[2]fr[3]fr[4]fr[5]fr[6]fr[7]fr[8]fr[9]第一趟收集530790921101614485215306637738基數(shù)排序的“分配”與“收集”過程第二趟614921485637738101215530790306第二趟分配（按次低位i=2）re[0]re[1]re[2]re[3]re[4]re[5]re[6]re[7]re[8]re[9]614738921485637101215530790306fr[0]fr[1]fr[2]fr[3]fr[4]fr[5]fr[6]fr[7]fr[8]fr[9]第二趟收集530790921101614485215306637738基數(shù)排序的“分配”與“收集”過程第三趟614921485637738101215530790306第三趟分配（按最高位i=1）re[0]re[1]re[2]re[3]re[4]re[5]re[6]re[7]re[8]re[9]614738921485637101215530790306fr[0]fr[1]fr[2]fr[3]fr[4]fr