數(shù)據(jù)結(jié)構(gòu)與算法-交換排序、歸并排序

8內(nèi)排序(8.4-8.5)內(nèi)排序(8.4-8.5)主要內(nèi)容8.1排序問題的基本概念8.2插入排序（Shell排序）8.3選擇排序（堆排序）8.4交換排序8.4.1冒泡排序8.4.2快速排序8.5歸并排序8.6分配排序和索引排序8.7排序算法的時間代價2/54內(nèi)排序(8.4-8.5)冒泡排序..。oO3/548.4.1冒泡排序算法思想不停地比較相鄰的記錄，如果不滿足排序要求，就交換相鄰記錄，直到所有的記錄都已經(jīng)排好序注意：避免不必要的比較檢查每次冒泡過程中是否發(fā)生過交換，如果沒有，則表明整個數(shù)組已經(jīng)排好序了，排序結(jié)束內(nèi)排序(8.4-8.5)4/54冒泡排序動畫1234’322964783445內(nèi)排序(8.4-8.5)5/54冒泡排序算法template<classRecord>voidBubbleSort(RecordArray[],intn){

bool

NoSwap; //是否發(fā)生了交換的標志

inti,j; for(i=0;i<n-1;i++){

NoSwap=true; //標志初始為真 for(j=n-1;j>i;j--) if(Array[j]<Array[j-1]){//判斷是否逆置

swap(Array,j,j-1); //交換逆置對 NoSwap=false; //發(fā)生了交換，標志變?yōu)榧?/p>

}

if(NoSwap) //沒發(fā)生交換，則排好序，結(jié)束算法

return; }}

內(nèi)排序(8.4-8.5)6/54算法分析穩(wěn)定空間代價：Θ(1)時間代價分析：比較次數(shù)：最少：Θ(1)最多：交換次數(shù)最多為Θ(n2)，最少為0，平均為Θ(n2)。時間代價結(jié)論最大，平均時間代價均為Θ(n2)。最小時間代價為Θ(n)：最佳情況下只運行第一輪循環(huán)內(nèi)排序(8.4-8.5)7/548.4.2快速排序算法思想：選擇軸值（pivot）將序列劃分為兩個子序列L和R，使得L中所有記錄都小于或等于軸值，R中記錄都大于軸值對子序列L和R遞歸進行快速排序20世紀十大算法TopTenAlgorithmsoftheCentury7.1962London的ElliotBrothersLtd的TonyHoare提出的快速排序

基于分治法的排序：快速、歸并內(nèi)排序(8.4-8.5)8/54分治策略的基本思想分治策略的實例快速排序、歸并排序BST查找、插入、刪除算法二分檢索主要思想分——劃分子問題治——求解子問題(子問題不重疊)合——綜合解內(nèi)排序(8.4-8.5)9/54內(nèi)排序(8.4-8.5)快排序（QuickSort)

快速排序?qū)嵗炫判颉惴ㄋ枷?0/54快速排序分治思想2534453234’1229642529122934’34453264253412251234’64453434’最終排序結(jié)果：1225293234’34456445內(nèi)排序(8.4-8.5)11/54軸值選擇盡可能使L，R長度相等選擇策略：選擇最左邊記錄(第一個記錄)隨機選擇選擇平均值內(nèi)排序(8.4-8.5)12/54分割過程（Partition）整個快速排序的關(guān)鍵軸值位于正確位置，分割后使得L中所有記錄位于軸值左邊R中記錄位于軸值右邊內(nèi)排序(8.4-8.5)13/54一次分割過程1225322964453434’選擇軸值并存儲軸值最后一個元素放到軸值位置初始化下標i,j，分別指向頭尾i遞增直到遇到比軸值大的元素，將此元素覆蓋到j的位置；j遞減直到遇到比軸值小的元素，將此元素覆蓋到i的位置重復上一步直到i==j，將軸值放到i的位置，完畢64ij3234294512內(nèi)排序(8.4-8.5)14/54快速排序算法template<classRecord>voidQuickSort(RecordArray[],intleft,intright){ //Array[]為待排序數(shù)組，left,right分別為數(shù)組兩端

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

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

swap(Array,pivot,right); //先將軸值放到末端內(nèi)排序(8.4-8.5)15/54快速排序算法

//分割，使得軸值達正確位置 pivot=Partition(Array,left,right);

//對左子序列進行遞歸快速排序

QuickSort(Array,left,pivot-1);

//對右子序列進行遞歸快速排序

QuickSort(Array,pivot+1,right); }內(nèi)排序(8.4-8.5)16/54內(nèi)排序(8.4-8.5)第一趟排序后133827

49

76976552第二趟排序1338277697655249將序列分成兩部分，分別進行新的快速排序；第二趟排序后13382765

527697第三趟排序38276552第三趟排序后27385265最終有序序列為:13273852657697快速排序過程17/54內(nèi)排序(8.4-8.5)分割算法備份軸記錄取兩個指針low和high，初始值就是序列的兩端下標，保證low<=high移動兩個指針從high向左找到第一個小于軸的元素,放在low的位置從low向右找到第一個大于軸的元素，放在high的位置重復，直到low=high，把軸放在low所指的位置18/54軸值選擇函數(shù)int

SelectPivot(intleft,intright){ //選擇軸值，參數(shù)left,right分別表示序列的左右端下標

return(left+right)/2; //選擇中間記錄作為軸值}內(nèi)排序(8.4-8.5)19/54分割函數(shù)template<classRecord>intPartition(RecordArray[],intleft,intright){ //分割函數(shù)，分割后軸值已到達正確位置

intl=left; //l為左指針

intr=right; //r為右指針 RecordTempRecord=Array[r]; //保存軸值

內(nèi)排序(8.4-8.5)20/54

while(l!=r){//開始分割，l,r不斷向中間移動，直到相遇

//l指針向右移動，越過那些小于等于軸值的記錄//直到找到一個大于軸值的記錄

while(Array[l]<=TempRecord&&r>l) //“<=”也可以改寫為“<”，但增加記錄移動

l++; if(l<r){//若l,r尚未相遇，將逆置元素換到右邊空位

Array[r]=Array[l]; r--; //r指針向左移動一步

}

內(nèi)排序(8.4-8.5)21/54

//r指針向左移動，越過那些大于等于軸值的記錄 //直到找到一個小于軸值的記錄

while(Array[r]>=TempRecord&&r>l) //“>=”也可以改寫為“>”，但增加記錄移動

r--; if(l<r){//若l,r尚未相遇，將逆置元素換到左邊空位

Array[l]=Array[r]; l++; //

l指針向右移動一步

} } //endwhile Array[l]=TempRecord;

//把軸值回填到分界位置l上

returnl; //返回分界位置l}內(nèi)排序(8.4-8.5)22/54內(nèi)排序(8.4-8.5)分割算法過程3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high4923/54時間代價長度為n的序列，時間為T(n)T(0)=T(1)=1選擇軸值時間為常數(shù)分割時間為cn分割后長度分別為

i和

n-i-1對子序列進行快速排序所需時間分別為T(i)和T(n-1-i)求解遞推方程內(nèi)排序(8.4-8.5)24/54最差情況總的時間代價為：內(nèi)排序(8.4-8.5)25/54最佳情況內(nèi)排序(8.4-8.5)26/54logn次分割

內(nèi)排序(8.4-8.5)27/54平均情況，等概率分割

T(i)和T(n-1-i)的平均值均為代入方程內(nèi)排序(8.4-8.5)28/54上式乘以n帶入n-1上述二式相減，上式兩邊同時除以n(n+1)，并忽略常數(shù)系數(shù)內(nèi)排序(8.4-8.5)29/54因此內(nèi)排序(8.4-8.5)30/54算法分析最差情況：時間代價：Θ(n2)空間代價：Θ(n)最佳情況：時間代價：Θ(nlogn)空間代價：Θ(logn)

平均情況：時間代價：Θ(nlogn)

空間代價：Θ(logn)

內(nèi)排序(8.4-8.5)31/54算法分析（續(xù)）不穩(wěn)定可能優(yōu)化：軸值選擇RQS（randomizedquicksort）小子串不遞歸消除遞歸內(nèi)排序(8.4-8.5)32/54優(yōu)化的快速排序#defineTHRESHOLD28template<classRecord>voidModQuickSort(RecordArray[],intleft,intright){

if(right-left+1>THRESHOLD){//長子串處理

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

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

pivot=Partition(Array,left,right);//分割

ModQuickSort(Array,left,pivot-1);//處理左

ModQuickSort(Array,pivot+1,right);//處理右

}}內(nèi)排序(8.4-8.5)33/54template<classRecord>voidQuicksort(Record*Array,intn){//調(diào)用優(yōu)化的遞歸快排，不處理小子串 ModQuickSort(Array,0,n-1); //最后這個序列進行掃尾插入排序

InsertSort(Array,n);

}內(nèi)排序(8.4-8.5)34/54內(nèi)排序(8.4-8.5)主要內(nèi)容8.1排序問題的基本概念8.2插入排序（Shell排序）8.3選擇排序（堆排序）8.4交換排序8.4.1冒泡排序8.4.2快速排序8.5歸并排序8.6分配排序和索引排序8.7排序算法的時間代價35/548.5歸并排序算法思想簡單地將原始序列劃分為兩個子序列分別對每個子序列遞歸排序最后將排好序的子序列合并為一個有序序列，即歸并過程內(nèi)排序(8.4-8.5)36/54(25344532781234’64)(25344532)(781234’64)(2534)(4532)(7812)(34’64)(25)(34)(45)(32)(78)(12)(34’)(64)(2534)(3245)(1278)(34’64)(25323445)(1234’6478)(1225323434’456478)先劃分再歸并歸并思想內(nèi)排序(8.4-8.5)37/54兩路歸并排序template<classRecord>voidMergeSort(RecordArray[],RecordTempArray[],intleft,intright){//Array為數(shù)組，left，right兩端

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

middle=(left+right)/2;//從中間劃為兩個子序列 //對左邊一半進行遞歸

MergeSort(Array,TempArray,left,middle); //對右邊一半進行遞歸

MergeSort(Array,TempArray,middle+1,right);

Merge(Array,TempArray,left,right,middle); //歸并

}}內(nèi)排序(8.4-8.5)38/54歸并函數(shù)//兩個有序子序列都從左向右掃描，歸并到新數(shù)組template<classRecord>voidMerge(RecordArray[],RecordTempArray[],intleft,intright,intmiddle){

int

i,j,index1,index2; //將數(shù)據(jù)暫存入臨時數(shù)組 for(j=left;j<=right;j++) TempArray[j]=Array[j]; index1=left; //左邊子序列的起始位置

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

i=left; //從左開始歸并內(nèi)排序(8.4-8.5)39/54while(index1<=middle&&index2<=right){ //取較小者插入合并數(shù)組中

if(TempArray[index1]<=

TempArray[index2])//左優(yōu)先

Array[i++]=TempArray[index1++]; elseArray[i++]=TempArray[index2++]; }

內(nèi)排序(8.4-8.5)40/54

while(index1<=middle) //只剩左序列，可以直接復制 Array[i++]=TempArray[index1++]; while(index2<=right) //或者直接復制剩余的右序列 Array[i++]=TempArray[index2++]; }內(nèi)排序(8.4-8.5)41/54(25344532781234’64)(25344532)(781234’64)(2534)(4532)(7812)(34’64)(25)(34)(45)(32)(78)(12)(34’)(64)(2534)(4532)(1278)(6434’)(25323445)(786434’12)(1225323434’456478)先劃分再歸并R.Sedgewick優(yōu)化歸并思想內(nèi)排序(8.4-8.5)42/54256478323434’4512R.Sedgewick優(yōu)化歸并i1i2k647834’12i1i2k內(nèi)排序(8.4-8.5)43/54優(yōu)化的歸并排序#defineTHRESHOLD28template<classRecord>voidModMergeSort(RecordArray[],RecordTempArray[],intleft,intright){//Array為待排序數(shù)組，left，right兩端

intmiddle; //如果序列長度大于閾值(28最佳)，遞歸進行歸并 if(right-left+1>THRESHOLD){

middle=(left+right)/2;//從中間劃分

//對左邊一半進行遞歸

ModMergeSort(Array,TempArray,left,middle);

內(nèi)排序(8.4-8.5)44/54優(yōu)化的歸并排序（cont.）

//對右邊一半進行遞歸

ModMergeSort(Array,TempArray,

middle+1,

right);

//對相鄰的有序序列進行歸并

ModMerge(Array,TempArray,left,right,middle); }

//小長度子序列進行插入排序，“&”傳Array[left]的地址elseInsertSort(&Array[left],right-left+1);}內(nèi)排序(8.4-8.5)45/54優(yōu)化的歸并函數(shù)//優(yōu)化的Sedgwick兩個有序子序列歸并//右序列逆置了，都從兩端向中間掃描，歸并到新數(shù)組template<classRecord>voidModMerge(RecordArray[],RecordTempArray[],int

left,int

right,intmiddle){ //歸并過程

intindex1,index2;//子序列的起始位置

int

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

TempArray[i]=Array[i];內(nèi)排序(8.4-8.5)46/54

//復制右邊的子序列，但順序顛倒過來 for(j=1;j<=right-middle;j++) TempArray[right-j+1]=Array[j+middle]; //開始歸并，取較小者插入合并數(shù)組中

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