數(shù)據(jù)結(jié)構(gòu)項目八

數(shù)據(jù)結(jié)構(gòu)項目八共分為五個任務(wù)數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第1頁。項目八排序任務(wù)一排序的相關(guān)概念任務(wù)二插入排序任務(wù)三交換排序任務(wù)四選擇排序任務(wù)五歸并排序和基數(shù)排序數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第2頁。任務(wù)一排序的相關(guān)概念1．排序2．數(shù)據(jù)元素的存儲結(jié)構(gòu)3．算法的穩(wěn)定性4．算法的評價數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第3頁。1．排序排序是指將一個數(shù)據(jù)元素的任意序列按關(guān)鍵字的遞增或遞減次序重新排列起來，使其成為一個按關(guān)鍵字有序排列的序列。內(nèi)部排序是指將待排數(shù)據(jù)元素完全放置在內(nèi)存中進行排序的方法。外部排序是指因待排數(shù)據(jù)元素數(shù)量太大，排序過程中不僅需要使用內(nèi)存，還要借助外部存儲器來完成的排序方法。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第4頁。2．數(shù)據(jù)元素的存儲結(jié)構(gòu)數(shù)據(jù)元素可有3種存儲結(jié)構(gòu)：順序結(jié)構(gòu)、鏈式結(jié)構(gòu)和地址向量結(jié)構(gòu)。排序過程中一定要移動數(shù)據(jù)元素排序過程中不用移動數(shù)據(jù)元素，而只需要修改指針指將數(shù)據(jù)元素順序存儲的同時，另設(shè)一個指示各個數(shù)據(jù)元素位置的地址向量，這樣在排序過程中不用移動數(shù)據(jù)元素，而只需修改地址向量中數(shù)據(jù)元素的“地址”即可順序結(jié)構(gòu)的數(shù)據(jù)類型定義如下：#defineMAXSIZE100 //順序表的最大長度typedefstruct {KeyTypekey; //關(guān)鍵字項OtherTypeotheritem; //另外的數(shù)據(jù)項}RecordType;typedefstruct {RecordTyper[MAXSIZE+1];//定義數(shù)據(jù)元素數(shù)組，r[0]為哨兵單元intlength; //順序表長度}SeqList;數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第5頁。3．算法的穩(wěn)定性如果待排序的數(shù)據(jù)元素序列中有兩個數(shù)據(jù)元素的關(guān)鍵字的值相同，經(jīng)過排序后，兩個數(shù)據(jù)元素的相對次序保持不變，則稱所用的排序方法是穩(wěn)定的；反之，則稱所用的排序方法是不穩(wěn)定的。關(guān)鍵字序列（35，2，15，6，81，6*）結(jié)果序列為（2，6，6*，15，35，81）表示為穩(wěn)定的排序方法結(jié)果序列為（2，6*，6，15，35，81）表示為不穩(wěn)定的排序方法數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第6頁。4．算法的評價可以從兩個方面來評價某種排序算法的優(yōu)劣：通過排序過程中所需的內(nèi)存輔助空間的多少來衡量。通過排序過程中關(guān)鍵字的比較次數(shù)和數(shù)據(jù)元素的移動次數(shù)來反映。①空間復雜度：②時間復雜度：數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第7頁。任務(wù)二插入排序一、直接插入排序二、折半插入排序三、希爾排序數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第8頁。1．基本思想2．算法實現(xiàn)一、直接插入排序3．算法分析數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第9頁。1．基本思想將待排數(shù)據(jù)元素插入到已排好序的有序表中，從而得到一個新的有序表。對于一個具有n個數(shù)據(jù)元素的序列，進行直接插入排序具體過程：①將第1個數(shù)據(jù)元素看作一個已排好序的有序表。②將第i（2≤i≤n）個數(shù)據(jù)元素的關(guān)鍵字Ki依次與其前面數(shù)據(jù)元素的關(guān)鍵字Ki－1、Ki－2、…、K1進行比較，將所有關(guān)鍵字大于Ki的數(shù)據(jù)元素依次向后移動一個位置，直到某個數(shù)據(jù)元素的關(guān)鍵字Kj小于或者等于Ki時，將第i個數(shù)據(jù)元素插入到關(guān)鍵字為Kj的數(shù)據(jù)元素后面，即完成第i個數(shù)據(jù)元素的插入。③經(jīng)過n－1次插入操作后，所有數(shù)據(jù)元素構(gòu)成一個按關(guān)鍵字值大小排列的有序序列。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第10頁。數(shù)據(jù)元素序列{35，66，2，15，6，81，6*，9}進行直接插入排序的過程：數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第11頁。2．算法實現(xiàn)voidInsertSort(SeqList *L)//對順序表L作直接插入排序{inti,j;for(i=2;i<=L->Length;i++)//從第二個數(shù)據(jù)元素開始排序if(L->r[i].key<L->r[i-1].key) {//如果第i個數(shù)據(jù)元素的關(guān)鍵字小于其前面數(shù)據(jù)元素的關(guān)鍵字，則將其插入到有序表中L->r[0]=L->r[i]; //將待插入數(shù)據(jù)元素存入r[0]作為監(jiān)視哨//搜索插入位置，將有序表中大于待排關(guān)鍵字的數(shù)據(jù)元素后移for(j=i-1;L->r[0].key<L->r[j].key;j--)L->r[j+1]=L->r[j]; L->r[j+1]=L->r[0]; }}//將待排數(shù)據(jù)元素插入到第j個數(shù)據(jù)元素之后數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第12頁。3．算法分析（1）空間復雜度排序過程中僅使用了一個輔助單元r[0]，算法的空間復雜度為O(1)。（2）時間復雜度直接插入排序的時間復雜度為O(n2)。（3）穩(wěn)定性直接插入排序是一種穩(wěn)定的排序算法。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第13頁。二、折半插入排序1．算法實現(xiàn)2．算法分析數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第14頁。1．算法實現(xiàn)通過對有序表進行折半查找來確定插入位置，以減少關(guān)鍵字比較的次數(shù)。算法描述如下：voidBinSort(SeqList*L){//對順序表L作折半插入排序inti,j;intlow,high,mid;for(i=2;i<=L->length;i++) //從第2個元素開始排序{L->r[0]=L->r[i]; //將待插入數(shù)據(jù)元素存入r[0]作為監(jiān)視哨low=1;high=i-1; //設(shè)置初始查找區(qū)間while(low<=high) //搜索插入位置{mid=(low+high)/2; //求中間位置if(L->r[0].key<L->r[mid].key)high=mid–1;//在前半部分查找elselow=mid+1;} //在后半部分查找for(j=i-1;j>=low;j--) //將插入位置以后的數(shù)據(jù)元素后移L->r[j+1]=L->r[j];L->r[low]=L->r[0];}} //插入數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第15頁。2．算法分析（1）空間復雜度（2）時間復雜度（3）穩(wěn)定性排序過程中僅使用了一個輔助單元r[0]，算法的空間復雜度為O(1)。折半插入排序的時間復雜度為O(n2)。折半插入排序是一種穩(wěn)定的排序算法。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第16頁。三、希爾排序1．基本思想2．算法實現(xiàn)3．算法分析數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第17頁。1．基本思想將待排序數(shù)據(jù)元素劃分成若干個子序列，其中每個子序列由相隔某個“增量”的數(shù)據(jù)元素組成，然后對這些子序列分別進行直接插入排序，通過縮小“增量”對子序列進行調(diào)整。當整個序列基本有序時，對全部數(shù)據(jù)元素進行一次直接插入排序。具體過程：①按選定增量d1（d1＜n），將所有距離為d1的數(shù)據(jù)元素劃分為一個子序列，對各個子序列進行直接插入排序。②選定增量d2（d2＜d1），對所有數(shù)據(jù)元素重新進行劃分并對各子序列直接插入排序。③重復以上操作，直到增量di＝1，即將所有數(shù)據(jù)元素放在一個子序列中進行一次直接插入排序，最后得到所有數(shù)據(jù)元素按關(guān)鍵字有序排列的序列。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第18頁。2．算法實現(xiàn)voidShellInsert(SeqList *L,intdi) {//對順序表L作一趟希爾排序，di為增量inti,j;for(i=di+1;i<=L->Length;i++)if(L->r[i].key<L->r[i-di].key){//將第i個數(shù)據(jù)元素插入有序子序列L->r[0]=L->r[i]; //將第i個數(shù)據(jù)元素存入r[0]作為監(jiān)視哨//查找插入位置，將子序列內(nèi)插入位置后的數(shù)據(jù)元素后移for(j=i-di;j>0&&L->r[0].key<L->r[j].key;j=j-di)L->r[j+di]=L->r[j];L->r[j+di]=L->r[0];}}//插入數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第19頁。voidShellSort(SeqList*L,intd[],intt){//按增量序列d[]對順序表L作t趟希爾排序intk;for(k=0;k<t;k++)ShellInsert(L,d[k]); //一趟增量為d[k]的希爾排序}數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第20頁。3．算法分析（1）空間復雜度（2）時間復雜度（3）穩(wěn)定性排序過程中僅使用了一個輔助單元，算法的空間復雜度為O(1)。希爾排序是一種不穩(wěn)定的排序算法。在數(shù)據(jù)量較少時，利用直接插入排序的效率較高；當待排序的數(shù)據(jù)元素數(shù)目較大時，希爾排序方法一般要比直接插入排序方法快。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第21頁。任務(wù)三交換排序一、冒泡排序二、交換排序數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第22頁。一、冒泡排序1．基本思想2．算法實現(xiàn)3．算法分析數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第23頁。1．基本思想從頭掃描待排序的數(shù)據(jù)元素序列，依次比較相鄰兩個數(shù)據(jù)元素的關(guān)鍵字大小，如果逆序，則交換它們的位置，逐步將待排序列變成有序序列。具體過程：①對待排序數(shù)據(jù)元素序列進行第一趟掃描，依次比較相鄰兩個數(shù)據(jù)元素的關(guān)鍵字大小，如果前面數(shù)據(jù)元素的關(guān)鍵字大于后面數(shù)據(jù)元素的關(guān)鍵字，就將它們交換，這樣具有較大關(guān)鍵字的數(shù)據(jù)元素將不斷后移，最后，具有最大關(guān)鍵字的數(shù)據(jù)元素移動到最后一個位置上；②第二趟掃描僅需對前n－1個數(shù)據(jù)元素進行，重復以上操作，使具有次大關(guān)鍵字的數(shù)據(jù)元素移動到第n－1個位置；③依此類推，直到某一趟掃描過程中沒有發(fā)生數(shù)據(jù)元素的交換，則可結(jié)束冒泡排序。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第24頁。對數(shù)據(jù)元素序列（35，66，2，15，6，81，6*，9）進行冒泡排序：數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第25頁。2．算法實現(xiàn)voidBubbleSort(SeqList *L)//對順序表L作冒泡排序{inti,j,change;change=TRUE; //設(shè)置交換標志，初始值為TRUEfor(i=1;i<L->Length&&change;i++)//進行冒泡排序，無交換時結(jié)束{change=FALSE; //設(shè)置交換標志為FALSEfor(j=1;j<=L->Length-i;j++)//對未排好序的數(shù)據(jù)元素排序if(L->r[j].key>L->r[j+1].key)//比較相鄰兩個數(shù)據(jù)元素的大小{L->r[0]=L->r[j]; //要交換的數(shù)據(jù)元素暫時存入r[0]中L->r[j]=L->r[j+1];L->r[j+1]=L->r[0];change=TRUE;}}} //設(shè)置交換標志為TRUE數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第26頁。3．算法分析（1）空間復雜度（2）時間復雜度（3）穩(wěn)定性冒泡排序過程中僅使用了一個輔助單元，算法的空間復雜度為O(1)。冒泡排序的時間復雜度為O(n2)。冒泡排序是一種穩(wěn)定的排序算法。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第27頁。二、快速排序1．基本思想2．算法實現(xiàn)3．算法分析數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第28頁。1．基本思想從待排數(shù)據(jù)元素序列中選取一個數(shù)據(jù)元素為基準，通過一趟掃描將待排序列分成兩部分。其中一部分數(shù)據(jù)元素的關(guān)鍵字都小于或等于基準數(shù)據(jù)元素的關(guān)鍵字，而另一部分數(shù)據(jù)元素的關(guān)鍵字都大于或等于基準數(shù)據(jù)元素的關(guān)鍵字。對各部分不斷劃分，直到整個序列按關(guān)鍵字有序排列為止。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第29頁。具體過程如下：①選取待排序列中的第一個數(shù)據(jù)元素為基準，將其復制到r[0]中，并令該位置為空；設(shè)置兩個指針low和high，分別指向第一個數(shù)據(jù)元素和最后一個數(shù)據(jù)元素，即初始狀態(tài)時r[low]為空。②從后向前掃描，若r[high]的關(guān)鍵字大于或等于基準關(guān)鍵字，則high向前移動一個位置，直到r[high]的關(guān)鍵字小于基準關(guān)鍵字時，將r[high]與r[low]交換。③從前向后掃描，若r[low]的關(guān)鍵字小于或等于基準關(guān)鍵字，則low向后移動一個位置，直到r[low]的關(guān)鍵字大于基準關(guān)鍵字時，將r[low]與r[high]交換。④重復步驟②和③，直至low＝high時，令r[low]＝r[0]，以r[low]為基準將待排序列劃分為前后兩部分，第一次劃分完成。⑤按照以上方法，對各部分不斷劃分，直到各部分只有一個數(shù)據(jù)元素時，整個序列排序完成。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第30頁。對數(shù)據(jù)元素序列（35，66，2，15，6，81，6*，9）進行一趟快速排序的過程：數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第31頁。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第32頁。2．算法實現(xiàn)intPartition(SeqList*L,intlow,inthigh){//以第一個數(shù)據(jù)元素為基準進行一趟快排，返回排序后基準數(shù)據(jù)元素的位置L->r[0]=L->r[low]; //以序列中第一個數(shù)據(jù)元素為基準while(low<high) //從序列兩端交替向中間掃描{while(low<high&&L->r[high].key>=L->r[0].key)//從后向前掃描high--; //high指針前移L->r[low]=L->r[high];//將小于基準關(guān)鍵字的數(shù)據(jù)元素移到low所指位置while(low<high&&L->r[low].key<=L->r[0].key)//從前向后掃描low++; //low指針后移L->r[high]=L->r[low];}//將大于基準關(guān)鍵字的數(shù)據(jù)元素移到high所指位置L->r[low]=L->r[0]; //將基準數(shù)據(jù)元素移到low所指位置returnlow;} //返回排序后基準數(shù)據(jù)元素的位置voidQuickSort(SeqList*L,intlow,inthigh){//對順序表L作快速排序intp;if(low<high) //表長度大于1{p=Partition(L,low,high);//對L進行一趟快速排序，返回基準數(shù)據(jù)元素的位置QuickSort(L,low,p-1); //對表的前半部分進行快速排序QuickSort(L,p+1,high); //對表的后半部分進行快速排序}}數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第33頁。3．算法分析（1）空間復雜度（2）時間復雜度（3）穩(wěn)定性快速排序是一種不穩(wěn)定的排序算法。最好情況下為O(log2n)，最壞情況下為O(n)。最好情況下為O(log2n)，最壞情況下為O(n2)，平均時間復雜度為O(nlog2n)

。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第34頁。任務(wù)四選擇排序一、直接選擇排序二、樹形選擇排序三、堆排序數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第35頁。一、直接選擇排序1．基本思想2．算法實現(xiàn)3．算法分析數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第36頁。1．基本思想通過關(guān)鍵字的比較，每次從待排序列中選出關(guān)鍵字最小的數(shù)據(jù)元素，將其與待排序列的第一個數(shù)據(jù)元素交換，直到全部數(shù)據(jù)元素都有序排列。對于一個具有n個數(shù)據(jù)元素的序列，進行直接選擇排序的具體過程是：①進行第一趟排序時，用r[1]與其余n－1個數(shù)據(jù)元素比較，選出關(guān)鍵字最小的數(shù)據(jù)元素與r[1]交換。②進行第二趟排序時，用r[2]與其余n－2個數(shù)據(jù)元素比較，選出關(guān)鍵字最小的數(shù)據(jù)元素與r[2]交換。③依此類推，進行第i趟排序時，用r[i]與其余n－i個數(shù)據(jù)元素比較，選出關(guān)鍵字最小的數(shù)據(jù)元素與r[i]交換。共需進行i－1趟選擇，直到所有數(shù)據(jù)元素有序排列為止。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第37頁。對數(shù)據(jù)元素序列（35，66，2，15，6，81，6*，9）進行直接選擇排序的過程：數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第38頁。2．算法實現(xiàn)voidSelectSort(SeqList *L)//對順序表L作直接選擇排序{inti,j,t;for(i=1;i<L->Length;i++){進行第i趟排序時，選出待排序列中關(guān)鍵字最小的數(shù)據(jù)元素與r[i]交換t=i; //設(shè)置t的初值

for(j=i+1;j<=L->Length;j++)if(L->r[j].key<L->r[t].key)//找到待排序列中關(guān)鍵字最小的數(shù)據(jù)元素

t=j; //記錄關(guān)鍵字最小的數(shù)據(jù)元素的下標

if(t!=i) {//關(guān)鍵字最小的數(shù)據(jù)元素與第i個數(shù)據(jù)元素交換L->.r[0]=L->r[t];L->r[t]=L->r[i];L->.r[i]=L->r[0];}}}數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第39頁。3．算法分析（1）空間復雜度（2）時間復雜度（3）穩(wěn)定性直接選擇排序是一種不穩(wěn)定的排序算法。排序過程中僅使用了一個輔助單元，算法的空間復雜度為O(1)。直接選擇排序的平均時間復雜度為O(n2)。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第40頁。二、樹形選擇排序2．算法分析1．基本思想數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第41頁。1．基本思想對待排序列的所有數(shù)據(jù)元素進行兩兩比較，選出每兩個中的較小者，然后采取同樣方法對這些較小者再進行兩兩比較，如此反復，直至選出關(guān)鍵字最小的數(shù)據(jù)元素并輸出；將該數(shù)據(jù)元素置為∞，以便進行下一趟選擇排序，……當所有數(shù)據(jù)元素全部輸出，則排序完成。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第42頁。對數(shù)據(jù)元素序列（35，66，2，15，6，81，6*，9）進行樹形選擇排序的過程如下：數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第43頁。2．算法分析（1）空間復雜度（2）時間復雜度（3）穩(wěn)定性算法的空間復雜度為O(n)。時間復雜度為O(nlog2n)。樹形選擇排序是一種穩(wěn)定的排序方法。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第44頁。三、堆排序1．堆的定義2．基本思想3．算法實現(xiàn)4．算法分析數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第45頁。1．堆的定義n個關(guān)鍵字序列kl，k2，…，kn，當且僅當該序列滿足如下性質(zhì)時稱為堆。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第46頁。樹中任一非葉子結(jié)點的關(guān)鍵字均不大于或不小于其左右孩子結(jié)點的關(guān)鍵字。其中，前者稱為小頂堆，后者稱為大頂堆。堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第47頁。2．基本思想將待排序列初始化為大頂堆（或小頂堆），然后將堆頂數(shù)據(jù)元素與最后一個葉子結(jié)點交換，輸出該葉子結(jié)點表示的數(shù)據(jù)元素；然后將剩余的數(shù)據(jù)元素重新調(diào)整為大頂堆（或小頂堆），重復以上操作，直到所有數(shù)據(jù)元素有序輸出。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第48頁。對數(shù)據(jù)元素序列（35，66，2，15，6，81，6*，9）進行堆排序的過程如下所示。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第49頁。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第50頁。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第51頁。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第52頁。3．算法實現(xiàn)voidHeapAdjust(SeqList*L,ints,intm){//將順序表L中的r[s…m]調(diào)整為一個大頂堆intj;L->r[0]=L->r[s]; //保存根結(jié)點for(j=2*s;j<=m;j*=2) //沿關(guān)鍵字較大的孩子結(jié)點向下篩選{if(j<m&&L->r[j].key<L->r[j+1].key)j++; //令j為關(guān)鍵字較大的元素的下標if(L->r[0].key>=L->r[j].key)break; //若r[0]最大，將r[0]插入在位置s上else {L->.r[s]=L->r[j]; //將關(guān)鍵字最大的結(jié)點插入在位置ss=j;}} //沿關(guān)鍵字最大的結(jié)點進行下一層篩選L->r[s]=L->r[0];} //插入最后一個結(jié)點voidHeapSort(SeqList*L){//對順序表L進行堆排序inti,j;for(i=L->length/2;i>0;i--)//將r[s…m]調(diào)整為一個大頂堆HeapAdjust(L,i,L->length); for(i=L->length;i>1;i--){L->r[0]=L->r[1]; //將堆頂元素與最后一個元素交換L->r[1]=L->r[i];L->r[i]=L->r[0];HeapAdjust(L,1,i-1);}} //將L.r[1…i-1]重新調(diào)整為大頂堆數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第53頁。4．算法分析（1）空間復雜度（2）時間復雜度（3）穩(wěn)定性堆排序的時間復雜度為O(nlog2n)。堆排序是一種不穩(wěn)定的排序方法。堆排序僅使用了一個輔助單元，算法的空間復雜度為O(1)。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第54頁。任務(wù)五歸并排序和基數(shù)排序一、歸并排序二、基數(shù)排序數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第55頁。一、歸并排序1．基本思想2．算法實現(xiàn)3．算法分析數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第56頁。1．基本思想對于一個具有n個數(shù)據(jù)元素的序列，將其中的每個數(shù)據(jù)元素看成長度為1的有序子表，然后對其進行兩兩歸并，即第1個子表與第2個子表歸并，第3個子表與第4個子表歸并，依此類推，這樣得到n/2個長度為2的有序表（若n為奇數(shù)，則最后一個有序表的長度為1）；在此基礎(chǔ)上再進行兩兩歸并，得到n/4個長度為4的有序表（最后一個有序表的長度可能小于4），依此類推，直至得到一個長度為n的有序表為止。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第57頁。對數(shù)據(jù)元素序列（35，66，2，15，6，81，6*，9）進行歸并排序的過程如下圖所示。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第58頁。2．算法實現(xiàn)voidMerge(RecordTyper1[],RecordTyper2[],intlow,intmid,inthigh){//r1[low…mid]和r1[mid+1…h(huán)igh]分別按關(guān)鍵字有序排列，將它們合并為有序序列存放//在r2[low…h(huán)igh]中inti,j,k;i=low;j=mid+1;k=low;//i、j分別為指向r1[low…mid]和r1[mid+1…h(huán)igh]的指針，將r1中的數(shù)據(jù)元素由小到大并入r2中while((i<=mid)&&(j<=high)) {//值小的送入r2if(r1[i].key<r1[j].key) {r2[k]=r1[i]; //r1[low…mid]中的元素送入r2i++;} //指針i后移else{r2[k]=r1[j]; //r1[mid+1…h(huán)igh]中的元素送入r2j++;} //指針j后移k++;}while(i<=mid) //若r1[low…mid]中有元素剩余，直接將剩余元素復制到r2中{ r2[k]=r1[i]; k++; i++;}while(j<=high) //若r1[mid+1…h(huán)igh]中有元素剩余，直接將剩余元素復制到r2中{ r2[k]=r1[j]; k++; j++;}}voidMSort(RecordTyper1[],RecordTyper2[],intlow,inthigh){//將r1[low…h(huán)igh]歸并排序為r2[low…h(huán)igh]intmid;RecordType*r;r2=(RecordType*)malloc(sizeof(RecordType)*(high–low+1));//r2為輔助數(shù)組if(low==high) //若表長為1，則直接將r1復制到r2中r2[low]=r1[high];else{mid=(low+high)/2; //將r1[low…h(huán)igh]平分為兩個子序列MSort(r1,r,low,mid); //將r1[low…mid]歸并為r[low…mid]MSort(r1,r,mid+1,high);//將r1[mid+1…h(huán)igh]歸并為r[mid+1…h(huán)igh]Merge(r,r2,low,mid,high);}}//將有序的r[low…mid]和r[mid+1…h(huán)igh]歸并為有序的r2[low…h(huán)igh]voidMergeSort(SeqList*L){//對順序表L作歸并排序MSort(L->r,L->r,1,L->length);}數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第59頁。3．算法分析（1）空間復雜度（2）時間復雜度（3）穩(wěn)定性歸并排序的時間復雜度為O(nlog2n)。歸并排序是一種穩(wěn)定的排序方法。排序過程中需要一個與待排序列等長的輔助單元存放數(shù)據(jù)元素，因此，算法的空間復雜度為O(n)。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第60頁。二、基數(shù)排序2．基本思想3．算法實現(xiàn)4．算法分析1．基本概念數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第61頁。1．基本概念基數(shù)排序是一種基于多關(guān)鍵字排序思想進行排序的排序方法。例如，表8-2給出的某班學生成績單中包含了數(shù)學成績和英語成績（用A、B、C、D、E5個等級來表示），對該成績單先按數(shù)學成績的等級由高到低排序，數(shù)學成績相同的學生再按英語成績的等級由高到低排序。

高位優(yōu)先法（MostSignificantDigitfirst，簡稱MSD）：先按數(shù)學成績的等級由高到低將學生記錄分成A、B、C、D、E5組，再分別對每組記錄按英語成績的等級由高到低進行排序。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第62頁。低位優(yōu)先法（LeastSignificantDigitfirst，簡稱LSD）：先按英語成績的等級由高到低將學生記錄分成A、B、C、D、E5組，再將其按從左到右、從上到下的順序排列，得到關(guān)鍵字序列，如左圖所示；然后按數(shù)學成績的等級由高到低重新分成A、B、C、D、E5組，再將其按從左到右、從上到下的順序排列，得到關(guān)鍵字序列，如右圖所示；數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第63頁。2．基本思想根據(jù)基數(shù)的值設(shè)立相應(yīng)個數(shù)的隊列，排序時先按最低位子關(guān)鍵字的值進行排序，即按子關(guān)鍵字的不同值將各數(shù)據(jù)元素分配到相應(yīng)的隊列中，然后按照一定順序?qū)?shù)據(jù)元素收集起來，此時得到的序列已按最低位子關(guān)鍵字有序排列。在此基礎(chǔ)上按次低位子關(guān)鍵字的值進一步排序，依此類推，直至按關(guān)鍵字的最高位排序后，整個序列排序完成。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第64頁。例如，對數(shù)據(jù)元素序列{35，66，2，15，6，81，6*，9}進行基數(shù)排序的過程如下圖所示。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第65頁。數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第66頁。3．算法實現(xiàn)數(shù)據(jù)類型定義如下：#defineKEY_SIZE10 //關(guān)鍵字項數(shù)最大值#defineRADIX10 //關(guān)鍵字基數(shù)#defineLIST_SIZE20 //靜態(tài)鏈表的最大容量typedefstruct{KeyTypekey[KEY_SIZE]; //子關(guān)鍵字數(shù)組OtherTypotheritem; //其他數(shù)據(jù)項intnext; //靜態(tài)鏈表的指針域}RecordType;typedefstruct //定義靜態(tài)鏈表類型{RecordTyper[LIST_SIZE+1]; //r[0]為頭結(jié)點intkeynum; //當前關(guān)鍵字個數(shù)intlength; //靜態(tài)鏈表的當前長度}SLinkList; typedefintheadtail[RADIX]; //指針數(shù)組類型數(shù)據(jù)結(jié)構(gòu)項目八全文共71頁，當前為第67頁。算法描述如下：voidDistribute(SeqList*L,inti,headtailhead,headtailtail){//靜態(tài)鏈表L已按key[i+1]之后的關(guān)鍵字進行過“低位優(yōu)先”排序