【正文】 作 ， 整個(gè)排序的時(shí)間開銷就可以大大減少 。 希爾排序的方法（續(xù)） ?希爾排序方法的一開始組數(shù)較多而組中記錄較少 ， 各組中記錄的直接插入排序是處在 n值很小的情況下進(jìn)行 ， 有著較高的效率；并且在不滿足次序時(shí)的移動 ， 是用較少的移動次數(shù)而得到了記錄的較大移動距離 。 ?但也有人提出不同的 di選取方法 ， 如克努特 （ Knuth） 提出的方法是 d1=,di+1=(i=2， 3， 4 … )。 d = n。i++) {j = i。 (R[0].key R[jd].key)) {R[j] = R[jd]。 } /*shellsorting end*/ 希爾排序（續(xù)） ?需要說明的是 ， 算法中沒有調(diào)用直接插入排序算法insertsorting， 而是獨(dú)立設(shè)計(jì)直接插入排序的部分；這是因?yàn)橄柵判蛑芯嚯x為 d的倍數(shù)的記錄為一組 ， 組中成員記錄之間有間隔不連續(xù)不能直接調(diào)用的緣故 。 由于在各趟排序中的增量 d1,d2 … di是逐次縮小的 ， 而待排序文件中各記錄的位置空間安排好之后不宜變動（ 移動需時(shí)間開銷 ） ， 所以 d可選為 di中的最大值 d1， 即一次性安排監(jiān)視哨空間并固定不變； ?另外 ， 監(jiān)視哨中的值應(yīng)在不同組中的不同記錄插入時(shí)安排不同的值 （ 即待插入記錄的值 ） ， 但是多次更換監(jiān)視哨中的值既繁瑣又影響效率 ， 我們可以考慮在排序之前一次性設(shè)置各監(jiān)視哨的值 ， 可設(shè)置為不超過待排序文件中最小關(guān)鍵字值的某一個(gè)值如 maxint。i=(n+1)/2。 for(i=2*d+1。 while(R[0].keyR[jd].key) {R[j] = R[jd]。 } /*shellsort end*/ 希爾排序的算法分析 ?在前面給出的兩個(gè)算法 ， 除了是否設(shè)置監(jiān)視哨外 ， 排序的方法是相同的 ， 其時(shí)間復(fù)雜度也是相同的；其增量序列為 d1= ， di= (i2)。 由算法分析的乘法法則可知 ， 前面給出的兩個(gè)希爾排序算法 ，shellsorting和 shellsort的時(shí)間復(fù)雜度為 O(n(log2n)2)。 ?二分法插入排序與直接插入排序相比較 ， 僅是減少了尋找插入位置時(shí)的關(guān)鍵字比較次數(shù) ， 記錄的移動次數(shù)沒有改變 ，其時(shí)間復(fù)雜度仍為 O(n2)； ?所需的輔助存儲空間也與直接插入排序相同 ， 也是穩(wěn)定的排序方法 （ 在檢索位置出現(xiàn)關(guān)鍵字值相等時(shí)需后移插入位置指示器變量 ， 否則為不穩(wěn)定方法 ） 。 二路插入排序舉例 二路插入排序舉例（續(xù)） 二路插入排序（續(xù)） ?在二路插入排序中 ， 記錄的移動次數(shù)約為 n2/8， 比直接插入排序減少移動次數(shù)約一半 。 ?共享?xiàng)２迦肱判?（ shared stack insertion sort）也是對直接插入排序的一種改進(jìn)方法 。 即 R[i].key≥R[top1].key 且R[i].key≤R[top2].key時(shí)進(jìn)棧 1， 只須改變 top1的值為top1+1即可 。 由棧 2傳送到棧 1一個(gè)記錄 ， 需要把 R[i+1]到 R[top21]的記錄后移一個(gè)位置 。 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡介 交換排序 ?交換排序 的基本方法是 ， 兩兩比較待排序記錄的關(guān)鍵字值 ， 并交換那些不滿足順序要求的記錄對 ， 直到全部待排序記錄都已滿足順序要求時(shí)為止 。 冒泡排序算法 ?冒泡排序的具體做法是： ?將關(guān)鍵字縱向排列 ， 然后自下而上地對相鄰兩個(gè)記錄的關(guān)鍵字進(jìn)行比較 ， 若為逆序 （ 即 R[j1].keyR[j].key，j=n,n1… 2） 則交換兩個(gè)記錄 ， 直到全部記錄都比較和交換完畢 （ 即 j=2） ， 第一趟冒泡排序結(jié)束； ?此時(shí)最小關(guān)鍵字值的記錄上浮到了 R[1]的位置上 。 ?事實(shí)上存在不需要 n1趟就可以完全排好序的情況 ，如上例的第五趟排序后就已經(jīng)排好序了； ?其識別辦法是 ， 若某一趟冒泡排序過程中沒有進(jìn)行記錄的位置交換 ， 則說明待排序文件已經(jīng)完全排好序了 。 for(i=1。j = i+1。 flag=flag+1。 ?在平均情況下 ， 關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)大約為最壞情況下的一半 ， 因此冒泡排序算法的時(shí)間復(fù)雜度為 O(n2)。 交替變化掃描方向可以加速最輕和最重的氣泡向兩端迅速沉浮 ， 有利于加速排序過程 。 快速排序算法 ?設(shè)兩個(gè)指示器變量 i和 j， 分別指向待排序區(qū)間的第一個(gè)記錄和最后一個(gè)記錄； ?先將第一個(gè)記錄移到暫存變量 temp中 ， 然后 j從區(qū)間的最后一個(gè)記錄起向前掃描 ， 直到找到滿足 R[j].key的記錄時(shí) ， 將 R[j]移入 R[i]中； ?再令 i 自 i+1 起 向 后 掃 描 ， 直 到 找 到 滿 足R[i].key ， 將 R[i]移入 R[j]中； ?就這樣 j自 j1從后向前掃描一次移入一個(gè) R[j]于 R[i]中 ，i自 i+1從前向后掃描一次移入一個(gè) R[i]于 R[j]中 ， 反復(fù)交替的掃描和移動記錄； ?直到 i=j時(shí)把 temp移入 R[i]中 （ 區(qū)間中第一個(gè)記錄應(yīng)在的位置 ） ， 它把整個(gè)待排序區(qū)間分割為相互獨(dú)立的兩個(gè)更小的區(qū)間 。 j=t。(ij)) j。amp。 } }while(ij)。 調(diào)用 divideareasort對 R[ ]進(jìn)行快速排序的遞歸算法可描述如下： void quicksort(recordtype R[],int s,int t) {int i。 } } /*quicksort end*/ 快速排序的算法舉例 ?下面我們使用快速排序算法對關(guān)鍵字序列 （ 36， 73， 65，97， 13， 27， ， 29） 排序 ， 在下面的排序過程示例中 ，先給出第一趟中的區(qū)間分割的整個(gè)過程 ， 然后給出各趟的排序結(jié)果；用方括號表示區(qū)間 ， 用方框表示暫存變量 temp的關(guān)鍵字值 （ 并未參加交換 ， 在分割完成后才放入最終位置上 ） 。 ?在 最好的情況 下 ， 基準(zhǔn)二叉樹是一棵理想的平衡二叉檢索樹 ， 深度為 ， 遞歸所需棧的存儲開銷為 O(log2n)，時(shí)間開銷為結(jié)點(diǎn)數(shù)乘平均檢索長度 ， 即 O(n?log2n)。 ?所謂三者取中是指在 R[s]、 R[t]和 R[(s+t)/2]三者中選取關(guān)鍵字值居中的記錄作為分割區(qū)間的基準(zhǔn) ， 這種選取基準(zhǔn)記錄的方法可以大大改善快速排序在最壞情況下的性能 。 選擇排序 直接選擇排序 樹形選擇排序 堆排序 直接選擇排序 ?直接選擇排序 （ direct selection sort） 也稱作簡單選擇排序 。 for(i=1。i=n。 R[m]=temp。 ? 由于在直接選擇排序中存在著任意位置上的記錄互換的可能性 ， 所以有可能改變具有相同關(guān)鍵字值的記錄的相對位置次序 ， 如 （ 5, ,2） 的直接選擇排序結(jié)果為 （ 2, ,5） ； ?因此直接選擇排序方法是 不穩(wěn)定的 。 樹形選擇排序舉例 ?選擇關(guān)鍵字值最小的記錄放在根結(jié)點(diǎn)位置的過程如下圖 (a)的二叉樹所示 。 ?樹形選擇排序的缺點(diǎn)是需要的輔助空間較多 ， 需要用 n1個(gè)記錄大小的空間來保存各層次的比較結(jié)果；此外 ， 與 ∞ 進(jìn)行多余的比較也是其缺點(diǎn)之一 。 ?因此在一個(gè)堆中 ， 堆頂元素 （ 完全二叉樹的根 ） 必為堆中的最小 （ 或最大 ） 元素 ， 并且堆中的每一棵子樹也都是堆 。 創(chuàng)建初始堆 ?先討論建初始堆問題 。 ?這種方法就像過篩子一樣 ， 把最小關(guān)鍵字值的記錄一層一層地篩選出來 ， 最后輸出堆頂?shù)?最小關(guān)鍵字記錄 。 ?由于除根結(jié)點(diǎn) K1之外的所有子樹仍然具有堆的性質(zhì) ， 故只需要對根結(jié)點(diǎn)自上而下調(diào)整即可 。 堆排序過程舉例（續(xù)） ?由于 K3K2且 K3K1， 則 82與 25所在的兩個(gè)記錄交換位置； ?又由于交換破壞了右子樹的堆 ， 則需再次進(jìn)行類似的調(diào)整 ， 直至進(jìn)行到葉子結(jié)點(diǎn)； ?調(diào)整后的狀態(tài)如圖 (c)所示 ， 即得到一個(gè)有 n1個(gè)記錄的新堆 ， 同時(shí)得到次小關(guān)鍵字 25所在的記錄 。 篩選算法的算法描述 void heapadjust(recordtype R[],int s,int t) {int i,j。 j=2*i。 if(R[j].key) {R[i]=R[j]。 } R[i]=temp。i=1。i) {temp=R[1]。 } } /*heapadjust end*/ 堆排序的算法分析 ?堆排序的性能分析如下：設(shè)表示堆的完全二叉樹深度為h， h= ， 從根到葉的篩選過程中 ， 關(guān)鍵字的比較次數(shù)至多為 2（ k1） 次 ， 至多交換記錄 k次 。 ?堆排序 適宜用于 待排序文件中記錄較多的情況 ， 因?yàn)槠渲饕獣r(shí)間開銷在于建堆和調(diào)整堆 ， 記錄較少時(shí)不合算 。 這種排序方法稱為 二路歸并排序 （ twoway merge sort） 。 i=L。amp。 while(j=h) R1[k++]=R[j++]。 if(L==h) R1[L]=R[L]。 merge(R1,L,m,h,R)。 ?進(jìn)行一趟歸并排序時(shí)調(diào)用算法 merge， 依次對相鄰的兩個(gè)長度為 len的有序子序列歸并；當(dāng)有序子序列為奇數(shù)個(gè)或雖為偶數(shù)個(gè)但最后一個(gè)有序子序列長度小于 len時(shí)的兩種情況做特殊處理 。 } if(i+len1n) merge(R,i,i+len1,n,R1)。 recordtype R1[]。 len=2*len。 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡介 二路歸并排序的算法分析 ?前面介紹的各種排序方法 ， 都是通過 對待排序文件中記錄的關(guān)鍵字值大小的比較 來進(jìn)行的 。 ?因此 ， 要比較任意兩張撲克牌的大小 ， 方法是先比較花色 ， 若花色相同時(shí)再比較點(diǎn)力 。上述的例子可以推廣到一般情況下： ?設(shè)待排序文件 R的 n個(gè)記錄 （ R1,R2 … Rn） 中 ， 每個(gè)記錄 Ri都含有 d個(gè)關(guān)鍵字位 （ … ） ， 稱其中兩個(gè)記錄有序 （ 即 RiRj） 是指滿足條件 ； ?若對于任意記錄都滿足 RiRj（ 1≤ i≤ j≤ n） ， 則稱待排序文件 R有序；利用 d個(gè)關(guān)鍵字位整理待排序文件 R有序的過程 ， 稱作 多關(guān)鍵字排序 。 ?它是先按最低關(guān)鍵字位 對待排序文件中的 n個(gè)記錄進(jìn)行排序 ， 按 的值把待排序文件中的 n個(gè)記錄分配到具有不同 值的若干個(gè)堆 ， ?然后按 值從小到大的次序收集在一起；下一次再按高一位關(guān)鍵字位 的值進(jìn)行分配和收集 ， 如此不斷地按更高一位關(guān)鍵字位進(jìn)行分配和收集； ?直到用 分配和收集之后 ， 整個(gè)文件按多關(guān)鍵字位 有序 。 ?假設(shè)含有 n個(gè)記錄的待排序文件中 ， 每個(gè)記錄的關(guān)鍵字由 d 個(gè)關(guān)鍵字位 組成 ， 并且每個(gè)關(guān)鍵字位的取值范圍都相同 ， 即 c1≤ ≤c rd（ 1≤j≤d ） ； ?關(guān)鍵字位可能的取值個(gè)數(shù) rd稱為 基數(shù) 。 排序從最低關(guān)鍵字位 開始直到最高關(guān)鍵字位 ； ?每一趟按一個(gè)關(guān)鍵字位的值把各記錄分配到 rd個(gè)鏈隊(duì)列中去 ， 同一鏈隊(duì)列中的記錄都是用鏈域指針鏈接起來的 ， 所有的隊(duì)頭和隊(duì)尾指針分別存放在兩個(gè)數(shù)組中 ， 每一趟分配后通過修改指針將這 rd個(gè)鏈隊(duì)列中的記錄收集起來； ?如此這樣重復(fù)分配和收集 d趟 ， 便得到了待排序文件中各記錄的一個(gè)有序序列 。 ?在第三趟收集之后得到的單鏈表 （ 如下圖 (g)所示 ） ， 就是最終得到的排序結(jié)果 。 datatype other。 int f[rd],e[rd]。 for(i=d。j++) /*隊(duì)列頭指針初始化為 null*/ f[j]=1。 e[k]=p。 p=f[j]。 t=e[