7-3交換排序v第七章排序技術學什么？起泡（冒泡）排序快速排序提出關鍵問題給出解決方法寫出算法描述得到完整算法運行實例7-3-1起泡排序v第七章排序技術基本思想無序區(qū)r1r2ri-1…有序區(qū)rirnri+1…起泡排序的基本思想：兩兩比較相鄰記錄，如果反序則交換，直到沒有反序的記錄為止。反序則交換類似水中的氣泡，體積大的浮到上面，起泡排序（冒泡排序）因而得名運行實例2420101812待排序序列第一趟排序結果第二趟排序結果第三趟排序結果第四趟排序結果1210201824241012182024101218202410121820第二趟排序有必要嗎？88888第五趟排序結果24101218208第四、五趟排序有必要嗎？關鍵問題2420101812待排序序列第一趟排序結果1210182024如果有多個記錄位于最終位置，如何不參加下一趟排序？if(data[j]>data[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}設置變量exchange記載交換的位置，一趟排序后exchange記載的就是最后交換的位置，從exchange之后的記錄不參加下一趟排序。解決方法：算法描述：交換交換2420101812待排序序列第一趟排序結果2024下一趟排序的范圍是多少？bound=exchange;exchange=0;for(j=0;j<bound;j++)if(data[j]>data[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}設置變量bound表示一趟起泡排序的范圍[1,bound]，并且bound與上一趟起泡排序的最后交換的位置exchange之間的關系是bound=exchange。解決方法：算法描述：交換交換121018關鍵問題某趟排序結果下一趟排序結果2024如何判別起泡排序的結束？while(exchange!=0){

執(zhí)行一趟起泡排序；}一趟排序沒有交換，則表明整個序列已經有序。解決方法：算法描述：1210182024121018關鍵問題算法實現voidSort::BubbleSort(){ intj,exchange,bound,temp;exchange=length-1;while(exchange!=0){bound=exchange;exchange=0；

for(j=0;j<bound;j++)if(data[j]>data[j+1]){temp=data[j];data[j]=data[j+1];data[j+1]=temp;

exchange=j；//記載每一次記錄交換的位置

}}}比較語句？執(zhí)行次數？移動語句？執(zhí)行次數？取決于待排序序列的初始狀態(tài)時間性能性能分析比較次數：n-1

移動次數：0

12345最好情況：正序O(n)最壞情況：逆序O(n2)比較次數：

移動次數：平均情況：隨機排列O(n2)51432

空間性能：O(1)

穩(wěn)定性：穩(wěn)定if(data[j]>data[j+1]){

temp=r[j];r[j]=r[j+1];r[j+1]=temp

exchange=j；}7-3-2快速排序v第七章排序技術改進的著眼點5143245352551記錄的比較在相鄰單元中進行每次交換只能右移一個單元總的比較次數和移動次數較多較大記錄從前面直接移到后面，較小記錄從后面直接移到前面？基本思想快速排序的基本思想：選一個軸值，將待排序記錄劃分成兩部分，左側記錄均小于或等于軸值，右側記錄均大于或等于軸值，然后分別對這兩部分重復上述過程，直到整個序列有序。均≤ri'r1'ri-1'…ri'rn'ri+1'…r1ri-1…rirnri+1…均≥ri'運行實例10283216242030待排序序列第一趟排序結果第二趟排序結果第三趟排序結果102832162420301028321620301028322010283216242030最終排序結果關鍵問題如何選擇軸值？選取不同軸值有什么后果?決定兩個子序列的長度決定排序的時間性能解決方法：（1）第一個記錄；（2）隨機選取；（3）三數取中：取三個記錄的中值；不失一般性，取第一個記錄作為軸值10283216242030待排序序列10283216242030一次劃分結果一次劃分：以軸值為基準將無序序列劃分為兩部分如何實現一次劃分——較大的記錄移到后面，較小記錄移到前面？記錄的比較和移動從兩端向中間進行較小的記錄一次就能從后面移到前面（較大的記錄？）減少了總的比較次數和移動次數關鍵問題10283216242030待排序序列10283216242030一次劃分結果運行實例10283216242030待排序序列jij從后向前掃描直到r[j]<r[i]10283216242030ji交換r[j]和r[i]，i++10283216242030待排序序列j從后向前掃描直到r[j]<r[i]10283216242030ji交換r[j]和r[i]，i++i從前向后掃描直到r[j]<r[i]交換r[j]和r[i]，j--10283216242030ji重復上述過程，直到i等于j運行實例算法實現intSort::Partition(intfirst,intlast){ inti=first,j=last,temp;while(i<j) {}retutni;/*i為軸值記錄的最終位置*/}為什么設置形參first和last？表示什么？1028321624203010283216242030表示待劃分區(qū)間[first,last]，是變化的jiintSort::Partition(intfirst,intlast){ inti=first,j=last,temp;

while(i<j) {}

retutni;

}

while(i<j&&data[i]<=data[j])j--；if(i<j){temp=data[i];data[i]=data[j];data[j]=temp;i++;}

while(i<j&&data[i]<=data[j])i++；if(i<j){temp=data[i];data[i]=data[j];data[j]=temp;j--;}算法實現時間性能時間復雜度是多少？下標i和j共同將數組掃描一遍比較語句？執(zhí)行次數？移動語句？執(zhí)行次數？取決于待排序序列的初始狀態(tài)O(n)10283216242030待排序序列10283216242030如何處理一次劃分得到的兩個待排序子序列？解決方法：遞歸執(zhí)行快速排序一次劃分結果voidSort::QuickSort(intfirst,intlast){intpivot=Partition(first,last);QuickSort(first,pivot-1);QuickSort(pivot+1,last);}算法描述：關鍵問題10283216242030待排序序列第一趟排序結果第二趟排序結果10283216242030102832162030何時結束遞歸？解決方法：若待排序序列只有一個記錄，即待劃分區(qū)間長度為1if(first>=last)return;關鍵問題voidSort::QuickSort(intfirst,intlast){ }else{intpivot=Partition(first,last);QuickSort(first,pivot-1);QuickSort(pivot+1,last);}if(first>=last)return;算法實現性