內(nèi)部排序1概述2插入排序3快速排序-資料下載頁(yè)
2025-05-13 06:17本頁(yè)面
【正文】 { [0]=[low]。 //用表的第一個(gè)記錄作樞軸記錄 pivotkey=[low].key。 //樞軸記錄關(guān)鍵字 while(lowhigh) { while(lowhighamp。amp。[high].key=pivotkey) high。 [low]=[high]。 //比樞軸記錄小的記錄移到低端 while(lowhighamp。amp。[low].key=pivotkey) ++low。 [high]=[low]。 //比樞軸記錄大的記錄移到高端 } [low]=[0]。 return low。 } 算法： void QSort(SqList amp。L,int low,int high) //對(duì)順序表的子表排序 { if(lowhigh) //長(zhǎng)度大于 1 {pivotloc=Partition(L,low,high)。 //樞軸位置 QSort(L,low,pivotloc1)。 //對(duì)低子表遞歸排序 QSort(+1,high)。 //對(duì)高子表遞歸排序 } } void QuickSort(SqList amp。L) //對(duì)順序表排序 { QSort(L,1,)。 } 例 初始關(guān)鍵字 38 65 97 76 13 27 49 49 49 樞軸記錄關(guān)鍵字 pivotkey= low high high 27進(jìn)行第一次交換后 27 38 65 97 76 13 49 low high low 65 進(jìn)行第二次交換后 27 38 97 76 13 65 49 low high high 13 進(jìn)行第三次交換后 27 38 13 97 76 65 49 low high low 97 進(jìn)行第四次交換后 27 38 13 76 97 65 49 low high high low high 例 初始關(guān)鍵字 38 65 97 76 13 27 49 49 49 樞軸記錄關(guān)鍵字 pivotkey= 49 進(jìn)行第四次交換后 27 38 13 76 97 65 49 49 low=high 完成一趟排序 27 38 13 49 76 97 65 49 { } { } 分別進(jìn)行 快速排序 13 27 38 { } { } 49 65 76 97 { } { } 49 65 { } 有序序列 13 27 38 49 49 65 76 97 特點(diǎn)： 二 .快速排序 ① 從時(shí)間上看，快速排序的平均性能優(yōu)于前面所 討論的各種排序方法。 ② 快速排序?yàn)椴环€(wěn)定算法。 如 ： （ 3， 2， 2） 排序后 ： （ 2， 2， 3） 快速排序 練習(xí) (12， 5， 9， 20， 6， 31， 24)，對(duì)該數(shù)據(jù)序列進(jìn)行排序，寫(xiě)出直接插入排序、起泡排序、快速排序每趟的結(jié)果。 （ Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按字母序的升序重新排列，則： 冒泡排序一趟掃描的結(jié)果是 ；初始步長(zhǎng)為 4的希爾排序一趟的結(jié)果是 ；快速排序一趟掃描的結(jié)果是 。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1