第第頁數(shù)據(jù)結(jié)構(gòu)chapter10(2)堆排序算法1、數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)DATASTRUCTURE,DS授課教師：郭艷授課教師：郭艷授課班級授課班級:191091-4授課班級授課班級:1910914中國地質(zhì)大學(xué)計算機(jī)學(xué)院中國地質(zhì)大學(xué)計算機(jī)學(xué)院2021年春年春上堂課要點回顧上堂課要點回顧?排序排序排序的定義和類型排序的定義和類型?排序的定義和類型排序的定義和類型?排序算法的衡量標(biāo)準(zhǔn)排序算法的衡量標(biāo)準(zhǔn)?排序算法排序算法?直接插入排序直接插入排序?直接選擇排序直接選擇排序?冒泡排冒泡排序序序序?希爾排序希爾排序?堆排序堆排序堆排序堆排序第第十九十九次次課課第第十九十九次次課課閱讀：閱讀：朱戰(zhàn)立，第266-275頁習(xí)題：習(xí)題：作業(yè)17數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容???直接選擇排序直接插入排序?

2、???????堆排序希爾排序冒泡排序直接選擇排序??????基數(shù)排序歸并排序快速排序堆排序算法堆排序算法?先建初始最大堆先建初始最大堆???對對n個結(jié)點產(chǎn)生堆的過程是從個結(jié)點產(chǎn)生堆的過程是從i=開始到開始到0，反復(fù)調(diào)用篩選算法，每次將，反復(fù)調(diào)用篩選算法，每次將x[i]~x[n-1]建成最大堆建成最大堆最終將最終將[0][1]建成初始最大堆建成初始最大堆??12/?n，，最終將最終將x[0]~x[n-1]建成初始最大堆建成初始最大堆?進(jìn)行進(jìn)行n-1趟堆排序趟堆排序?設(shè)設(shè)i表示趟數(shù)，從表示趟數(shù)，從n-1到到0，每趟，每趟?交換交換堆頂記錄堆頂記錄x[0]與當(dāng)前未排序子序列的最終一個與當(dāng)前未排序子序列的最終一個記錄記錄x[i]，，x[0]定位在正確位置定位

3、在正確位置記錄記錄x[i]，，x[0]定位在正確位置定位在正確位置?重新調(diào)整重新調(diào)整，把，把x[0]“拉下來”，使記錄“拉下來”，使記錄x[0]~x[i-1]成成為最大堆為最大堆為最大堆為最大堆【堆排序算法】【堆排序算法】voidHeapSort(DataTypex[],intn)voidHeapSort(DataTypex[],intn)/*用堆排序法對記錄用堆排序法對記錄x[0]~x[n--1]排序排序*/{inti;{;/*將將x[0]~x[n--1]建成初始的最大堆建成初始的最大堆*/for(i=n/2-1;i=0;i)(;;)HeapAdjust(x,n,i);for(i=n--1;i0;i){/*交換堆頂記錄與當(dāng)前未排序子

4、序列的最終一個記錄交換堆頂記錄與當(dāng)前未排序子序列的最終一個記錄x[i]的位置的位置*/swap(x,0,i);/*重新調(diào)整，把重新調(diào)整，把x[0]“拉下來”，使記錄“拉下來”，使記錄成為最大堆成為最大堆x[0]~x[i--1]成為最大堆成為最大堆*/HeapAdjust(x,i,0);}}}堆排序算法分析?不穩(wěn)定排序算法不穩(wěn)定排序算法?總時間代價為總時間代價為O(nlog2n)?一一次建堆次建堆，，n次刪除堆頂并重新調(diào)整次刪除堆頂并重新調(diào)整次建堆次建堆，，n次刪除堆頂并重新調(diào)整次刪除堆頂并重新調(diào)整?建堆：建堆：O(n)?刪除堆頂并重新調(diào)整為堆刪除堆頂并重新調(diào)整為堆:O(log2n)?刪除堆頂并重新調(diào)整為堆刪除堆頂并重新調(diào)整為堆:O(log2n)?空間

5、代價為空間代價為O(1)10.4.2快速排序?算法思想：算法思想：?選擇選擇軸值軸值〔〔pivot〕〕?將序列將序列劃分劃分為兩個子序列為兩個子序列L和和R，，使得使得L中的中的?將序列將序列劃分劃分為兩個子序列為兩個子序列L和和R，，使得使得L中的中的全部記錄都小于或等于軸值，全部記錄都小于或等于軸值，R中的全部記中的全部記錄都大于軸值錄都大于軸值，，即軸值已經(jīng)定位在正確位置即軸值已經(jīng)定位在正確位置錄都大于軸值錄都大于軸值，，即軸值已經(jīng)定位在正確位置即軸值已經(jīng)定位在正確位置對子序列對子序列L和和R遞歸遞歸進(jìn)行快速排序進(jìn)行快速排序LR?對子序列對子序列L和和R遞歸遞歸進(jìn)行快速排序進(jìn)行快速排序軸值選擇〔SelectPivot〕?盡可能盡可能使使L和和R

6、的長度相等的長度相等?選擇策略：選擇策略：選擇最左邊的記錄選擇最左邊的記錄?選擇最左邊的記錄選擇最左邊的記錄?選擇中間記錄，須將中間記錄和最左邊記錄選擇中間記錄，須將中間記錄和最左邊記錄互換互換互換互換?選擇平均值，須將平均值的記錄和最左邊記選擇平均值，須將平均值的記錄和最左邊記錄互換〔可使錄互換〔可使L和和R的長度相等〕的長度相等〕?隨機(jī)選擇隨機(jī)選擇，，須將選擇的須將選擇的記記錄和最錄和最左邊記左邊記錄錄互互隨機(jī)選擇隨機(jī)選擇須將選擇的錄和最錄須將選擇的錄和最錄換換劃分過程〔Partition〕?劃分是整個快速排序的關(guān)鍵劃分是整個快速排序的關(guān)鍵?劃分后使得劃分后使得L中全部記錄位于軸值左邊，中全部記錄位于軸值左邊，R中記錄位于軸值右邊中記錄位于軸值右

7、邊即軸值已經(jīng)定位即軸值已經(jīng)定位R中記錄位于軸值右邊中記錄位于軸值右邊，，即軸值已經(jīng)定位即軸值已經(jīng)定位于正確位置于正確位置LR例例：：初始關(guān)鍵字初始關(guān)鍵字：：[465513429451770]temp.key例例：：初始關(guān)鍵字初始關(guān)鍵字：：[465513429451770]進(jìn)行進(jìn)行一一次交換后次交換后[17]55134294517[70]ijj進(jìn)行次交換后進(jìn)行次交換后：：[17]55134294517[70]進(jìn)行二次交換后進(jìn)行二次交換后[17]551342945[5570]ji進(jìn)行二次交換后進(jìn)行二次交換后：：[17]551342945[5570]ij進(jìn)行三次交換后：進(jìn)行三次交換后：[175]1342945[5570]jiii進(jìn)行四次交換后：進(jìn)行四次交換

8、后：[1751342]94[945570]jij完成一趟排序：完成一趟排序：[1751342]46[945570]二趟排序之后二趟排序之后[135]17[42]46[7055]94ij二趟排序之后二趟排序之后：：[135]17[42]46[7055]94三趟排序之后：三趟排序之后：[5]13174246[55]7094【快速排序的軸值選擇函數(shù)】intSelectPivot(intlow,inthigh){/*參數(shù)參數(shù)lhih分別表示待排序序列的左右端分別表示待排序序列的左右端{(lán)/*參數(shù)參數(shù)low,high分別表示待排序序列的左右端分別表示待排序序列的左右端下標(biāo)下標(biāo)*///選擇選擇最左記錄最左記錄作為軸值作為軸值//選擇選擇最左記錄最左記錄作為軸值作為

9、軸值returnlow;}}【快速排序的分割函數(shù)】intPartition(DataTypex[],intlow,inthigh){//分割后軸值已到達(dá)正確位置分割后軸值已到達(dá)正確位置{//分割后軸值已到達(dá)正確位置分割后軸值已到達(dá)正確位置DataTypetemp;//存放軸值的臨時變量存放軸值的臨時變量itil//i為左指針為左指針j為右指針為右指針inti=low;//i為左指針為左指針，，j為右指針為右指針intj=high;//將軸值存放在臨時變量中將軸值存放在臨時變量中//將軸值存放在臨時變量中將軸值存放在臨時變量中temp=x[i];//開始分割開始分割ij不斷向中間移動不斷向中間移動直到相遇直到相遇//開始分割開始分割，，i,j不斷向中間

10、移動不斷向中間移動，，直到相遇直到相遇while(itk){inti,j,k,power=1;LQueue*tub;tub=(LQueue*)malloc(sizeof(LQueue)*d);f(i0idi++)for(i=0;id;i++)QueueInitiate(for(i=0;im;i++){if(i==0)power=1;elsepower=power*d;for(j=0;jn;j++)jjj{k=a[j].key/power-(a[j].key/(power*d))*d;QueueAppend(}}k=0;for(j=0;jd;j++)while(QueueNotEmpty(tub[j])!=0)while(QueueNotEmpty(t

11、ub[j])!=0){QueueDelete(k++;}}}}基數(shù)排序算法分析?穩(wěn)定穩(wěn)定的排序算法的排序算法?空間代價：空間代價：ＯＯ(d)?d個子個子序列的頭尾指針序列的頭尾指針?d個子個子序列的頭尾指針序列的頭尾指針?時間代價：時間代價：ＯＯ(m(n+d))?對于對于n個記錄個記錄執(zhí)行執(zhí)行一一次安排和收集的時間為次安排和收集的時間為?對于對于n個記錄個記錄，，執(zhí)行次安排和收集的時間為執(zhí)行次安排和收集的時間為O(n+d)?不需要移動記錄本身，只需要修改記錄的不需要移動記錄本身，只需要修改記錄的next指指針針針針?當(dāng)當(dāng)d或或m較小時，這種方法較為節(jié)約時間較小時，這種方法較為節(jié)約時間10.7排序方法的性能比較10.7排序方法的性能比較算法最大時算法最

12、大時間間平均時平均時間間最小時間幫助空最小時間幫助空間代價間代價穩(wěn)定穩(wěn)定性性間間間間間代價間代價性性直接插入排直接插入排序序O(n2)O(n2)O(n)O(1)穩(wěn)定穩(wěn)定序序折半插入排折半插入排序序O(n2)O(n2)O(nlog2n)O(1)穩(wěn)定穩(wěn)定序序冒泡排序冒泡排序O(n2)O(n2)O(n)O(1)穩(wěn)定穩(wěn)定直接選擇排序直接選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定不穩(wěn)定算法最大時間平均時間最小時間幫助空算法最大時間平均時間最小時間幫助空間代價間代價穩(wěn)定穩(wěn)定性性間代價間代價性性Shell排序排序O(n3/2)O(n3/2)O(n3/2)O(1)不穩(wěn)不穩(wěn)定定定定快速排序快速排序O(n2)O(nlog2n)O(nlog2n)O(log2n)

13、不穩(wěn)不穩(wěn)定定歸并排序歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)穩(wěn)定穩(wěn)定歸并排序歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)穩(wěn)定穩(wěn)定堆排堆排序序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不穩(wěn)不穩(wěn)序序(g2)(g2)(g2)()不穩(wěn)不穩(wěn)定定基數(shù)排序基數(shù)排序O(m(n+d))O(m(n+d))O(m(n+d))O(d)穩(wěn)定穩(wěn)定基數(shù)排序基數(shù)排序O(m(n+d))O(m(n+d))O(m(n+d))O(d)穩(wěn)定穩(wěn)定小結(jié)?n很小或基本有序時n很小或基本有序時直接插入排序直接插入排序比較有比較有效效?盼望以最快速度選擇出若干最大或最小盼望以最快速度選擇出若干最大或最小?盼望以最快速度選擇出若

14、干最大或最小盼望以最快速度選擇出若干最大或最小元素，元素，堆排序堆排序或直接選擇最合適或直接選擇最合適?綜合性能綜合性能快速排序最正確快速排序最正確作業(yè)作業(yè)17