新編-《數(shù)據(jù)結(jié)構(gòu)用C語言描述》第八章jsp課件

概述插入排序交換排序選擇排序歸并排序基數(shù)排序各種內(nèi)排方法比較第八章排序概述第八章排序1概述排序：將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。

數(shù)據(jù)表(datalist):它是待排序數(shù)據(jù)對(duì)象的有限集合。主關(guān)鍵字(key):數(shù)據(jù)對(duì)象有多個(gè)屬性域,即多個(gè)數(shù)據(jù)成員組成,其中有一個(gè)屬性域可用來區(qū)分對(duì)象,作為排序依據(jù)，稱為關(guān)鍵字。也稱為關(guān)鍵字。概述排序：將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵2排序方法的穩(wěn)定性:

如果在對(duì)象序列中有兩個(gè)對(duì)象r[i]和r[j],它們的關(guān)鍵字k[i]

==k[j]

,且在排序之前,對(duì)象r[i]排在r[j]前面。如果在排序之后,對(duì)象r[i]仍在對(duì)象r[j]的前面,則稱這個(gè)排序方法是穩(wěn)定的,否則稱這個(gè)排序方法是不穩(wěn)定的。內(nèi)排序與外排序:

內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。排序方法的穩(wěn)定性:如果在對(duì)象序列中有兩個(gè)對(duì)象r[i]和r3排序的時(shí)間開銷:排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來衡量。typedefstruct{intkey;datatypeother;}rectype;rectypeR[n];排序的時(shí)間開銷:排序的時(shí)間開銷是衡量算法好壞的最重要的4內(nèi)排序分類依不同原則 插入排序、交換排序、選擇排序、歸并排序、和基數(shù)排序等。依所須工作量 簡(jiǎn)單排序---時(shí)間復(fù)雜度o(n2) 先進(jìn)排序方法---時(shí)間復(fù)雜度o(nlogn) 基數(shù)排序---時(shí)間復(fù)雜度o(d.n)內(nèi)排序分類依不同原則5插入排序(InsertSorting)基本思想

當(dāng)插入第i(i1)個(gè)對(duì)象時(shí),前面的R[0],R[1],…,R[i-1]已經(jīng)排好序。這時(shí),用R[i]的關(guān)鍵字與R[i-1],R[i-2],…的關(guān)鍵字順序進(jìn)行比較,找到插入位置即將R[i]插入,原來位置上的對(duì)象向后順移。

基本思想每步將一個(gè)待排序的對(duì)象,按其關(guān)鍵字大小,插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上,直到對(duì)象全部插入為止。直接插入排序(InsertSort)插入排序(InsertSorting)基本思想當(dāng)插入第6直接插入排序過程012345tempi=1i=2012345temp2108254925*162125084925*16252125084925*162125084925*16492125084925*16i=32125084925*1625*2125084925*16直接插入排序過程0127i=4i=52125084925*1616162125084925*162125084925*162125084925*1608i=4i=52125084925*1616162128直接插入排序的算法InsertSort(rectypeR[],intn){inti,j;for(i=2;i<n;i++){R[0]=R[i];j=i–1;//從后向前順序比較

while(R[0].key<R[j].key)R[j+1]=R[j--];R[j+1]=R[0];}}直接插入排序的算法9算法分析設(shè)待排序?qū)ο髠€(gè)數(shù)為n,則該算法的主程序執(zhí)行n-1趟。關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵字的初始排列有關(guān)。最好情況下,排序前對(duì)象已按關(guān)鍵字從小到大有序,每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象比較1次,移動(dòng)2次對(duì)象,總的關(guān)鍵字比較次數(shù)為n-1,對(duì)象移動(dòng)次數(shù)為2(n-1)。算法分析設(shè)待排序?qū)ο髠€(gè)數(shù)為n,則該算法的主程序執(zhí)行n-110最壞情況下,第i趟時(shí)第i個(gè)對(duì)象必須與前面i個(gè)對(duì)象都做關(guān)鍵字比較,并且每做1次比較就要做1次數(shù)據(jù)移動(dòng)。則總關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN分別為在平均情況下的關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。最壞情況下,第i趟時(shí)第i個(gè)對(duì)象必須與前面i個(gè)對(duì)11折半插入排序(BinaryInsertsort)基本思想

設(shè)在順序表中有一個(gè)對(duì)象序列R[0],R[1],…,R[n-1]。其中,R[0],R[1],…,R[i-1]是已經(jīng)排好序的對(duì)象。在插入R[i]時(shí),利用折半搜索法尋找R[i]的插入位置。折半插入排序的算法折半插入排序(BinaryInsertsort)基本思想12typedefintSortData;RoidBinInsSort(SortDataR[],intn){SortDatatemp;intLeft,Right;

for(inti=1;i<n;i++){Left=0;Right=i-1;temp=R[i];while(Left<=Right){ intmid=(Left+Right)/2; if(temp<R[mid])Right=mid-1; elseLeft=mid+1;}for(intk=i-1;k>=Left;k--)R[k+1]=R[k];//記錄后移R[Left]=temp;//插入

}}typedefintSortData;13折半插入排序012345tempi=1i=2012345temp52133i=35521532144i=4215388i=52153161684421384516折半插入排序01214折半搜索比順序搜索查找快,所以折半插入排序就平均性能來說比直接插入排序要快。它所需的關(guān)鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān),僅依賴于對(duì)象個(gè)數(shù)。在插入第i個(gè)對(duì)象時(shí),需要經(jīng)過log2i+1次關(guān)鍵字比較,才能確定它應(yīng)插入的位置。因此,將n個(gè)對(duì)象(為推導(dǎo)方便,設(shè)為n=2k)用折半插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為：

算法分析

折半搜索比順序搜索查找快,所以折半插入排序就平均性能來說比15當(dāng)n較大時(shí),總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要好得多,但比其最好情況要差。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字排好序或接近有序時(shí),直接插入排序比折半插入排序執(zhí)行的關(guān)鍵字比較次數(shù)要少。折半插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同,依賴于對(duì)象的初始排列。折半插入排序是一個(gè)穩(wěn)定的排序方法。折半插入排序的時(shí)間復(fù)雜度為o(n2)。當(dāng)n較大時(shí),總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要16希爾排序(ShellSort)基本思想設(shè)待排序?qū)ο笮蛄杏衝個(gè)對(duì)象,首先取一個(gè)整數(shù)gap<n作為間隔,將全部對(duì)象分為gap個(gè)子序列,所有距離為gap的對(duì)象放在同一個(gè)子序列中,在每一個(gè)子序列中分別施行直接插入排序。然后縮小間隔gap,例如取gap=gap/2，重復(fù)上述的子序列劃分和排序工作。直到最后取gap==1,將所有對(duì)象放在同一個(gè)序列中排序?yàn)橹埂Ｏ柵判蚍椒ㄓ址Q為縮小增量排序。希爾排序(ShellSort)基本思想設(shè)待排序?qū)ο笮蛄杏?7i

=3Gap=30123452108254925*160123452108254925*16i

=2Gap=22108254925*162108254925*16i

=1Gap=12108254925*162108254925*16希爾排序過程i=3Gap=30118ShellSort(rectypeR[],intn){rectypetemp;intgap=n/2;//gap是間隔 while(gap!=0){ //循環(huán),直到gap為零for(inti=gap;i<n;i++){temp=R[i]; //直接插入排序for(intj=i;j>=gap;j=j-gap)if(temp<R[j-gap])R[j]=R[j-gap];elsebreak; R[j]=temp;} gap=(int)(gap/2);}}

希爾排序的算法ShellSort(rectypeR[],int19開始時(shí)gap的值較大,子序列中的對(duì)象較少,排序速度較快;隨著排序進(jìn)展,gap值逐漸變小,子序列中對(duì)象個(gè)數(shù)逐漸變多,由于前面大多數(shù)對(duì)象已基本有序,所以排序速度仍然很快。Gap的取法有多種。shell提出取gap=n/2，gap=gap/2，直到gap=1。對(duì)特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)鍵字的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。希爾排序所需的比較次數(shù)和移動(dòng)次數(shù)約為n1.3 當(dāng)n趨于無窮時(shí)可減少到n(log2n)2開始時(shí)gap的值較大,子序列中的對(duì)象較少,排序速度較20交換排序(ExchangeSort)基本方法設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為n。一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個(gè)記錄地關(guān)鍵字，如果發(fā)生逆序，則交換之，其結(jié)果是這n-i+1個(gè)記錄中，關(guān)鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。

基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字,如發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之,直到所有對(duì)象都排好序?yàn)橹?。起泡排?BubbleSort)交換排序(ExchangeSort)基本方法設(shè)待排序21210825492516214925251608214925251608214925251608214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過程21082549251621492525160821492522210825492516081621254925212516492125084925251621214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過程21082549251608162125492521251623起泡排序的算法BubbleSort(rectypeR[],intn){inti,j,noswap;rectypetemp;for(i=0;i<n-1;i++){noswap=1; //標(biāo)志置為1,假定未交換for(j=n-1;j>=i;j--)if(R[j+1].key<R[j].key) //逆序 {temp=R[j+1];//交換 R[j+1]=R[j];R[j]=temp;noswap=0;//標(biāo)志置為0,有交換}if(noswap)break;}}思考題：如何實(shí)現(xiàn)雙起泡起泡排序的算法24

第i趟對(duì)待排序?qū)ο笮蛄蠷[i-1],R[i],,R[n-1]進(jìn)行排序,結(jié)果將該序列中關(guān)鍵字最小的對(duì)象交換到序列的第一個(gè)位置(i-1),其它對(duì)象也都向排序的最終位置移動(dòng)。。最多做n-1趟起泡就能把所有對(duì)象排好序。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí),此算法只執(zhí)行一趟起泡,做n-1次關(guān)鍵字比較,不移動(dòng)對(duì)象。這是最好的情形。第i趟對(duì)待排序?qū)ο笮蛄蠷[i25最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1in)做n-i次關(guān)鍵字比較,執(zhí)行n-i次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：起泡排序是一個(gè)穩(wěn)定的排序方法。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1in)26快速排序(QuickSort)基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象(例如取第一個(gè)對(duì)象)作為基準(zhǔn),按照該對(duì)象的關(guān)鍵字大小,將整個(gè)對(duì)象序列劃分為左右兩個(gè)子序列：

左側(cè)子序列中所有對(duì)象的關(guān)鍵字都小于或等于基準(zhǔn)對(duì)象的關(guān)鍵字右側(cè)子序列中所有對(duì)象的關(guān)鍵字都大于基準(zhǔn)對(duì)象的關(guān)鍵字快速排序(QuickSort)基本思想是任取待排序?qū)ο笮?7基準(zhǔn)對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置)。然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止?；鶞?zhǔn)對(duì)象也稱為樞軸（或支點(diǎn)）記錄。基準(zhǔn)對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置28QuickSort(List){if(List的長(zhǎng)度大于1){ 將序列List劃分為兩個(gè)子序列LeftList和RightList;QuickSort(LeftList); QuickSort(RightList); 將兩個(gè)子序列LeftList和RightList 合并為一個(gè)序列List;}}快速排序算法描述QuickSort(List){快速排序算法描述29快速排序的過程2108254925*16初始關(guān)鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621prikey一次交換二次交換三次交換四次交換完成一趟排序ijijjiijjiji快速排序的過程2108254925*16初始關(guān)鍵字082543008254925*1621完成一趟排序分別進(jìn)行快速排序08254925*1621有序序列08254925*162108254925*1621完成一趟排序分別進(jìn)行快速排序08231

快速排序的算法QuickSort(rectypeR[],intlow,inthigh)//在序列l(wèi)owhigh中遞歸地進(jìn)行快速排序{if(low<high) {inti=Partition(R,low,high);//劃分

QuickSort(R,low,i-1);//對(duì)左序列同樣處理

QuickSort(R,i+1,high);//對(duì)右序列同樣處理}}快速排序的算法32intPartition(rectypeR[],intlow,inthigh){R[0]=R[low];//子表的第一個(gè)記錄作基準(zhǔn)對(duì)象tempkey=R[low].key;//基準(zhǔn)對(duì)象關(guān)鍵字While(low<high){While(low<high&&R[high].key>=tempkey)high--;R[low]=R[high];//小于基準(zhǔn)的移到區(qū)間的左側(cè)While(low<high&&R[low].key<=tempkey)low++;R[high]=R[low];//大于基準(zhǔn)的移到區(qū)間的右側(cè)}R[low]=R[0];returnlow;}intPartition(rectypeR[],33

算法quicksort是一個(gè)遞歸的算法,其遞歸樹如圖所示。算法partition利用序列第一個(gè)對(duì)象作為基準(zhǔn)，將整個(gè)序列劃分為左右兩個(gè)子序列。算法中執(zhí)行了一個(gè)循環(huán),只要是關(guān)鍵字小于基準(zhǔn)對(duì)象關(guān)鍵字的對(duì)象都移到序列左側(cè),最后基準(zhǔn)對(duì)象安放到位,函數(shù)返回其位置。2125*25490816算法quicksort是一個(gè)遞歸的算法,其遞歸樹如34算法分析快速排序的趟數(shù)取決于遞歸樹的高度。如果每次劃分對(duì)一個(gè)對(duì)象定位后,該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同,則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序,這是最理想的情況。在n個(gè)元素的序列中,對(duì)一個(gè)對(duì)象定位所需時(shí)間為O(n)。若設(shè)t(n)是對(duì)n個(gè)元素的序列進(jìn)行排序所需的時(shí)間,而且每次對(duì)一個(gè)對(duì)象正確定位后,正好把序列劃分為長(zhǎng)度相等的兩個(gè)子序列,此時(shí),總的計(jì)算時(shí)間為：算法分析快速排序的趟數(shù)取決于遞歸樹的高度。35

T(n)cn+2T(n/2)//c是一個(gè)常數(shù)cn+2(cn/2+2T(n/4))=2cn+4T(n/4)2cn+4(cn/4+2T(n/8))=3cn+8T(n/8)………cnlog2n+nT(1)=O(nlog2n)可以證明,函數(shù)quicksort的平均計(jì)算時(shí)間也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明:就平均計(jì)算時(shí)間而言,快速排序是所有內(nèi)排序方法中最好的一個(gè)?？焖倥判蚴沁f歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)。T(n)cn+2T(n/2)//36最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為log2(n+1)。因此，要求存儲(chǔ)開銷為O(log2n)。在最壞的情況,即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵字從小到大排好序的情況下,其遞歸樹成為單支樹,每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。總的關(guān)鍵字比較次數(shù)將達(dá)快速排序是一種不穩(wěn)定的排序方法。最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為log237

基本思想每一趟(例如第i趟,i=0,1,…,n-2)在后面n-i個(gè)待排序記錄中選出關(guān)鍵字最小的記錄,作為有序序列中的第i個(gè)記錄。待到第n-2趟作完,待排序記錄只剩下1個(gè),就不用再選了。選擇排序基本思想每一趟(例如第i趟,選擇排序38直接選擇排序是一種簡(jiǎn)單的排序方法,它的基本步驟是：在一組對(duì)象R[i]～R[n-1]中選擇具有最小關(guān)鍵字的對(duì)象；若它不是這組對(duì)象中的第一個(gè)對(duì)象,則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào);在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵字的對(duì)象。在剩下的對(duì)象R[i+1]～R[n-1]中重復(fù)執(zhí)行第①、②步,直到剩余對(duì)象只有一個(gè)為止。直接選擇排序(SelectSort)直接選擇排序是一種簡(jiǎn)單的排序方法,它的基本步驟是：直接選3921254925*16080123452125*i=0492516251608490825*4921i=1i=2081625*2521初始最小者08交換21,08最小者16交換25,16最小者21交換49,21

直接選擇排序的過程21254925*16080140最小者25*無交換4925*01234525*i=42516084925*4921結(jié)果i=308162521最小者25無交換25211608各趟排序后的結(jié)果最小者25*4925*0141 直接選擇排序的算法SelectSort(rectypeR[],intn){inti,j,k;rectypetemp;for(i=0;i<n-1;i++){k=i;//選擇具有最小關(guān)鍵字的對(duì)象for(j=i+1;j<n;j++)if(R[j].key<R[k].key)k=j;//當(dāng)前具最小關(guān)鍵字的對(duì)象if(k!=i)//對(duì)換到第i個(gè)位置 {temp=R[i];R[i]=R[k];R[k]=temp;} }} 直接選擇排序的算法42直接選擇排序的關(guān)鍵字比較次數(shù)KCN與對(duì)象的初始排列無關(guān)。設(shè)整個(gè)待排序?qū)ο笮蛄杏衝個(gè)對(duì)象,則第i趟選擇具有最小關(guān)鍵字對(duì)象所需的比較次數(shù)總是n-i-1次?？偟年P(guān)鍵字比較次數(shù)為對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時(shí)候,對(duì)象的移動(dòng)次數(shù)RMN=0，達(dá)到最少。最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為RMN=3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。直接選擇排序的關(guān)鍵字比較次數(shù)KCN與對(duì)象的初始排列無關(guān)。43堆排序(Heapsort)堆(Heap)設(shè)有一個(gè)關(guān)鍵字集合，按完全二叉樹的順序存儲(chǔ)方式存放在一個(gè)一維數(shù)組中。對(duì)它們從根開始，自頂向下，同一層自左向右從0開始連續(xù)編號(hào)。若滿足

Ki

K2i&&KiK2i+1或Ki

K2i&&KiK2i+1,則稱該關(guān)鍵字集合構(gòu)成一個(gè)堆。前者成為小根堆，后者稱為大根堆。堆排序(Heapsort)堆(Heap)設(shè)有一個(gè)44完全二叉樹順序表示Ki

K2i&KiK2i+1完全二叉樹順序表示Ki

K2i&&KiK2i+1090987877878454565653131532323531717完全二叉樹完全二叉樹0909878778784545656545堆排序(HeapSort)利用堆及其運(yùn)算,可以很容易地實(shí)現(xiàn)選擇排序的思路。堆排序分為兩個(gè)步驟根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法SIFT()形成初始堆;通過一系列的對(duì)象交換和重新調(diào)整堆進(jìn)行排序。堆排序(HeapSort)46自下向上逐步調(diào)整為小根堆5353171778780923456587i0923456587i=4i=3i初始小根堆的建立過程自下向上逐步調(diào)整為小根堆535317177878092345475353171778780923456587i0923456587i=2i5353171778780923456587i09234564853171778780923456587i0923456587i=1i5353171778780923456587i0923456584953171778780923456587i0923456587i53建成堆53171778780923456587i09234565850初始大根堆的建立過程212525*491608123456i212525*164908136542i初始關(guān)鍵字集合i=3時(shí)的局部調(diào)整初始大根堆的建立過程212525*491608123456i51212525*491608123456i492525*162108136542i=1時(shí)的局部調(diào)整形成大根堆i=2時(shí)的局部調(diào)整212525*491608123456i492525*16252大根堆的篩選算法SIFT(rectypeR[],inti,intm){intj=2*i;rectypetemp=R[i];while(j<=m){if(j<m&&R[j].key<R[j+1].key) j=j+1;//選兩子女的大者if(temp.key>=R[j])break;else{

大根堆的篩選算法SIFT(rectypeR[],i53

R[i]=R[j];//大子女上移i=j;j=2*i;//向下繼續(xù)調(diào)整}}R[i]=temp;//回放到合適位置}將表轉(zhuǎn)換成堆for(i=n/2;i>=1;i--)SIFT(R,i,n);

R[i]=R[j];54基于初始堆(大頂堆)進(jìn)行堆排序最大堆堆頂R[0]具有最大的關(guān)鍵字,將R[0]與R[n-1]對(duì)調(diào),把具有最大關(guān)鍵字的對(duì)象交換到最后,再對(duì)前面的n-1個(gè)對(duì)象,使用堆的調(diào)整算法SIFT(0,n-2),重新建立最大堆,具有次最大關(guān)鍵字的對(duì)象又上浮到R[0]位置。再對(duì)調(diào)R[0]和R[n-2],調(diào)用SIFT(0,n-3),對(duì)前n-2個(gè)對(duì)象重新調(diào)整，…。如此反復(fù)執(zhí)行，最后得到全部排序好的對(duì)象序列。這個(gè)算法即堆排序算法，基于初始堆(大頂堆)進(jìn)行堆排序最大堆堆頂R[0]具有最大的關(guān)55492525*211608012345082525*16214902543149252125*160808252125*1649交換0號(hào)與5號(hào)對(duì)象,5號(hào)對(duì)象就位初始最大堆基于初始堆進(jìn)行堆排序492525*211608012345082525*1621562525*082116490123451625*082521490254312525*210816491625*210825

49交換0號(hào)與4號(hào)對(duì)象,4號(hào)對(duì)象就位從0號(hào)到4號(hào)重新調(diào)整為最大堆2525*082116490123451625*0825215725*1608212549012345081625*25214902543125*16210825

4908162125*

25

49交換0號(hào)與3號(hào)對(duì)象,3號(hào)對(duì)象就位從0號(hào)到3號(hào)重新調(diào)整為最大堆25*1608212549012345081625*252158211625*082549012345081625*25214902543121160825*

25

49081621

25*

25

49交換0號(hào)與2號(hào)對(duì)象,2號(hào)對(duì)象就位從0號(hào)到2號(hào)重新調(diào)整為最大堆211625*082549012345081625*252159160825*212549012345081625*25214902543116082125*

25

490816

21

25*

25

49交換0號(hào)與1號(hào)對(duì)象,1號(hào)對(duì)象就位從0號(hào)到1號(hào)重新調(diào)整為最大堆160825*212549012345081625*252160堆排序的算法HeapSort(rectypeR[])//對(duì)表R[1]到R[n]進(jìn)行排序,使得表中對(duì)象關(guān)鍵字非遞減有序。{inti;rectypetemp;for(i=n/2;i>=1;i--)SIFT(R,i,n);//初始堆for(i=n;i>=1;i--){temp=R[1];R[1]=R[i];//交換R[i]=temp;SIFT(R,1,i-1); //重建最大堆}}堆排序的算法61若設(shè)堆中有n個(gè)結(jié)點(diǎn),且2k-1

n2k,則對(duì)應(yīng)的完全二叉樹有k層。在第i層上的結(jié)點(diǎn)數(shù)2i(i=0,1,…,k-1)。在第一個(gè)形成初始堆的for循環(huán)中對(duì)每一個(gè)非葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法SIFT(),因此該循環(huán)所用的計(jì)算時(shí)間為：其中,i是層序號(hào),2i是第i層的最大結(jié)點(diǎn)數(shù),(k-i-1)是第i層結(jié)點(diǎn)能夠移動(dòng)的最大距離。堆排序的算法分析若設(shè)堆中有n個(gè)結(jié)點(diǎn),且2k-1n2k,62第二個(gè)for循環(huán)中調(diào)用了n-1次SIFT()算法,該循環(huán)的計(jì)算時(shí)間為O(nlog2n)。因此,堆排序的時(shí)間復(fù)雜性為O(nlog2n)。該算法的附加存儲(chǔ)主要是在第二個(gè)for循環(huán)中用來執(zhí)行對(duì)象交換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個(gè)不穩(wěn)定的排序方法。第二個(gè)for循環(huán)中調(diào)用了n-1次SIFT()算法,該循環(huán)63歸并排序(MergeSort)歸并將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。兩路歸并(2-waymerging)原始序列R[]中兩個(gè)有序表R[l]…R[m]和R[m+1]…R[n]，它們可歸并成一個(gè)有序表,存于另一對(duì)象序列R1的l…n中。歸并排序(MergeSort)歸并將兩個(gè)或兩個(gè)以上的有序6408212525*49627293163754lowmidmid+1highR0816212525*374954627293lowhighkR1設(shè)變量i和j是表R[l…m]和R[m+1…n]的當(dāng)前檢測(cè)指針。k是存放指針。當(dāng)i和j都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí),根據(jù)對(duì)應(yīng)項(xiàng)的關(guān)鍵字的大小,依次把關(guān)鍵字小的對(duì)象排放到新表k所指位置中；當(dāng)i與j中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一個(gè)表中的剩余部分照抄到新表中。ij08212525*4962729365merge(rectypeR[],rectypeR1[],intlow,intmid,inthigh){inti=low,j=mid+1,k=low; while(i<=mid&&j<=high)//兩兩比較將較小的并入if(R[i]<=R[j]){R1[k]=R[i];i++;k++;}else{R1[k]=R[j];j++;k++;}while(i<=mid){R1[k]=R[i];i++;k++;}//將mid前剩余的并入while(j<=high){R1[k]=R[j];j++;k++;}//將mid后剩余的并入} 兩路歸并算法merge(rectypeR[],rectype66一趟歸并排序的情形設(shè)R[0]到R[n-1]中n個(gè)對(duì)象已經(jīng)分為一些長(zhǎng)度為len的歸并項(xiàng),將這些歸并項(xiàng)兩兩歸并,歸并成長(zhǎng)度為2len的歸并項(xiàng),結(jié)果放到R1[]中。如果n不是2len的整數(shù)倍,則一趟歸并到最后,可能遇到兩種情形：剩下一個(gè)長(zhǎng)度為len的歸并項(xiàng)和另一個(gè)長(zhǎng)度不足len的歸并項(xiàng),可用merge算法將它們歸并成一個(gè)長(zhǎng)度小于2len的歸并項(xiàng)。只剩下一個(gè)歸并項(xiàng)，其長(zhǎng)度小于或等于len,將它直接抄到R1[]中。一趟歸并排序的情形設(shè)R[0]到R[n-1]中n個(gè)對(duì)象已經(jīng)67迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過程進(jìn)行排序的。其基本思想是：假設(shè)初始對(duì)象序列有n個(gè)對(duì)象，首先把它看成是n個(gè)長(zhǎng)度為1的有序子序列(歸并項(xiàng))，先做兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的歸并項(xiàng)(如果n為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為1)；再做兩兩歸并，…，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為n的有序序列。迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過程進(jìn)行68迭代的歸并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16迭代的歸并排序算法212525*25*9362720837169MergePass(rectypeR[],rectypeR1[],intlen){inti=0;while(i+2*len-1<=n-1){merge(R,R1,i,i+len-1,i+2*len-1);i+=2*len;//循環(huán)兩兩歸并}if(i+len<=n-1)merge(R,R1,i,i+len-1,n-1);elsefor(intj=i;j<=n-1;j++)R1[j]=R[j];}MergePass(rectypeR[],rec70歸并排序的主算法MergeSort(rectypeR[],intn){//按對(duì)象關(guān)鍵字非遞減的順序?qū)Ρ碇袑?duì)象排序rectypeR1[n];intlen=1;while(len<n){MergePass(R,R1,len);len*=2; MergePass(R1,R,len);len*=2;}}歸并排序的主算法71在迭代的歸并排序算法中,函數(shù)MergePass()做一趟兩路歸并排序,要調(diào)用merge()函數(shù)n/(2*len)

O(n/len)次,函數(shù)MergeSort()調(diào)用MergePass()正好log2n次,而每次merge()要執(zhí)行比較O(len)次,所以算法總的時(shí)間復(fù)雜度為O(nlog2n)。歸并排序占用附加存儲(chǔ)較多,需要另外一個(gè)與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個(gè)算法的缺點(diǎn)。歸并排序是一個(gè)穩(wěn)定的排序方法。在迭代的歸并排序算法中,函數(shù)MergePass()做一72基數(shù)排序多關(guān)鍵字排序例對(duì)52張撲克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A兩個(gè)關(guān)鍵字：花色（<<<）

面值（2<3<……<A）并且“花色”地位高于“面值”多關(guān)鍵字排序方法最高位優(yōu)先法（MSD)：先對(duì)最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對(duì)最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個(gè)有序序列基數(shù)排序多關(guān)鍵字排序73最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字排序，……依次重復(fù)，直至對(duì)最高位關(guān)鍵字k1排序后，便成為一個(gè)有序序列鏈?zhǔn)交鶖?shù)排序基數(shù)排序：借助“分配”和“收集”對(duì)單邏輯關(guān)鍵字進(jìn)行排序的一種方法鏈?zhǔn)交鶖?shù)排序方法：用鏈表作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序設(shè)置10個(gè)隊(duì)列，f[i]和e[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針第一趟分配對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至10個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進(jìn)行排序，然后再74第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將10個(gè)隊(duì)列鏈成一個(gè)鏈表重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對(duì)十位、百位進(jìn)行，最后得到一個(gè)有序序列第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一75例：初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：例：初始狀態(tài)：2781090639305891845052676505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：50500810993006326927808318458977008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集：00806308310918426927850558993078各種排序方法的比較各種排序方法的比較79概述插入排序交換排序選擇排序歸并排序基數(shù)排序各種內(nèi)排方法比較第八章排序概述第八章排序80概述排序：將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。

數(shù)據(jù)表(datalist):它是待排序數(shù)據(jù)對(duì)象的有限集合。主關(guān)鍵字(key):數(shù)據(jù)對(duì)象有多個(gè)屬性域,即多個(gè)數(shù)據(jù)成員組成,其中有一個(gè)屬性域可用來區(qū)分對(duì)象,作為排序依據(jù)，稱為關(guān)鍵字。也稱為關(guān)鍵字。概述排序：將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵81排序方法的穩(wěn)定性:

如果在對(duì)象序列中有兩個(gè)對(duì)象r[i]和r[j],它們的關(guān)鍵字k[i]

==k[j]

,且在排序之前,對(duì)象r[i]排在r[j]前面。如果在排序之后,對(duì)象r[i]仍在對(duì)象r[j]的前面,則稱這個(gè)排序方法是穩(wěn)定的,否則稱這個(gè)排序方法是不穩(wěn)定的。內(nèi)排序與外排序:

內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。排序方法的穩(wěn)定性:如果在對(duì)象序列中有兩個(gè)對(duì)象r[i]和r82排序的時(shí)間開銷:排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來衡量。typedefstruct{intkey;datatypeother;}rectype;rectypeR[n];排序的時(shí)間開銷:排序的時(shí)間開銷是衡量算法好壞的最重要的83內(nèi)排序分類依不同原則 插入排序、交換排序、選擇排序、歸并排序、和基數(shù)排序等。依所須工作量 簡(jiǎn)單排序---時(shí)間復(fù)雜度o(n2) 先進(jìn)排序方法---時(shí)間復(fù)雜度o(nlogn) 基數(shù)排序---時(shí)間復(fù)雜度o(d.n)內(nèi)排序分類依不同原則84插入排序(InsertSorting)基本思想

當(dāng)插入第i(i1)個(gè)對(duì)象時(shí),前面的R[0],R[1],…,R[i-1]已經(jīng)排好序。這時(shí),用R[i]的關(guān)鍵字與R[i-1],R[i-2],…的關(guān)鍵字順序進(jìn)行比較,找到插入位置即將R[i]插入,原來位置上的對(duì)象向后順移。

基本思想每步將一個(gè)待排序的對(duì)象,按其關(guān)鍵字大小,插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上,直到對(duì)象全部插入為止。直接插入排序(InsertSort)插入排序(InsertSorting)基本思想當(dāng)插入第85直接插入排序過程012345tempi=1i=2012345temp2108254925*162125084925*16252125084925*162125084925*16492125084925*16i=32125084925*1625*2125084925*16直接插入排序過程01286i=4i=52125084925*1616162125084925*162125084925*162125084925*1608i=4i=52125084925*16161621287直接插入排序的算法InsertSort(rectypeR[],intn){inti,j;for(i=2;i<n;i++){R[0]=R[i];j=i–1;//從后向前順序比較

while(R[0].key<R[j].key)R[j+1]=R[j--];R[j+1]=R[0];}}直接插入排序的算法88算法分析設(shè)待排序?qū)ο髠€(gè)數(shù)為n,則該算法的主程序執(zhí)行n-1趟。關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵字的初始排列有關(guān)。最好情況下,排序前對(duì)象已按關(guān)鍵字從小到大有序,每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象比較1次,移動(dòng)2次對(duì)象,總的關(guān)鍵字比較次數(shù)為n-1,對(duì)象移動(dòng)次數(shù)為2(n-1)。算法分析設(shè)待排序?qū)ο髠€(gè)數(shù)為n,則該算法的主程序執(zhí)行n-189最壞情況下,第i趟時(shí)第i個(gè)對(duì)象必須與前面i個(gè)對(duì)象都做關(guān)鍵字比較,并且每做1次比較就要做1次數(shù)據(jù)移動(dòng)。則總關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN分別為在平均情況下的關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。最壞情況下,第i趟時(shí)第i個(gè)對(duì)象必須與前面i個(gè)對(duì)90折半插入排序(BinaryInsertsort)基本思想

設(shè)在順序表中有一個(gè)對(duì)象序列R[0],R[1],…,R[n-1]。其中,R[0],R[1],…,R[i-1]是已經(jīng)排好序的對(duì)象。在插入R[i]時(shí),利用折半搜索法尋找R[i]的插入位置。折半插入排序的算法折半插入排序(BinaryInsertsort)基本思想91typedefintSortData;RoidBinInsSort(SortDataR[],intn){SortDatatemp;intLeft,Right;

for(inti=1;i<n;i++){Left=0;Right=i-1;temp=R[i];while(Left<=Right){ intmid=(Left+Right)/2; if(temp<R[mid])Right=mid-1; elseLeft=mid+1;}for(intk=i-1;k>=Left;k--)R[k+1]=R[k];//記錄后移R[Left]=temp;//插入

}}typedefintSortData;92折半插入排序012345tempi=1i=2012345temp52133i=35521532144i=4215388i=52153161684421384516折半插入排序01293折半搜索比順序搜索查找快,所以折半插入排序就平均性能來說比直接插入排序要快。它所需的關(guān)鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān),僅依賴于對(duì)象個(gè)數(shù)。在插入第i個(gè)對(duì)象時(shí),需要經(jīng)過log2i+1次關(guān)鍵字比較,才能確定它應(yīng)插入的位置。因此,將n個(gè)對(duì)象(為推導(dǎo)方便,設(shè)為n=2k)用折半插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為：

算法分析

折半搜索比順序搜索查找快,所以折半插入排序就平均性能來說比94當(dāng)n較大時(shí),總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要好得多,但比其最好情況要差。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字排好序或接近有序時(shí),直接插入排序比折半插入排序執(zhí)行的關(guān)鍵字比較次數(shù)要少。折半插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同,依賴于對(duì)象的初始排列。折半插入排序是一個(gè)穩(wěn)定的排序方法。折半插入排序的時(shí)間復(fù)雜度為o(n2)。當(dāng)n較大時(shí),總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要95希爾排序(ShellSort)基本思想設(shè)待排序?qū)ο笮蛄杏衝個(gè)對(duì)象,首先取一個(gè)整數(shù)gap<n作為間隔,將全部對(duì)象分為gap個(gè)子序列,所有距離為gap的對(duì)象放在同一個(gè)子序列中,在每一個(gè)子序列中分別施行直接插入排序。然后縮小間隔gap,例如取gap=gap/2，重復(fù)上述的子序列劃分和排序工作。直到最后取gap==1,將所有對(duì)象放在同一個(gè)序列中排序?yàn)橹?。希爾排序方法又稱為縮小增量排序。希爾排序(ShellSort)基本思想設(shè)待排序?qū)ο笮蛄杏?6i

=3Gap=30123452108254925*160123452108254925*16i

=2Gap=22108254925*162108254925*16i

=1Gap=12108254925*162108254925*16希爾排序過程i=3Gap=30197ShellSort(rectypeR[],intn){rectypetemp;intgap=n/2;//gap是間隔 while(gap!=0){ //循環(huán),直到gap為零for(inti=gap;i<n;i++){temp=R[i]; //直接插入排序for(intj=i;j>=gap;j=j-gap)if(temp<R[j-gap])R[j]=R[j-gap];elsebreak; R[j]=temp;} gap=(int)(gap/2);}}

希爾排序的算法ShellSort(rectypeR[],int98開始時(shí)gap的值較大,子序列中的對(duì)象較少,排序速度較快;隨著排序進(jìn)展,gap值逐漸變小,子序列中對(duì)象個(gè)數(shù)逐漸變多,由于前面大多數(shù)對(duì)象已基本有序,所以排序速度仍然很快。Gap的取法有多種。shell提出取gap=n/2，gap=gap/2，直到gap=1。對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)鍵字的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。希爾排序所需的比較次數(shù)和移動(dòng)次數(shù)約為n1.3 當(dāng)n趨于無窮時(shí)可減少到n(log2n)2開始時(shí)gap的值較大,子序列中的對(duì)象較少,排序速度較99交換排序(ExchangeSort)基本方法設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為n。一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個(gè)記錄地關(guān)鍵字，如果發(fā)生逆序，則交換之，其結(jié)果是這n-i+1個(gè)記錄中，關(guān)鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。

基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字,如發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之,直到所有對(duì)象都排好序?yàn)橹?。起泡排?BubbleSort)交換排序(ExchangeSort)基本方法設(shè)待排序100210825492516214925251608214925251608214925251608214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過程210825492516214925251608214925101210825492516081621254925212516492125084925251621214925251608初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序的過程210825492516081621254925212516102起泡排序的算法BubbleSort(rectypeR[],intn){inti,j,noswap;rectypetemp;for(i=0;i<n-1;i++){noswap=1; //標(biāo)志置為1,假定未交換for(j=n-1;j>=i;j--)if(R[j+1].key<R[j].key) //逆序 {temp=R[j+1];//交換 R[j+1]=R[j];R[j]=temp;noswap=0;//標(biāo)志置為0,有交換}if(noswap)break;}}思考題：如何實(shí)現(xiàn)雙起泡起泡排序的算法103

第i趟對(duì)待排序?qū)ο笮蛄蠷[i-1],R[i],,R[n-1]進(jìn)行排序,結(jié)果將該序列中關(guān)鍵字最小的對(duì)象交換到序列的第一個(gè)位置(i-1),其它對(duì)象也都向排序的最終位置移動(dòng)。。最多做n-1趟起泡就能把所有對(duì)象排好序。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí),此算法只執(zhí)行一趟起泡,做n-1次關(guān)鍵字比較,不移動(dòng)對(duì)象。這是最好的情形。第i趟對(duì)待排序?qū)ο笮蛄蠷[i104最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1in)做n-i次關(guān)鍵字比較,執(zhí)行n-i次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：起泡排序是一個(gè)穩(wěn)定的排序方法。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1in)105快速排序(QuickSort)基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象(例如取第一個(gè)對(duì)象)作為基準(zhǔn),按照該對(duì)象的關(guān)鍵字大小,將整個(gè)對(duì)象序列劃分為左右兩個(gè)子序列：

左側(cè)子序列中所有對(duì)象的關(guān)鍵字都小于或等于基準(zhǔn)對(duì)象的關(guān)鍵字右側(cè)子序列中所有對(duì)象的關(guān)鍵字都大于基準(zhǔn)對(duì)象的關(guān)鍵字快速排序(QuickSort)基本思想是任取待排序?qū)ο笮?06基準(zhǔn)對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置)。然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止?；鶞?zhǔn)對(duì)象也稱為樞軸（或支點(diǎn)）記錄。基準(zhǔn)對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置107QuickSort(List){if(List的長(zhǎng)度大于1){ 將序列List劃分為兩個(gè)子序列LeftList和RightList;QuickSort(LeftList); QuickSort(RightList); 將兩個(gè)子序列LeftList和RightList 合并為一個(gè)序列List;}}快速排序算法描述QuickSort(List){快速排序算法描述108快速排序的過程2108254925*16初始關(guān)鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621prikey一次交換二次交換三次交換四次交換完成一趟排序ijijjiijjiji快速排序的過程2108254925*16初始關(guān)鍵字0825410908254925*1621完成一趟排序分別進(jìn)行快速排序08254925*1621有序序列08254925*162108254925*1621完成一趟排序分別進(jìn)行快速排序082110

快速排序的算法QuickSort(rectypeR[],intlow,inthigh)//在序列l(wèi)owhigh中遞歸地進(jìn)行快速排序{if(low<high) {inti=Partition(R,low,high);//劃分

QuickSort(R,low,i-1);//對(duì)左序列同樣處理

QuickSort(R,i+1,high);//對(duì)右序列同樣處理}}快速排序的算法111intPartition(rectypeR[],intlow,inthigh){R[0]=R[low];//子表的第一個(gè)記錄作基準(zhǔn)對(duì)象tempkey=R[low].key;//基準(zhǔn)對(duì)象關(guān)鍵字While(low<high){While(low<high&&R[high].key>=temp