零基礎(chǔ)學(xué)數(shù)據(jù)結(jié)構(gòu)-第12章-內(nèi)排序12.1基本概念穩(wěn)定排序和不穩(wěn)定排序：在待排序的記錄序列中，若存在兩個或兩個以上關(guān)鍵字想到呢個的記錄。假設(shè)ki=kj(1≤i≤n,1≤j≤n,i≠j)，且排序前的對應(yīng)的記錄Ei領(lǐng)先于Ej（即i<j）。若在排序之后，如果元素Ei仍領(lǐng)先于Ej，則稱這種排序采用的方法是穩(wěn)定的。如果經(jīng)過排序之后，元素Ej領(lǐng)先于Ei（即i<j），則稱這種排序方法是不穩(wěn)定的。一個排序算法的好壞可以主要通過時間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性來衡量。無論算法穩(wěn)定還是不穩(wěn)定的，都不會影響到排序的最終結(jié)果。12.1基本概念內(nèi)排序和外排序：由于待排序的記錄數(shù)量不同，使得排序過程中涉及的存儲器不同，可將排序方法分為兩類：內(nèi)部排序和外部排序。內(nèi)部排序也稱為內(nèi)排序，指的是待排序記錄存放在計算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程；外部排序也稱為外排序，指的是待排序記錄的數(shù)據(jù)流很大，以致內(nèi)存一次不能容納全部記錄，在排序的過程中需要不斷對外存進(jìn)行訪問的排序過程。12.1基本概念內(nèi)排序的方法有許多，按照排序過程中采用的策略將排序分為幾個大類：插入排序、選擇排序、交換排序和歸并排序。在排序過程中，需要以下兩種基本操作：（1）比較兩個元素相應(yīng)關(guān)鍵字的大小；（2）將元素從一個位置移動到另一個位置。其中，第（1）種操作對大多數(shù)排序方法來說都是必要的，第（2）種操作可通過改變記錄的存儲方式可以避免。12.1基本概念待排序的記錄序列可有下列3種存儲方式：（1）順序存儲。待排序的元素存儲在一組連續(xù)的存儲單元中，這類似于線性表的順序存儲，在序列中相鄰的兩個記錄Ei和Ej，它們的物理位置也相鄰。在這種存儲方式中，記錄之間的次序關(guān)系由其存儲位置決定，則實現(xiàn)排序必須要移動記錄。（2）鏈?zhǔn)酱鎯?。待排序元素存儲在一組不連續(xù)的存儲單元中，這類似于線性表的鏈?zhǔn)酱鎯Γ蛄兄邢噜彽膬蓚€記錄Ei和Ej，其物理位置不一定相鄰。在這種存儲方式中，記錄之間的關(guān)系由附設(shè)的指針指示，在進(jìn)行排序時，不需要移動元素，只需要修改指針即可。（3）靜態(tài)鏈表。帶排序記錄存放在靜態(tài)鏈表中，記錄之間的關(guān)系由被稱為游標(biāo)的指針指示，實現(xiàn)排序不需要移動元素，只需要修改游標(biāo)即可。12.2插入排序12.2.1直接插入排序直接插入排序（straightinsertionsort）是一種最簡單的插入排序算法。它的基本算法思想描述如下：假設(shè)待排序元素有n個，初始時，已排序子集只有一個元素，即第1個元素。未排序子集是剩下的n-1個元素。例如，有4個待排序元素22、6、17和8，排序前的狀態(tài)如圖12.1所示。12.2插入排序第1趟排序：將無序集中的第一個元素，也就是6與有序集中的元素22進(jìn)行比較，因為22>6，所以需要先將22向后移動一個位置，然后將6插入到第一個位置，如圖12.2所示。其中，陰影部分表示無序集，白色部分表示有序集。第2趟排序：將無序集的元素17從右到左依次與有序集中的元素比較，即先與22比較，因為17<22，所以先將22向后移動一個位置，然后比較17與第1個元素6的大小，因為17>6，所以將17放在第2個元素的位置，如圖12.3所示。12.2插入排序第3趟排序：將待排序集合中的元素8與已經(jīng)有序的元素集合從右到左依次比較，先與22比較。因為8<22，所以需要將22向后移動一個位置并與前一個元素17比較。由于8<17，將17向后移動并繼續(xù)與6進(jìn)行比較。因為8>6，所以將8放在第2個位置，如圖12.4所示。12.2插入排序假設(shè)待排序元素有8個，分別是17、46、32、87、58、9、50、38。使用直接插入排序?qū)υ撛匦蛄械呐判蜻^程如圖12.5所示。12.2插入排序直接插入排序算法描述如下。voidInsertSort(SqList*L)/*直接插入排序*/{ inti,j; DataTypet; for(i=1;i<L->length;i++) /*前i個元素已經(jīng)有序，從第i+1個元素開始與前i個有序的關(guān)鍵字比較*/ { t=L->data[i+1]; /*取出第i+1個元素，即待排序的元素*/ j=i; while(j>0&&t.key<L->data[j].key)/*尋找當(dāng)前元素的合適位置*/ { L->data[j+1]=L->data[j]; j--; } L->data[j+1]=t; /*將當(dāng)前元素插入合適的位置*/ }}12.2插入排序12.2.2折半插入排序折半插入排序算法是直接插入排序的改進(jìn)。它的主要改進(jìn)在于，在已經(jīng)有序的集合中使用折半查找法確定待排序元素的插入位置。在找到要插入的位置后，將待排序元素插入到相應(yīng)的位置。假設(shè)待排序元素有7個：67、53、73、21、34、98、12。使用折半插入排序?qū)υ撛匦蛄械谝惶伺判蜻^程如圖12.6所示。12.2插入排序第2趟折半插入排序過程如圖12.7所示。12.2插入排序voidBinInsertSort(SqList*L)/*折半插入排序*/{ inti,j,mid,low,high; DataTypet; for(i=1;i<L->length;i++) { t=L->data[i+1]; /*取出第i+1個元素，即待排序的元素*/ low=1,high=i; while(low<=high) /*利用折半查找思想尋找當(dāng)前元素的合適位置*/ { mid=(low+high)/2; if(L->data[mid].key>t.key) high=mid-1; else low=mid+1; } for(j=i;j>=low;j--) /*移動元素，空出要插入的位置*/ L->data[j+1]=L->data[j]; L->data[low]=t; /*將當(dāng)前元素插入合適的位置*/ }}12.2插入排序12.2.3希爾排序希爾排序（shell’ssort）也稱為縮小增量排序（diminishingincrementsort），它也屬于插入排序類的算法，但時間效率比前幾種排序有較大改進(jìn)。設(shè)待排序元素為：48、26、66、57、32、85、55、19，使用希爾排序算法對該元素序列的排序過程如圖12.8所示。12.2插入排序相應(yīng)地，希爾排序的算法可描述如下。voidShellInsert(SqList*L,intc)/*對順序表L進(jìn)行一次希爾排序，c是增量*/{ inti,j; DataTypet; for(i=c+1;i<=L->length;i++) /*將距離為c的元素作為一個子序列進(jìn)行排序*/ { if(L->data[i].key<L->data[i-c].key) /*如果后者小于前者，則需要移動元素*/ { t=L->data[i]; for(j=i-c;j>0&&t.key<L->data[j].key;j=j-c) L->data[j+c]=L->data[j]; L->data[j+c]=t;/*依次將元素插入到正確的位置*/ } }}12.2插入排序voidShellInsertSort(SqList*L,intdelta[],intm)/*希爾排序，每次調(diào)用算法ShellInsert,delta是存放增量的數(shù)組*/{ inti; for(i=0;i<m;i++) /*進(jìn)行m次希爾插入排序*/ { ShellInsert(L,delta[i]); }}希爾排序的分析是一個非常復(fù)雜的事情，問題主要在于希爾排序選擇的增量，但是經(jīng)過大量的研究，當(dāng)增量的序列為2m-k+1-1時，其中m為排序的次數(shù)，1≤k≤t，其時間復(fù)雜度為O(n3/2)。希爾排序的空間復(fù)雜度為O(1)。

12.2插入排序12.2.4插入排序應(yīng)用舉例【例12_1】任意給定一組元素序列，利用直接插入排序、折半插入排序和希爾排序?qū)υ撔蛄羞M(jìn)行排序?！痉治觥恐饕疾熘苯硬迦肱判?、折半插入排序和希爾排序的算法思想。12.2插入排序

【例12_2】編寫一個插入排序算法，要求用鏈表實現(xiàn)?！痉治觥恐饕疾觳迦肱判虻乃惴ㄋ枷牒玩湵淼牟僮?。算法思想：首先創(chuàng)建一個鏈表，將待排序元素依次插入到鏈表中。將待排序鏈表分為兩個部分：有序序列和待排序序列。初始時，有序序列中沒有元素，令L->next=NULL。指針p指向待排序的鏈表，若有序序列為空，將p指向的第一個結(jié)點插入到空鏈表L中。然后將有序鏈表即L指向的鏈表的每一個結(jié)點與p指向的結(jié)點比較，并將結(jié)點*p插入到L指向的鏈表的恰當(dāng)位置。重復(fù)執(zhí)行上述操作，直到待排序鏈表為空。此時，L就是一個有序鏈表。12.3交換排序12.3.1冒泡排序冒泡排序(bubblesort)是一種簡單的交換類排序算法，它是通過交換相鄰的兩個數(shù)據(jù)元素，逐步將待排序序列變成有序序列。它的基本算法思想描述如下：假設(shè)待排序元素有n個，從第1個元素開始，依次交換相鄰的兩個逆序元素，直到最后一個元素為止。當(dāng)?shù)?趟排序結(jié)束，就會將最大的元素移動到序列的末尾。然后按照以上方法進(jìn)行第2趟排序，次大的元素將會被移動到序列的倒數(shù)第2個位置。依次類推，經(jīng)過n-1趟排序后，整個元素序列就成了一個有序的序列。每趟排序過程中，值小的元素向前移動，值大的元素向后移動，就像氣泡一樣向上升，因此將這種排序方法稱為冒泡排序。12.3交換排序例如，有5個待排序元素55、26、48、63和37。第1趟排序：12.3交換排序第2趟排序：從第1個元素開始，依次比較第1個元素與第2個元素、第2個元素與第3個元素、第3個元素與第4個元素，如果前者大于后者，則交換之；否則不進(jìn)行交換。第2趟排序過程如圖12.12所示。12.3交換排序第3趟排序：按照以上方法，依次比較兩個相鄰元素，交換逆序的元素。第3趟排序過程如圖12.13所示。第4趟排序：此時，待排序元素只剩下26和37，只需要進(jìn)行一次比較即可。因為26<37，所以不需要交換。第4趟排序過程如圖12.14所示。12.3交換排序設(shè)待排序元素為56、72、44、31、99、21、69、80，使用冒泡排序?qū)υ撛匦蛄械呐判蜻^程如圖12.15所示。12.3交換排序冒泡排序的算法描述如下。voidBubbleSort(SqList*L,intn)/*冒泡排序*/{ inti,j,flag; DataTypet; for(i=1;i<=n-1&&flag;i++) /*需要進(jìn)行n-1趟排序*/ { flag=0; for(j=1;j<=n-i;j++) /*每一趟排序需要比較n-i次*/ if(L->data[j].key>L->data[j+1].key)

{ t=L->data[j]; L->data[j]=L->data[j+1]; L->data[j+1]=t; flag=1; } }}12.3交換排序快速排序的算法思想是：從待排序記錄序列中選取一個記錄（通常是第一個記錄）作為樞軸，其關(guān)鍵字設(shè)為key，然后將其余關(guān)鍵字小于key的記錄移至前面，而將關(guān)鍵字大于key的記錄移至后面，結(jié)果將待排序記錄序列分為兩個子表，最后將關(guān)鍵字key的記錄插入到其分界線的位置。我們將這個過程稱為一趟快速排序。通過這一趟劃分后，就以關(guān)鍵字為key的記錄為界，將待排序序列分為兩個子表，前面的子表所有記錄的關(guān)鍵字均不大于key，而后面子表的所有記錄的關(guān)鍵字均不小于key。繼續(xù)對分割后的子表進(jìn)行上述劃分，直至所有子表的表長不超過1為止，此時的待排序記錄就成了一個有序序列。12.3交換排序【算法步驟】設(shè)待排序序列存放在數(shù)組a[1…n]中，n為元素個數(shù)，設(shè)置兩個指針i和j，初值分別為1和n，令a[1]作為樞軸元素賦給pivot，a[1]相當(dāng)于空單元，然后執(zhí)行以下操作：（1）j從右往左掃描，若a[j].key<pivot.key，將a[j]移至a[i]中，此時a[j]相當(dāng)于空單元，并執(zhí)行一次i++操作；（2）i從左至右掃描，直至a[i].key>pivot.key，將a[i]移至a[j]中，并執(zhí)行一次j--操作；（3）重復(fù)執(zhí)行（1）和（2），直到出現(xiàn)i≥j，則將元素pivot移動到a[i]中。此時整個元素序列在位置i被劃分成兩個部分，前一部分的元素關(guān)鍵字都小于a[i].key，后一部分元素的關(guān)鍵字都大于等于a[i].key。即完成了一趟快速排序。12.3交換排序例如，一組待排序元素序列為55,22,44,67,35,77,18,69，依據(jù)快速排序的算法思想，得到第1趟排序的過程如圖12.16所示。12.3交換排序設(shè)待排序元素為55、22、44、67、35、77、18、69，用快速排序算法對該元素序列的排序過程如圖12.17所示。12.3交換排序進(jìn)行一趟快速排序，即將元素序列進(jìn)行一次劃分的算法描述如下所示。intPartition(SqList*L,intlow,inthigh)/*對順序表L.r[low..high]的元素進(jìn)行一趟排序，使樞軸前面的元素關(guān)鍵字小于樞軸元素的關(guān)鍵字，樞軸后面的元素關(guān)鍵字大于等于樞軸元素的關(guān)鍵字，并返回樞軸位置*/{ DataTypet; KeyTypepivotkey; pivotkey=(*L).data[low].key;/*將表的第一個元素作為樞軸元素*/ t=(*L).data[low]; while(low<high) /*從表的兩端交替地向中間掃描*/ { while(low<high&&(*L).data[high].key>=pivotkey)/*從表的末端向前掃描*/ high--; if(low<high) /*將當(dāng)前high指向的元素保存在low位置*/ { (*L).data[low]=(*L).data[high]; low++; }while(low<high&&(*L).data[low].key<=pivotkey) /*從表的始端向后掃描*/ low++; if(low<high) /*將當(dāng)前l(fā)ow指向的元素保存在high位置*/ { (*L).data[high]=(*L).data[low]; high--; } (*L).data[low]=t;/*將樞軸元素保存在low=high的位置*/

} returnlow; /*返回樞軸所在位置*/}12.3交換排序12.3交換排序通過多次遞歸調(diào)用一次劃分算法即一趟排序算法，可實現(xiàn)快速排序，其算法描述如下所示。voidQuickSort(SqList*L,intlow,inthigh)/*對順序表L進(jìn)行快速排序*/{ intpivot; if(low<high) /*如果元素序列的長度大于1*/ { pivot=Partition(L,low,high); /*將待排序序列L.r[low..high]劃分為兩部分*/ QuickSort(L,low,pivot-1); /*對左邊的子表進(jìn)行遞歸排序，pivot是樞軸位置*/ QuickSort(L,pivot+1,high); /*對右邊的子表進(jìn)行遞歸排序*/ }}12.3交換排序快速排序在最好的情況下是每趟排序?qū)⑿蛄幸环謨砂?，從表中間開始，將表分成兩個大小相同的子表，類似折半查找，這樣快速排序的劃分的過程就將元素序列構(gòu)成一個完全二叉樹的結(jié)構(gòu)，分解的次數(shù)等于樹的深度即log2n，因此快速排序總的比較次數(shù)為T(n)≤n+2T(n/2)≤n+2*(n/2+2*T(n/4))=2n+4T(n/4)≤3n+8T(n/8)≤…≤nlog2n+nT(1)。因此，在最好的情況下，時間復(fù)雜度為O(nlog2n)。12.3.3交換排序應(yīng)用舉例【例12_3】編寫算法，使用冒泡排序和快速排序算法對給定的一組關(guān)鍵字序列(37,22,43,32,19,12,89,26,48,92)進(jìn)行排序，并輸出每趟排序結(jié)果?！痉治觥恐饕疾靸煞N交換排序即冒泡排序和快速排序的算法思想。這兩種算法都是對存在逆序的元素進(jìn)行交換，從而實現(xiàn)排序。主要區(qū)別在于：冒泡排序通過比較相鄰的兩個元素，并對兩個相鄰的逆序元素進(jìn)行交換；而快速排序則是選定一個樞軸元素作為參考元素，設(shè)置兩個指針，分別從表頭和表尾開始，將當(dāng)前掃描的元素與樞軸元素進(jìn)行比較，存在逆序的元素不一定是相鄰的元素，如果存在逆序，則交換之。12.3交換排序12.4.1簡單選擇排序簡單選擇排序是一種簡單的選擇類排序算法，它是通過依次找到待排序元素序列中最小的數(shù)據(jù)元素，并將其放在序列的最前面，從而使待排序元素序列變?yōu)橛行蛐蛄?。它的基本算法思想描述如下：假設(shè)待排序的元素序列有n個，在第一趟排序過程中，從n個元素序列中選擇最小的元素，并將其放在元素序列的最前面即第一個位置。在第二趟排序過程中，從剩余的n-1個元素中，選擇最小的元素，將其放在第二個位置。依次類推，直到?jīng)]有待比較的元素，簡單選擇排序算法結(jié)束。12.4選擇排序簡單選擇排序的算法描述如下。voidSelectSort(SqList*L,intn)/*簡單選擇排序*/{ inti,j,k; DataTypet; /*將第i個元素的關(guān)鍵字與后面[i+1...n]個元素的關(guān)鍵字比較，將關(guān)鍵字最小的的元素放在第i個位置*/ for(i=1;i<=n-1;i++) { j=i; for(k=i+1;k<=n;k++) /*關(guān)鍵字最小的元素的序號為j*/ if(L->data[k].key<L->data[j].key) j=k; if(j!=i) /*如果序號i不等于j，則需要將序號i和序號j的元素交換*/ { t=L->data[i]; L->data[i]=L->data[j]; L->data[j]=t; } }}12.4選擇排序12.4選擇排序一組元素的關(guān)鍵字序列為(76,31,19,20,6,83,60,52)，簡單選擇排序的過程如圖12.19所示。12.4.2堆排序1．什么是堆和堆排序堆排序(heapsort)主要是利用了二叉樹的樹形結(jié)構(gòu)，按照完全二叉樹的編號次序，將元素序列的關(guān)鍵字依次存放在相應(yīng)的結(jié)點。然后從葉子結(jié)點開始，從互為兄弟的兩個結(jié)點中（沒有兄弟結(jié)點除外），選擇一個較大（或較小）者與其雙親結(jié)點比較，如果該結(jié)點大于（或小于）雙親結(jié)點，則將兩者進(jìn)行交換，使較大（或較小）者成為雙親結(jié)點。將所有的結(jié)點都做類似操作，直到根結(jié)點為止。這時，根結(jié)點的元素值的關(guān)鍵字最大（或最?。?2.4選擇排序這樣就構(gòu)成了堆，堆中的每一個結(jié)點都大于（或小于）其孩子結(jié)點。堆的數(shù)學(xué)形式定義為：假設(shè)存在n個元素，其關(guān)鍵字序列為(k1,k2,…,ki,…,kn)，如果有：則稱此元素序列構(gòu)成了一個堆。如果將這些元素的關(guān)鍵字存放在一維數(shù)組中，將此一維數(shù)組中的元素與完全二叉樹一一對應(yīng)起來，則完全二叉樹中的每個非葉子結(jié)點的值都不小于（或不大于）孩子結(jié)點的值。12.4選擇排序在堆中，堆的根結(jié)點元素值一定是所有結(jié)點元素值的最大值或最小值。例如，序列（89,77,65,62,32,55,60,48）和（18,37,29,48,50,43,33,69,77,60）都是堆，相應(yīng)的完全二叉樹表示如圖12.20所示。12.4選擇排序如果將堆中的根結(jié)點（堆頂）輸出之后，然后將剩余的n-1個結(jié)點的元素值重新建立一個堆，則新堆的堆頂元素值是次大（或次?。┲?，將該堆頂元素輸出。然后將剩余的n-2個結(jié)點的元素值重新建立一個堆，反復(fù)執(zhí)行以上操作，直到堆中沒有結(jié)點，就構(gòu)成了一個有序序列，這樣的重復(fù)建堆并輸出堆頂元素的過程稱為堆排序。12.4選擇排序2．建堆堆排序的過程就是建立堆和不斷調(diào)整使剩余結(jié)點構(gòu)成新堆的過程。假設(shè)將待排序的元素的關(guān)鍵字存放在數(shù)組a中，第1個元素的關(guān)鍵字a[1]表示二叉樹的根結(jié)點，剩下的元素的關(guān)鍵字aa[2…n]分別與二叉樹中的結(jié)點按照層次從左到右一一對應(yīng)。例如，a[1]的左孩子結(jié)點存放在a[2]中，右孩子結(jié)點存放在a[3]中，a[i]的左孩子結(jié)點存放在a[2*i]中，右孩子結(jié)點存放在a[2*i+1]中。12.4選擇排序例如，給定一組元素序列(27,58,42,53,42,69,50,62)，建立大頂堆的過程如圖12.21所示。12.4選擇排序相應(yīng)地，建立大頂堆的算法描述如下所示。voidCreateHeap(SqList*H,intn)/*建立大頂堆*/{ inti; for(i=n/2;i>=1;i--) /*從序號n/2開始建立大頂堆*/ AdjustHeap(H,i,n);}12.4選擇排序voidAdjustHeap(SqList*H,ints,intm)/*調(diào)整H.data[s...m]的關(guān)鍵字，使其成為一個大頂堆*/{ DataTypet; intj; t=(*H).data[s]; /*將根結(jié)點暫時保存在t中*/ for(j=2*s;j<=m;j*=2) { if(j<m&&(*H).data[j].key<(*H).data[j+1].key) /*沿關(guān)鍵字較大的孩子結(jié)點向下篩選*/ j++; /*j為關(guān)鍵字較大的結(jié)點的下標(biāo)*/ if(t.key>(*H).data[j].key) /*如果孩子結(jié)點的值小于根結(jié)點的值，則不進(jìn)行交換*/ break; (*H).data[s]=(*H).data[j]; s=j; } (*H).data[s]=t; /*將根結(jié)點插入到正確位置*/}12.4選擇排序3．調(diào)整堆具體實現(xiàn)：當(dāng)堆頂元素輸出后，可以將堆頂元素放在堆的最后，即將第1個元素與最后一個元素交換a[1]<->a[n]，則需要調(diào)整的元素序列就是a[1…n-1]。從根結(jié)點開始，如果其左、右子樹結(jié)點元素值大于根結(jié)點元素值，選擇較大的一個進(jìn)行交換。即如果a[2]>a[3]，則將a[1]與a[2]比較，如果a[1]>a[2]，則將a[1]與a[2]交換，否則不交換。如果a[2]<a[3]，則將a[1]與a[3]比較，如果a[1]>a[3]，則將a[1]與a[3]交換，否則不交換。重復(fù)執(zhí)行此操作，直到葉子結(jié)點不存在，就完成了堆的調(diào)整，構(gòu)成了一個新堆。12.4選擇排序12.4選擇排序例如，一個大頂堆的關(guān)鍵字序列為(69,62,50,58,42,42,27,53)，當(dāng)輸出69后，調(diào)整剩余的元素序列為大頂堆的過程如圖12.22所示。12.4選擇排序調(diào)整堆的算法實現(xiàn)如下。voidHeapSort(SqList*H)/*對順序表H進(jìn)行堆排序*/{ DataTypet; inti; CreateHeap(H,H->length); /*創(chuàng)建堆*/ for(i=(*H).length;i>1;i--) /*將堆頂元素與最后一個元素交換，重新調(diào)整堆*/ { t=(*H).data[1]; (*H).data[1]=(*H).data[i]; (*H).data[i]=t; AdjustHeap(H,1,i-1); /*將(*H).data[1..i-1]調(diào)整為大頂堆*/ }}12.4選擇排序例如，一個大頂堆的元素的關(guān)鍵字序列為(69,62,50,58,42,42,27,53)，其相應(yīng)的完整的堆排序過程如圖12.23所示。12.4選擇排序12.4.3選擇排序應(yīng)用舉例【例12_4】編寫算法，利用簡單選擇排序和堆排序算法對一組關(guān)鍵字序列(69,62,50,58,42,42,27,53)進(jìn)行排序，要求輸出每趟排序的結(jié)果?！痉治觥亢唵芜x擇排序和堆排序都是一種不穩(wěn)定的排序方法。它們的主要思想：每次從待排序元素中選擇關(guān)鍵字最?。ɑ蜃畲螅┑脑?，經(jīng)過不斷交換，重復(fù)執(zhí)行以上操作，最后形成一個有序的序列。12.4選擇排序【例12_5】編寫算法，對關(guān)鍵字序列(76,20,99,32,60,53,11,8,42)進(jìn)行選擇排序，要求使用鏈表實現(xiàn)?！痉治觥恐饕疾爝x擇排序的算法思想和鏈表的操作。具體實現(xiàn)時，設(shè)置兩個指針p和q，分別指向已排序鏈表和未排序鏈表。初始時，先創(chuàng)建一個鏈表，q指向該鏈表，p指向的鏈表為空。然后從q指向的鏈表中找到一個元素值最小的結(jié)點，將其取出并插入到p指向的鏈表中。重復(fù)執(zhí)行以上操作直到q指向的鏈表為空，此時p指向的鏈表就是一個有序鏈表。12.5歸并排序12.5.12路歸并排序算法主要思想是：假設(shè)元素的個數(shù)是n，將每個元素作為一個有序的子序列，然后將相鄰的兩個子序列兩兩歸并，得到個長度為2的有序子序列。然后將相鄰的兩個有序子序列兩兩歸并，得到個長度為4的有序子序列。如此重復(fù)，直至得到一個長度為n的有序序列為止。關(guān)鍵字序列(50,22,61,35,87,12,19,75)的2路歸并排序的過程如圖12.26所示。12.5歸并排序voidMerge(DataTypes[],DataTypet[],intlow,intmid,inthigh)/*將有序的s[low...mid]和s[mid+1..high]歸并為有序的t[low..high]*/{ inti,j,k; i=low,j=mid+1,k=low; while(i<=mid&&j<=high) /*將s中元素由小到大地合并到t*/ { if(s[i].key<=s[j].key) { t[k]=s[i++]; } else { t[k]=s[j++]; } k++; } while(i<=mid) /*將剩余的s[i..mid]復(fù)制到t*/ t[k++]=s[i++]; while(j<=high) /*將剩余的s[j..high]復(fù)制到t*/ t[k++]=s[j++];}12.5歸并排序voidMergeSort(DataTypes[],DataTypet[],intlow,inthigh)/*2路歸并排序，將s[low...high]歸并排序并存儲到t[low...high]中*/{ intmid; DataTypet2[MaxSize]; if(low==high) t[low]=s[low]; else { mid=(low+high)/2; /*將s[low...high]分為s[low...mid]和s[mid+1...high]*/ MergeSort(s,t2,low,mid); /*將s[low...mid]歸并為有序的t2[low...mid]*/ MergeSort(s,t2,mid+1,high); /*將s[mid+1...high]歸并為有序的t2[mid+1...high]*/ Merge(t2,t,low,mid,high); /*將t2[low...mid]和t2[mid+1..high]歸并到t[low...high]*/ }}12.5歸并排序12.5.2歸并排序應(yīng)用舉例【例12_6】編寫算法，請使用2路歸并排序?qū)σ唤M關(guān)鍵字(50,22,61,35,87,12,19,75)進(jìn)行排序。12.6基數(shù)排序12.6.1基數(shù)排序算法基數(shù)排序正是借助這種思想，對不同類的元素進(jìn)行分類，然后對同一類中的元素進(jìn)行排序，通過這樣的一種過程，完成對元素序列的排序。在基數(shù)排序中，通常將對不同元素的分類稱為分配，排序的過程稱為收集。具體算法思想：假設(shè)第i個元素ai的關(guān)鍵字keyi，keyi是由d位十進(jìn)制組成，即keyi=kidkid-1…ki1，其中ki1為最低位，kid為最高位。關(guān)鍵字的每一位數(shù)字都可作為一個子關(guān)鍵字。首先將元素序列按照最低的關(guān)鍵字進(jìn)行排序，然后從低位到高位直到最高位依次進(jìn)行排序，這樣就完成了排序過程。12.6基數(shù)排序例如，一組元素的關(guān)鍵字序列為(236,128,34,567,321,793,317,106)。對最低位進(jìn)行分配和收集的過程如圖12.28所示。其中，數(shù)組f[i]保存第i個鏈表的頭指針，數(shù)組r[i]保存第i個鏈表的尾指針。12.6基數(shù)排序?qū)κ粩?shù)字分配和收集的過程如圖12.29所示。對百位數(shù)字分配和收集的過程如圖12.30所示。12.6基數(shù)排序基數(shù)排序的算法主要包括分配和收集。靜態(tài)鏈表類型定義描述如下：#defineMaxNumKey6/*關(guān)鍵字項數(shù)的最大值*/#defineRadix10 /*關(guān)鍵字基數(shù)，此時是十進(jìn)制整數(shù)的基數(shù)*/#defineMaxSize1000typedefintKeyType;typedefstruct{ KeyTypekey[MaxNumKey];/*關(guān)鍵字*/ intnext;}SListCell; /*靜態(tài)鏈表的結(jié)點類型*/typedefstruct{ SListCelldata[MaxSize]; /*存儲元素，data[0]為頭結(jié)點*/ intkeynum; /*每個元素的當(dāng)前關(guān)鍵字個數(shù)*/ intlength; /*靜態(tài)鏈表的當(dāng)前長度*/}SList; /*靜態(tài)鏈表類型*/typedefintaddr[Radix]; /*指針數(shù)組類型*/12.6基數(shù)排序基數(shù)排序的分配算法實現(xiàn)如下所示。voidDistribute(SListCelldata[],inti,addrf,addrr)/*為data中的第i個關(guān)鍵字key[i]建立Radix個子表，使同一子表中元素的key[i]相同*//*f[0..Radix-1]和r[0..Radix-1]分別指向各個子表中第一個和最后一個元素*/{ intj,p; for(j=0;j<Radix;j++) /*將各個子表初始化為空表*/ f[j]=0; for(p=data[0].next;p;p=data[p].next) {