【正文】 1 13 04 49` 38 27 49 55 65 97 76 共交換 12次 04 13 49` 38 27 49 55 65 97 76 快速排序 快速排序是目前內部排序中最快的方法 。 ⒉ 具體步驟 (1) 置變量 i， j初值分別為文件的首、尾記錄位置； 選取文件首記錄 r[i]，并將其關鍵字賦給變量 x； (2) 從 j 位置開始向前搜索， (3) 直到遇到第一個關鍵字小于 x的記錄， (4) 并將 r[j]移至 r[i]； (5) 從 i 位置開始向后搜索， (6) 直到遇到第一個關鍵字大于 x的記錄， (7) 并將 r[i]移至 r[j]； (8) 重復 (2) (9) 直到 i=j， (10) 并將 x移至 r[i]，以 r[i]為中樞將文件分為 r[1..i1]和r[i+1..n]兩部分，完成一趟排序； (11) 重復 (1)至 (10)，直到每一部分只剩上一個記錄，整個文件已有序，快速排序算法結束。 快速排序 ⒊ 一趟快速排序算法 PROC qkpass(VAR r:listtype。 VAR i:integer)。 j:=t。 x:=r[s].key。 r[i]:=r[j]。 r[j]:=r[i] ] r[i]:=rp ENDP。 對待排序文件 49 4939。 49 65 ⑵ 快速排序的效率跟初始文件中關鍵字的排列和選取劃分的記錄有關 。 (4)快速排序算法的平均時間復雜度為 O(nlogn)。 1 n 第一趟 ． n個記錄 第二趟 ． n1 ．．． ．．． 第ｎ 1趟 2 比較次數 n1 n2 1 選擇排序 ⒉ 簡單選擇排序算法 PROC smpselecsort(VAR r:listtype)。 FOR j:=i+1 TO n DO IF r[j].key＜ r[k].key THEN k:=j。 {smpselecsort} 選擇排序 ⒊ 算法分析 ⑴ 交換次數：正序時交換次數最少 ， 為 0次 ， 逆序時最多 ， 為 n1次 。 ⑶ 簡單選擇排序時間復雜度為 O(n2)， 并且是穩(wěn)定的排序 。 選擇排序 若將堆視為一個完全二叉樹 （ 圖一 ） ， 則堆的含義為：完全二叉樹中所有非終端結點的值均不大于 (或不小于 )其左 、右孩子的值 （ 圖二 ） 。 k3 k1 k5 k2 k4 ．．．．．．．． 圖一 24 12 47 38 85 91 30 53 圖二 選擇排序 ⒉ 堆排序基本思想 ⑴ 以初始關鍵字序列 ， 建立堆； ⑵ 輸出堆頂最小元素； ⑶ 調整余下的元素 ， 使其成為一個新堆； ⑷ 重復 ⑵ ,⑶ n 次 ， 得到 一個有序序列 。 稱這個調整過程為 篩選 。 k,m:integer)。 要求 :調整 r[k]使 r[k..m]為堆 } i:=k。 x:=r[k].key。 finished:=false。 {滿足條件 ,沿右枝篩選 } IF x≤r[j].key THEN finished:=true ELSE [ r[i]:=r[j]。 j:=2*i] ] r[i]:=t ENDP。 13 49 76 38 49’ 97 65 27 65 49 76 38 97 49’ 13 27 27 13 76 38 49’ 97 65 49 例： {49， 38， 65， 97， 76， 13， 27， 49’} 選擇排序 ⒍ 堆排序過程 PROC headsort(VAR r:listtype)。 {自第 └ n/2┘開始篩選建堆 } FOR i:=n DOWNTO 2 DO [ r[1]←→r[i]。 {headsort} 堆排序是不穩(wěn)定的，時間復雜度為 O(nlogn)。 歸并排序基本思想：⑴將文件的每個記錄視為一個有序子文件；⑵然后兩兩子文件進行 2路歸并；⑶重復⑵，直到只剩一個長度為 n的有序文件 例：初始關鍵字： 49 38 65 97 76 13 27 49’ 第一趟后 38 49 65 97 13 76 27 49’ 第二趟后 38 49 65 97 13 27 49’ 76 第三趟后 13 27 38 49 49’ 65 76 97 每個記錄視為一個有序子文件，兩個子文件進行歸并，得 4個有序子文件。 l,m,n:integer。 { t[s..m]和 r[m+1..n] 為兩個有序子文件 , 歸并結果存放在 r2[s..n]中 } i:=s。 k:=s1。 {k為下一次存入 r2的位置 } IF r[i].key≤r[j].key THEN [ r2[k]:=r[i]。 i:=j+1] ]。 IF j≤n THEN r2[k+1..n]:=r[j..n] {將其中一個文件的余下部分復制到 r2的尾部 } ENDP。 基數排序 基數排序法是一種用多關鍵字排序思想對單邏輯關鍵字進行排序 ， 而無需進行關鍵字比較的新排序方法 ， 其基本操作是 “ 分配 ” 和 “ 收集 ” 。 設關鍵字有 d 位，每位的取值范圍為 r (稱為基數 )，則需要進行 d 趟分配與收集，需要設立 r 個隊列。 基數排序 2. 基數排序的步驟 ⑴ 從關鍵字的低位開始進行第 i趟 (i=1,2,...d)分配即將單鏈表中的記錄依次按關鍵字的第 i位分配到相應編號的隊列中； ⑵ 分配完畢后 ， 將各隊列的記錄按隊列編號順序收集成一個單鏈表； ⑶ 重復 ⑴⑵ ， 直到第 d趟收集完畢 ， 所得單鏈表已成為有序表 。 ⑶ 基數排序要進行 d趟分配和收集 ,需 r個隊列