第八章-內(nèi)排序【】?jī)?yōu)秀文檔

第八章內(nèi)排序宋國(guó)杰北京大學(xué)信息科學(xué)技術(shù)學(xué)院28.3Shell排序直接插入排序的兩個(gè)性質(zhì)在最好情況（序列本身已是有序的）下時(shí)間代價(jià)為Θ(n)對(duì)于短序列，直接插入排序比較有效Shell排序有效地利用了這兩個(gè)性質(zhì)Shell排序又稱為“縮小增量排序”，1959年由提出Shell排序又稱為“縮小增量排序”，1959年由提出總的排序碼比較次數(shù)將達(dá)if(left<right){ //如果序列中只有0或1個(gè)記錄，就不用排序分割后使得L中所有記錄位于軸值左邊，R中記錄位于軸值右邊，即軸值已位于正確位置//依次找出剩余記錄中的最大記錄，即堆頂“delta=2”的Shell排序if(right<=left) //如果子序列中只有0或1個(gè)記錄，就不需排序希爾排序是一種不穩(wěn)定的排序方法elseArray[k]=TempArray[index2--];classQuickSorter:publicSorter<Record,Compare>{ //快速排序類elseInsertSort(&Array[left],right-left+1);直接選擇排序：直接從剩余記錄中線性查找最大(小)記錄template<classRecord,classCompare>ModMerge(Array,TempArray,left,right,middle);//進(jìn)行歸并if(right-left+1>THRESHOLD){把數(shù)組暫時(shí)復(fù)制到臨時(shí)數(shù)組時(shí)，將第二個(gè)子數(shù)組中元素的順序顛倒了一下?；舅枷胂葘⒋判蛐蛄修D(zhuǎn)化為若干小序列（距離相同的間隔gap），在這些小序列內(nèi)進(jìn)行插入排序逐漸擴(kuò)大小序列的規(guī)模，而減少小序列個(gè)數(shù)(以delta縮小間隔)，使得待排序序列逐漸處于更有序的狀態(tài)最后對(duì)整個(gè)序列進(jìn)行掃尾直接插入排序，從而完成排序形式化描述選定一個(gè)增量序列n>d1>d2>…>dt=1，

其中n—文件長(zhǎng)度；

di

(1≤i≤t)——增量(正整數(shù))；

t——增量個(gè)數(shù)、排序趟數(shù)。將文件按d1

分組，彼此相距

d1

的記錄劃為一組，在各組內(nèi)采用直接插入法進(jìn)行排序。分別按d2,…dt

重復(fù)上述分組和排序工作。Shell

最初提出的增量序列是

d1=n

/2，di+1=di

/25Shell排序過程6“delta=2”的Shell排序template<classRecord,classCompare>VoidShellSorter<Record,Compare>::Sort(RecordArray[],intn){ //Shell排序，Array[]為待排序數(shù)組，

//n為數(shù)組長(zhǎng)度

//增量delta每次除以2遞減

for(intdelta=n/2;delta>0;delta/=2) //分別對(duì)delta個(gè)子序列排序

for(intj=0;j<delta;j++)

ModifiedInsertSort(&Array[j],n-j,delta);}7template<classRecord,classCompare>voidShellSorter<Record,Compare>::ModifiedInsertSort(RecordArray[],intn,intdelta){ //參數(shù)delta表示當(dāng)前的增量

//對(duì)子序列中第i個(gè)記錄排序

for(inti=delta;i<n;i+=delta) for(intj=i;j>=delta;j-=delta){ if(Array[j]<Array[j-delta]) swap(Array,j,j-delta); elsebreak; }}分析增量序列可有各種取法：任何正整數(shù)的遞減序列d1,d2,…dt,只要d1<n,dt=1,原則上都可作為希爾排序的增量序列Hibbard增量序列{2k-1，2k-1-1，…，7，3，1}，Hibbard增量序列的Shell排序的效率可以達(dá)到Θ(n3/2)

選取其他增量序列還可以更進(jìn)一步減少時(shí)間代價(jià)希爾排序是一種不穩(wěn)定的排序方法898.4基于分治法的排序“分而治之”的思想將原始序列分為若干個(gè)子部分,然后分別進(jìn)行排序該思想是解決問題的重要方法之一兩種算法快速排序（quicksorting）歸并排序（mergesorting）

快速排序(霍爾)1962.11快速排序基本思想首先，從待排序序列S中任意選擇一個(gè)記錄k作為軸值然后，將剩余的序列劃分為兩個(gè)子序列L和R，使得L中所有記錄都小于或等于軸值，R中記錄都大于軸值將L中所有記錄都放在k左邊R中的記錄都放在k的右邊k正好處于正確的位置對(duì)子序列L和R遞歸進(jìn)行快速排序，直到僅含1或0個(gè)元素在n個(gè)元素的序列中,對(duì)一個(gè)對(duì)象定位所需時(shí)間為O(n)。08162125*2549該思想是解決問題的重要方法之一ModifiedInsertSort(RecordArray[],intn,intdelta)while(index1<=middle&&index2<=right){//若長(zhǎng)度小于等于閾值，采用直接插入排序首先，從待排序序列S中任意選擇一個(gè)記錄k作為軸值inti,j,index1,index2;VoidShellSorter<Record,Compare>::Sort(RecordArray[],intn)if(i<j){ Array[i]=Array[j];i++;} //i指針向右移動(dòng)一步(2534)(4532)(7812)(34’64)while(Compare::gt(Array[j],TempRecord)&&(j>i))j--;其中n—文件長(zhǎng)度；12關(guān)鍵問題軸值選擇盡可能使L，R長(zhǎng)度相等選擇策略選擇最左邊記錄隨機(jī)選擇選擇中間位置值序列分割整個(gè)快速排序的關(guān)鍵分割后使得L中所有記錄位于軸值左邊，R中記錄位于軸值右邊，即軸值已位于正確位置13分割過程描述開始前，將軸值與最后一個(gè)記錄交換，并將軸值保存在一個(gè)臨時(shí)變量中（最后位置為空閑位置）用指針left,right掃描整個(gè)序列，初值位于序列的兩端首先，left指針從左邊開始掃描，找到大于軸值的元素停下，將該元素放在空閑位置上，left位置成為空閑位置然后，從right前面位置尋找小于軸值的元素，找到后停下，將該元素放在left位置的空閑位置上，right位置成為空閑位置重復(fù)上述過程，直至left與right相遇，整個(gè)過程結(jié)束分割過程完畢left快速排序的過程2108254925*16初始關(guān)鍵字08254925*162108254925*1608254925*1608254925*1608254925*1621pivot一次交換二次交換三次交換四次交換完成一趟排序leftrightrightrightleftleftrightrightleftrightleft08254925*1621完成一趟排序分別進(jìn)行快速排序08254925*1621有序序列08254925*16212125*25490816算法quicksort是一個(gè)遞歸的算法,其遞歸樹如圖所示16快速排序算法template<classRecord,classCompare>classQuickSorter:publicSorter<Record,Compare>{ //快速排序類 private: intSelectPivot(intleft,intright);//選擇軸值，返回軸值下標(biāo)

intPartition(RecordArray[],intleft,intright);//分割,返回軸值位置 public: voidSort(RecordArray[],intleft,intright);};template<classRecord,classCompare>intQuickSorter<Record,Compare>::SelectPivot(intleft,intright){ //參數(shù)left,right分別表示序列的左右端下標(biāo)

return(left+right)/2; //選擇中間紀(jì)錄作為軸值}17快速排序函數(shù)template<classRecord,classCompare>voidQuickSorter<Record,Compare>::Sort(RecordArray[],intleft,intright){ //Array[]為待排序數(shù)組，i,j分別為數(shù)組兩端

if(right<=left) //如果子序列中只有0或1個(gè)記錄，就不需排序 return;

intpivot=SelectPivot(left,right); //選擇軸值

swap(Array,pivot,right); //將軸值放在數(shù)組末端

pivot=Partition(Array,left,right); //對(duì)剩余的記錄進(jìn)行分割

Sort(Array,left,pivot-1); //對(duì)軸值左邊的子序列進(jìn)行遞歸快速排序

Sort(Array,pivot+1,right); //對(duì)軸值右邊的子序列進(jìn)行遞歸快速排序}18分割函數(shù)template<classRecord,classCompare>intQuickSorter<Record,Compare>::Partition(RecordArray[],intleft,intright)

{ //分割函數(shù)，分割后軸值已到達(dá)正確位置

RecordTempRecord; //存放軸值的臨時(shí)變量

inti=left; //i為左指針，j為右指針

intj=right; //將軸值存放在臨時(shí)變量中

TempRecord=Array[j];19 //開始分割，i,j不斷向中間移動(dòng)，直到相遇 while(i!=j){ //i指針右移，直到找到一個(gè)大于等于軸值的記錄

while(Compare::le(Array[i],TempRecord)&&(j>i))i++;

//如果i,j未相遇就將逆序元素?fù)Q到右邊空閑位置 if(i<j){ Array[j]=Array[i];j--; } //j指針向左移動(dòng)一步 //j指針左移，直到找到一個(gè)小于等于軸值的記錄

while(Compare::gt(Array[j],TempRecord)&&(j>i))j--; //如果i,j未相遇就將逆序元素?fù)Q到左邊空閑位置 if(i<j){ Array[i]=Array[j];i++;} //i指針向右移動(dòng)一步 }

Array[i]=TempRecord;//把軸值回填到分界位置i上 returni; //返回分界位置i}20算法復(fù)雜性分析快速排序的趟數(shù)取決于遞歸樹的高度如果每次劃分對(duì)一個(gè)對(duì)象定位后,該對(duì)象左右兩側(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í)間為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)21算法復(fù)雜性分析可以證明,函數(shù)quicksort的平均計(jì)算時(shí)間也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明:就平均計(jì)算時(shí)間而言,快速排序是所有內(nèi)排序方法中最好的一個(gè)快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為log2(n+1)

。因此，要求存儲(chǔ)開銷為O(log2n)。在最壞的情況,其遞歸樹成為單支樹（與軸值的選擇策略有關(guān)）,每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列?？偟呐判虼a比較次數(shù)將達(dá)快速排序是一種不穩(wěn)定的排序方法（why?）22優(yōu)化的快速排序優(yōu)化思想當(dāng)快速排序的子數(shù)組小于某個(gè)長(zhǎng)度時(shí)，其計(jì)算效率不如直接插入排序高經(jīng)驗(yàn)表明最好的組合方式是當(dāng)n（子數(shù)組的長(zhǎng)度）小于等于9或16或28時(shí)就使用插入排序（視測(cè)試環(huán)境有關(guān)）23優(yōu)化快速排序算法#defineTHRESHOLD9或16或28template<classRecord>voidModQuickSort(RecordArray[],intleft,intright){ //優(yōu)化的快速排序，

if(right-left+1>THRESHOLD){ //對(duì)長(zhǎng)度大于閾值(28最佳)的長(zhǎng)子串處理

intpivot=SelectPivot(left,right); //選擇軸值

swap(Array,pivot,right); //將軸值放在數(shù)組末端

pivot=Partition(Array,left,right); //分割后軸值已到達(dá)正確位置

ModQuickSort(Array,left,pivot-1); //對(duì)軸值左邊的子序列進(jìn)行遞歸快速排序

ModQuickSort(Array,pivot+1,right); //對(duì)軸值右邊的子序列進(jìn)行遞歸快速排序

}}template<classRecord>voidQuicksort(Record*Array,intn){ ModQuickSort(Array,0,n-1); //調(diào)用優(yōu)化的遞歸快排，不處理小子串

InsertSort(Array,n); //最后這個(gè)序列進(jìn)行掃尾插入排序}242、歸并排序基本思想簡(jiǎn)單地將原始序列劃分為兩個(gè)子序列分別對(duì)每個(gè)子序列遞歸排序最后將排好序的子序列合并為一個(gè)有序序列，即歸并過程快速排序側(cè)重于分割過程，而歸并排序側(cè)重于歸并過程(25344532781234’64)(25344532)(781234’64)(2534)(4532)(7812)(34’64)(25)(34)(45)(32)(78)(12)(34’)(64)(2534)(3245)(1278)(34’

64)(25323445)(12

34’6478)(1225323434’456478)先劃分再歸并歸并思想26兩路歸并排序算法template<classRecord>voidMergeSort(RecordArray[],RecordTempArray[],intleft,intright){ //Array為待排序數(shù)組，left，right兩端

intmiddle; if(left<right){ //如果序列中只有0或1個(gè)記錄，就不用排序

middle=(left+right)/2; //從中間劃分為兩個(gè)子序列

MergeSort(Array,TempArray,left,middle); //對(duì)左邊一半進(jìn)行遞歸

MergeSort(Array,TempArray,middle+1,right);//對(duì)右邊一半進(jìn)行遞歸

Merge(Array,TempArray,left,right,middle); //進(jìn)行歸并

}}27template<classRecord>voidMerge(RecordArray[],RecordTempArray[],intleft,intright,intmiddle){

inti,j,index1,index2; for(j=left;j<=right;j++) //將數(shù)組暫存入臨時(shí)數(shù)組

TempArray[j]=Array[j]; index1=left; //左邊子序列的起始位置

index2=middle+1; //右邊子序列的起始位置

i=left; //從左開始?xì)w并

while(index1<=middle&&index2<=right){ //取較小者插入合并數(shù)組中

if(TempArray[index1]<=TempArray[index2])//為保穩(wěn)定，相等時(shí)左邊優(yōu)先

Array[i++]=TempArray[index1++]; elseArray[i++]=TempArray[index2++]; } while(index1<=middle) //只剩左序列，可以直接復(fù)制

Array[i++]=TempArray[index1++]; while(index2<=right) //與上個(gè)循環(huán)互斥，直接復(fù)制剩余的右序列

Array[i++]=TempArray[index2++]; }歸并排序性能分析容易看出，對(duì)n個(gè)記錄進(jìn)行歸并排序的時(shí)間復(fù)雜度為Ο(nlogn)。即：每一趟歸并的時(shí)間復(fù)雜度為O(n)，總共需進(jìn)行l(wèi)ogn

趟。歸并排序需要附加一倍的存儲(chǔ)量O(n)，歸并排序是輔助存儲(chǔ)量最多的一種排序方法。是穩(wěn)定排序算法30優(yōu)化的歸并排序優(yōu)化思想把數(shù)組暫時(shí)復(fù)制到臨時(shí)數(shù)組時(shí)，將第二個(gè)子數(shù)組中元素的順序顛倒了一下。這樣，兩個(gè)子數(shù)組從兩端開始處理，向中間推進(jìn)，使得這兩個(gè)子數(shù)組的兩端互相成為另一個(gè)數(shù)組的“監(jiān)視哨”，從而不用像Merge算法那樣需要檢查子序列結(jié)束的情況另外，當(dāng)子數(shù)組小于某個(gè)長(zhǎng)度（例如28）時(shí)，也不繼續(xù)遞歸，而是在最后對(duì)整個(gè)序列使用插入排序31優(yōu)化的歸并排序算法#defineTHRESHOLD28template<classRecord>voidModMergeSort(RecordArray[],RecordTempArray[],intleft,intright){ //Array為待排序數(shù)組，left，right兩端

intmiddle; //如果序列長(zhǎng)度大于閾值(28最佳)，跳出遞歸 if(right-left+1>THRESHOLD){

middle=(left+right)/2; //從中間劃分為兩個(gè)子序列

ModMergeSort(Array,TempArray,left,middle);//對(duì)左邊一半進(jìn)行遞歸

ModMergeSort(Array,TempArray,middle+1,right);//對(duì)右邊一半進(jìn)行遞歸

ModMerge(Array,TempArray,left,right,middle);//進(jìn)行歸并

} //若長(zhǎng)度小于等于閾值，采用直接插入排序elseInsertSort(&Array[left],right-left+1);}32template<classRecord>voidModMerge(RecordArray[],RecordTempArray[],intleft,intright,intmiddle){

intindex1,index2; //兩個(gè)子序列的起始位置

inti,j,k; for(i=left;i<=middle;i++) //復(fù)制左邊的子序列

TempArray[i]=Array[i]; for(j=1;j<=right-middle;j++) //復(fù)制右邊的子序列，但順序顛倒過來

TempArray[right-j+1]=Array[j+middle]; //開始?xì)w并，取較小者插入合并數(shù)組中

for(index1=left,index2=right,k=left;k<=right;k++) if(TempArray[index1]<=TempArray[index2])//為穩(wěn)定，相等時(shí)左邊優(yōu)先

Array[k]=TempArray[index1++]; elseArray[k]=TempArray[index2--];}//算法復(fù)雜性本質(zhì)沒有發(fā)生改變，但性能得到了一些優(yōu)化歸并函數(shù)338.5堆排序直接選擇排序：直接從剩余記錄中線性查找最大(小)記錄堆排序基于最大（?。┒褋韺?shí)現(xiàn)，效率更高堆的分類堆的完全二叉樹表示堆可以用一棵完全二叉樹表示，則K2i+1

是Ki

的左孩子;K2i+2

是Ki

的右孩子?；?最小堆)(最大堆)Ki≤K2i+1Ki≤K2i+2Ki≥K2i+1Ki≥K2i+2(i=0,1,…,n/2-1)基本思想對(duì)所有記錄建立最大堆取出堆頂?shù)淖畲笥涗浺频綌?shù)組末端，放在下標(biāo)n-1的位置；重新將剩下的n-1個(gè)記錄建堆，再取新堆頂最大的記錄，放到數(shù)組第n-2位；…；不斷重復(fù)這一操作，直到堆為空。這時(shí)數(shù)組正好是按從小到大排序//若長(zhǎng)度小于等于閾值，采用直接插入排序RecordTempRecord; //存放軸值的臨時(shí)變量08162125*2549T(n)=cn+2T(n/2)//c是一個(gè)常數(shù)“delta=2”的Shell排序//若長(zhǎng)度小于等于閾值，采用直接插入排序intPartition(RecordArray[],intleft,intright);//分割,返回軸值位置if(left<right){ //如果序列中只有0或1個(gè)記錄，就不用排序return(left+right)/2; //選擇中間紀(jì)錄作為軸值if(Array[j]<Array[j-delta])交換0號(hào)與1號(hào)記錄for(intj=0;j<delta;j++)while(index1<=middle) //只剩左序列，可以直接復(fù)制基于最大（?。┒褋韺?shí)現(xiàn)，效率更高(霍爾)1962.#defineTHRESHOLD9或16或28最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為log2(n+1)。35例：對(duì)剛才建好的最大堆進(jìn)行排序：08252125*1649交換0號(hào)與5號(hào)記錄

r[0]r[n-1]492525*2116080123454