【正文】 ?所以希爾排序始終是在較高的效率下工作 。 希爾排序中增量 di的選擇可以有不同的取法 ， 一般是采用希爾在最早時提出的方法 ， 即 d1=,di+1=(i=2， 3， 4 … )。 ?但也有人提出不同的 di選取方法 ， 如克努特 （ Knuth） 提出的方法是 d1=,di+1=(i=2， 3， 4 … )。 如何選取增量序列才能產(chǎn)生最好的排序效果 ， 至今仍無法從數(shù)學(xué)角度得出圓滿的結(jié)論；然而逐步縮小增量和最后一次增量為 1是大家不爭的事實 。 希爾排序舉例 ?設(shè)待排序文件中有 10個記錄 ， 初始關(guān)鍵字序列為 (52,38,66,87,77,16,30,62,07)， 增量序列依次為 5,3,1， 排序過程如下： 希爾排序舉例（續(xù)） 希爾排序舉例（續(xù)） ?第一趟排序時 d1=5， 把待排序文件分成五組 ， 即（ R1， R6） 、 （ R2， R7） 、 （ R3， R8） 、 （ R4， R9）和 （ R5， R10） ， 各組中第一個記錄都自成長度為 1的有序區(qū) ， 依次把各組的第二個記錄插入有序區(qū)中得到第一趟排序結(jié)果； ?第二趟排序時 d2=3， 把待排序文件分成三組 ， 即（ R1， R4， R7， R10） 、 （ R2， R5， R8） 和 （ R3， R6，R9） ， 對各組進行直接插入排序后得到第二趟排序結(jié)果； ?第三趟排序時 d3=1， 整個待排序文件為一組 ， 對整個文件做直接插入排序得到的第三趟排序結(jié)果 ， 使整個待排序文件按關(guān)鍵字值有序 ， 即得到最終的排序結(jié)果 。 希爾排序的算法描述 (不設(shè)置監(jiān)視哨 ) ? 若不設(shè)置監(jiān)視哨 ， 希爾排序的算法可描述如下： void shellsorting(recordtype R[],int n) {int i,j,d。 d = n。 do {d = (d+1)/2。 for(i = d+1。i = n。i++) {j = i。 R[0] = R[j]。 while((j d) amp。amp。 (R[0].key R[jd].key)) {R[j] = R[jd]。 j = jd。 } R[j+d] = R[0]。 } }while(d 1)。 } /*shellsorting end*/ 希爾排序（續(xù)） ?需要說明的是 ， 算法中沒有調(diào)用直接插入排序算法insertsorting， 而是獨立設(shè)計直接插入排序的部分；這是因為希爾排序中距離為 d的倍數(shù)的記錄為一組 ， 組中成員記錄之間有間隔不連續(xù)不能直接調(diào)用的緣故 。 ?另外 ， 在 for循環(huán)中的分組執(zhí)行直接插入排序的過程 ，是依次先插入 d個組中的第二個記錄 ， 再插入 d個組中的第三個記錄 …… 最后插入 d個組中的最后一個記錄；是 d個組的交替插入過程 ， 而不是一個組的直接插入排序完成后再進行下一組 ， 這樣有利于算法設(shè)計的簡潔性和算法描述的方便性 。 希爾排序（續(xù)） ? 如果考慮設(shè)置監(jiān)視哨 ， 很自然地會考慮到仿照直接插入排序算法中的 監(jiān)視哨設(shè)置 辦法 。 對于增量為 d的一趟希爾排序 ， 待排序文件被分成 d 組 ， 各組中記錄之間的距離為 d；需要在 R[1]到 R[d]處設(shè)置監(jiān)視哨 ， 而在 R[d+1]到 R[d+n]處安排待排序文件中的 n個記錄 。 由于在各趟排序中的增量 d1,d2 … di是逐次縮小的 ， 而待排序文件中各記錄的位置空間安排好之后不宜變動（ 移動需時間開銷 ） ， 所以 d可選為 di中的最大值 d1， 即一次性安排監(jiān)視哨空間并固定不變； ?另外 ， 監(jiān)視哨中的值應(yīng)在不同組中的不同記錄插入時安排不同的值 （ 即待插入記錄的值 ） ， 但是多次更換監(jiān)視哨中的值既繁瑣又影響效率 ， 我們可以考慮在排序之前一次性設(shè)置各監(jiān)視哨的值 ， 可設(shè)置為不超過待排序文件中最小關(guān)鍵字值的某一個值如 maxint。 這種監(jiān)視哨的設(shè)置方法 ， 沒有在監(jiān)視哨中保存各組中的一個個待插入記錄 ， 但可以統(tǒng)一保存待插入記錄于R[0]中 。 希爾排序的算法描述 (設(shè)置監(jiān)視哨 ) ? 設(shè)置監(jiān)視哨的希爾排序算法可描述如下： void shellsort(recordtype R[],int n) {int i,j,d。 for(i=1。i=(n+1)/2。i++) R[i].key = maxint。 d = n。 do {d = (d+1)/2。 for(i=2*d+1。i=d+n。i++) {j = i。 R[0] = R[j]。 while(R[0].keyR[jd].key) {R[j] = R[jd]。 j = j – d。} R[j+d] = R[0] 。} }while(d 1)。 } /*shellsort end*/ 希爾排序的算法分析 ?在前面給出的兩個算法 ， 除了是否設(shè)置監(jiān)視哨外 ， 排序的方法是相同的 ， 其時間復(fù)雜度也是相同的；其增量序列為 d1= ， di= (i2)。 算法中的主要時間開銷在于三重循環(huán)： ?外層 dowhile循環(huán)控制排序趟數(shù) ， 共執(zhí)行 log2n次 。 ?中層的 for循環(huán)控制一趟中各組記錄的直接插入排序 ， 執(zhí)行次數(shù)依次為 次； 其平均次數(shù)為 ；即中層 for循環(huán)的平均執(zhí)行次數(shù)不超過 n。 ?內(nèi)層的 while循環(huán)確定各組中每個記錄的插入位置 ， 進行關(guān)鍵字的比較和記錄的移動操作； 希爾排序的算法分析 （續(xù)） ?在最好的情況下只執(zhí)行一次比較而無記錄移動 ， 其一趟中總 的 比 較 次 數(shù) 與 中 層 for 循 環(huán) 的 執(zhí) 行 次 數(shù) 相 同 ，為 ； ?而一趟中執(zhí)行插入的次數(shù)為 ndi， 即平均比較次數(shù)不超過 ,更不會超過 log2n次； ?由于希爾排序算法中開始時兩個記錄一組 ， 以后隨著組數(shù)的減少組中記錄增多也逐步基本有序 ， 所以在 n較大時的其它情況下的平均比較次數(shù)也是接近于最好情況下的次數(shù) log2n或是它的線性函數(shù) ， 而移動次數(shù)或平均移動次數(shù)是遠遠小于比較次數(shù)和平均比較次數(shù)的； ?由此得內(nèi)層 while循環(huán)的平均執(zhí)行次數(shù)為 O(log2n)階函數(shù) 。 由算法分析的乘法法則可知 ， 前面給出的兩個希爾排序算法 ，shellsorting和 shellsort的時間復(fù)雜度為 O(n(log2n)2)。 插入排序 直接插入排序 希爾排序 其它插入排序簡介 ? 由第七章的討論我們知道 ， 對有序表采用二分法檢索 ， 檢索性能大大優(yōu)于順序檢索 。 ?如果我們把直接插入排序中的由后向前順序檢索尋找插入位置的方法改為用二分法檢索來實現(xiàn) ， 當 n較大時就可以大幅度地降低關(guān)鍵字的比較次數(shù) 。 我們把經(jīng)過這種改進后的插入排序方法 ， 稱作 二分法插入排序 （ binary insertion sort） 。 ?二分法插入排序與直接插入排序相比較 ， 僅是減少了尋找插入位置時的關(guān)鍵字比較次數(shù) ， 記錄的移動次數(shù)沒有改變 ，其時間復(fù)雜度仍為 O(n2)； ?所需的輔助存儲空間也與直接插入排序相同 ， 也是穩(wěn)定的排序方法 （ 在檢索位置出現(xiàn)關(guān)鍵字值相等時需后移插入位置指示器變量 ， 否則為不穩(wěn)定方法 ） 。 ?二路插入排序 （ 2way insertion sort） 是在二分法插入排序基礎(chǔ)上的進一步改進 ， 改進的目標是減少排序過程中記錄的移動次數(shù) ， 但為此多開銷了 n個記錄大小的輔助存儲空間 。 ?其具體方法是： ?另設(shè)一個和 R同類型的數(shù)組 S， 先將 R[1]賦給 S[1]， 并將S[1]看成是在已排好序序列中處于中間位置的記錄； ?然后從 R中第二個記錄起 ， 依次插入到 S[1]之前或 S[1]之后的有序序列中去 ， ?若待插記錄的關(guān)鍵字小于 S[1].key則插入 S[1]之前的有序表中 ， 否則插入 S[1]之后的有序表中 。 ?在算法實現(xiàn)時 ， 把 S數(shù)組看成是一個循環(huán)數(shù)組 ， 并設(shè)兩個指針 first和 final分別指示排序過程中得到的有序序列中的第一個記錄和最后一個記錄在 S中的位置 。 二路插入排序舉例 二路插入排序舉例（續(xù)） 二路插入排序（續(xù)） ?在二路插入排序中 ， 記錄的移動次數(shù)約為 n2/8， 比直接插入排序減少移動次數(shù)約一半 。 它只能減少移動次數(shù)而不能絕對避免移動記錄 ， 若要大幅度降低移動次數(shù) ， 可改變存儲結(jié)構(gòu)為靜態(tài)鏈表 ， 進行表插入排序 。 ?此外 ， 二路插入排序中 ， 當 R[1]為待排序文件中最小或最大關(guān)鍵字的記錄時 ， 完全失去優(yōu)越性退化為直接插入排序的時間效率 。 ?二路插入排序 ， 是一種 穩(wěn)定的排序 方法 。 ?共享棧插入排序 （ shared stack insertion sort）也是對直接插入排序的一種改進方法 。 ?其基本思想是： ?把待排序的記錄數(shù)組 R看作是一個靜態(tài)的共享棧 （ 棧 1和棧 2） ， 棧 1按數(shù)組下標由小到大方向增長 ， 棧 2按數(shù)組下標由大到小方向增長；棧 1中按關(guān)鍵字升序排列壓入待排序記錄 ， 棧 2中按關(guān)鍵字降序排列壓入待排序記錄 。 ?一開始先比較 R[1]和 R[n]的關(guān)鍵字值大小 ， 若 R[1]R[n]則交換； top1=1,top2=n； ?然后把 R[2]到 R[n1]逐一插入兩個棧中 ， 插入的過程中始終保證棧 1的棧頂記錄的關(guān)鍵字值都不大于棧 2 的棧頂記錄的關(guān)鍵字值 。 共享棧插入排序（續(xù)） ?為此需要區(qū)分以下三種情況并作相應(yīng)處理： ?當待插入記錄 R[i]的關(guān)鍵字值不小于棧 1 的棧頂記錄的關(guān)鍵字值且不大于棧 2的棧頂記錄的關(guān)鍵字值時 ， 將待插記錄壓 入 棧 1 中 。 即 R[i].key≥R[top1].key 且R[i].key≤R[top2].key時進棧 1， 只須改變 top1的值為top1+1即可 。 ?當 R[i].key[top1].key時 ， 由棧 1反復(fù)傳送記錄到棧 2，直到 R[i].key≥R[top1].key時將 R[i]插入棧 1。 由棧 1傳送到棧 2一個記錄 ， 需要把 R[i+1]到 R[top21]的記錄前移一個位置 。 ?當 R[i].key[top2].key時 ， 由棧 2反復(fù)傳送記錄到棧 1，直到 R[i].key≤[top2].key時將 R[i]插入棧 2。 由棧 2傳送到棧 1一個記錄 ， 需要把 R[i+1]到 R[top21]的記錄后移一個位置 。 共享棧插入排序舉例 共享棧插入排序舉例（續(xù)） 共享棧插入排序（續(xù)） ?共享棧插入排序不需要增加額外的存儲開銷 ， 在時間性能上與二路插入排序相當 ， 而且有效地避免了因 R[1]為待排序記錄中關(guān)鍵字值為最大或最小記錄時完全失去優(yōu)越性的不足 。 ?若增加存儲開銷另設(shè)與 R相同類型的數(shù)組作為共享棧 ， 則可以進一步減少移動次數(shù) ， 且排序結(jié)果不象二路插入排序那樣要使用循環(huán)數(shù)組解釋 。 ?共享棧插入排序是一種 穩(wěn)定的排序 方法 。 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡介 交換排序 ?交換排序 的基本方法是 ， 兩兩比較待排序記錄的關(guān)鍵字值 ， 并交換那些不滿足順序要求的記錄對 ， 直到全部待排序記錄都已滿足順序要求時為止 。 ?本節(jié)介紹兩種交換排序的方法： ?一種是冒泡排序 ， ?一種是快速排序 。 交換排序 冒泡排序 快速排序 冒泡排序 ?冒泡排序 （ bubble sort） 也稱作起泡排序 ， 是一種簡單的排序方法 。 ?它是通過相鄰記錄之間的關(guān)鍵字比較和記錄交換 ，使關(guān)鍵字值較小的記錄由底部向上移動 ， 而關(guān)鍵字值較大的記錄由頂部向下移動 ， 就象水中的氣泡向上飄浮 （ 冒泡 ） 一樣 。 冒泡排序算法 ?冒泡排序的具體做法是： ?將關(guān)鍵字縱向排列 ， 然后自下而上地對相鄰兩個記錄的關(guān)鍵字進行比較 ， 若為逆序 （ 即 R[j1].keyR[j].key，j=n,n