11設：R1，R2，R3，…，Rn是n遞增：ki遞減：ki非遞減：ki非遞增：ki2排序分

3排序分

4排序分

簡單的排序方法先進的排序方法排序基本5KjKi＝KjRi仍領先于Rj，稱所用方法是穩定的。13,27,38,49,49,65,76,97穩定排序的 委托隊列（反映委托提交的時間先后按價格排((06,10.5),(09,10),(051,10),(033,9.8))#defineMAXSIZE20順序表的最大長度typedefintKeyType；//定義關鍵字類型typedefstruct{KeyType}

otherinfo;//typedef RedTyper[MAXSIZE+1r[0int8}8 直 排 第i（i＞1）個記錄時，前面的i-1個 ?

ri-

? 有序序 無序序 ?

r'i-

? 直 [初始關鍵

（49）38

97761327

97761327

（65）（38

761327

（97）（3849

1327

（76）（3849

76

27

（13）（1338

657697）27

（27）（132738496576（49）（13274849496576 StatusInsertSort(SqList&L{for(i=2;i<=L.length;++iif(LT(L.r[i].key,L.r[i-1].key)L.r[0].key //設置for(j=i-1;LT(L.r[0].key,L.r[j].key);--L.r[j+1]=L.r[j+1]=}

//記錄 到正確位直排直排序算法是穩定 直 最好的情況（正序序列n“比較”次數=1n-的情況（逆序序列n“比較”次數=in

(n+2)(n-2n

“移動”次數2+(i-1)=( 平均復雜

如何改進直 在第i（i＞1）個記錄時，前面i-1個記錄已經排好序，在尋找位置時，可折 例 … …s

668585858585 m

85) 排序基本接排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接排序。 具體實現 然后取d2<d1，重復上述分組和排序操作；di=1，即所有記錄放進一個組中排序 一趟排序結果 由于兩趟的排序中，記錄的關鍵字是 交換排序的基本反），則交換它們的位置。 反序

≤……≤rn-

1≤j≤i-

有序已經位于最終位初始第一趟排序第二趟排序后第三趟排序后第四趟排序第五趟排序第六趟排序后逐步減少減少總的比較次數和移動次較小記錄從后面直接移動到 由此，以該“界點i為分界線，基本R[s..t被分割成兩部分：R[s..i-1]無無序序無序子序列無序子序列快速排 無序子序列無序子序列將 到r[0]中，從high所指的位置lowlow所指位置起向后搜pivotkey的記錄，到intPartition(SqList&L,intlow,inthigh{L.r[0]=pivotkey=while(low<high{while(low<high&&L.r[high].key>=pivotkey--L.r[low]=while(low<high&&L.r[&&].key<=pivotkey++low;L.r[high]=L.r[low];}L.r[low]L.r[0];returnlow;}//

樞軸返回樞軸pivotkey= 第一次交

8第二次交

pivotkey= 第四次交

第一趟完

子序列

low 子序列初始{}一趟快速排序{}{}分別進行快速{}{}結結{}{}{結}結有序序{}整個快速排序遞歸進QSort(SqList&L,intlow,inthigh//對表LL.r[low?high快速if(lowhigh 度大于{pivotloc=Partition(L,low,highL.r[low?high]一分為QSort(L,low,pivotloc-1//對低子表遞歸排序，pivotloc是界點位QSortLpivotloc+1high高子}}voidQuickSortSqList&L//對順序表L QSort(L,1,} 快速排序特結構：順時間復雜度為Onlog2n空間復雜度為O(log2n)情況：每次劃分選擇樞軸是最小或最大元 最好情況（每次劃分折半 49 選擇排序基本思有序序

無序序 ?

ri-

交最小 ?

ri-

ri+1

一趟簡單選擇排序：通過n-i次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，并和第i（1<=i<=n）個記錄交換。voidSelectSort(SqList&L for(i=1;i<L.length;++i{j=SelectMinKey(L,i);if(i!=j)L.r[i]<=>}}對于n個關n-1選擇排序。例： 初始：[

27j

一趟

[27 38]j [38[65[65[76[97排序結束簡單選擇排序算法的性能分移動次比較次

n-

1n(n-1)2

穩定性：是一種穩定的排序算法 改進的著眼點：如何減少關鍵碼之間的比次數減少減少關鍵碼間的比查找查找最小值的同時n元素的{k1，k2，……，kn}，當僅當滿足以下關系時，稱之為堆ki

ki

大根ki

ki>=

堆是什么東

i=1，2，……，n/2與二叉樹的性質5增加了限制條件的完采用一維數大根堆的根結點所有結點的最大較大結

點，但不絕對

采用順 采用順 將堆用順 結構 ，則堆對應一組序列。堆排⑴如何由一個無序序列建成一個堆（即初始建堆⑶如何調整剩余記錄，成為一個新堆（即重建堆 1

用堆中最后 進

個元素替代

篩8 2

76 繼 篩

76 繼 輸 76

76

76

輸出

輸出：13輸出：13

輸出：輸出：1327輸出：13 輸出：輸出：1327輸出：132738輸出：132738

輸出：13輸出：1327384950輸出：13273849輸出：13273849

輸出：13輸出：1327384950輸出：132738495065 輸出：輸出：13273849506576后一個非終端結點是第n/2」個元素，由此篩選只需從第n/2」個元素開始。錄，則可看成n有序的子序列，每個子兩兩合并n/2個長度21的有序子序再兩兩合如此重復，直至得到一個長度為n的有序序列為止。例初始關鍵一趟歸并二趟歸并后： 三趟歸并后： 基數排

借助多關鍵字排序的方法對單關鍵字排包含多kk1,k2,…,kd的單關鍵字 最低位優例：對52 牌排<梅花,2><梅花,3>…<梅花<方塊,2><方塊,3>…<方塊<紅桃,2><紅桃,3>…<紅桃<黑桃,2><黑桃,3>…<黑桃排序方先按花色分類，再按面值分先按面值分類，再按花色分最優按花色（最）分梅花：13方塊：13張紅桃：13張黑桃：13每一堆按面值從小<梅花,2><梅花,3><梅花<方塊,2><方塊,3><方塊<紅桃,2><紅桃,3><紅桃<黑桃,2><黑桃,3>…<黑桃 最低位分配（按面值<梅花,2>梅花,3<梅花<方塊,2>方塊,3<方塊<紅桃,2>紅桃,3><紅桃<黑桃,2>黑桃,3><黑桃收集（按面值有序2：4張，3：4張，4：4張…A：4分配（按花色Initiallist：4691(按個) )收集：91319222((按) )收集：15223135468591

typedefsturctintnext;}

key[MAX_NUM_KEYtypedefsturctSLCellr[MAXSIZEintbitnum; intrednum;//記錄個數}typedefintArrType[RADIX 基數排序的特間復O(d(n+r))穩排序算法小直直接排

平均時 最 輔助空間穩定 穩 穩 不穩 不穩歸并基數

O(log