【正文】 = jd。amp。 R[0] = R[j]。i = n。 do {d = (d+1)/2。 希爾排序的算法描述 (不設(shè)置監(jiān)視哨 ) ? 若不設(shè)置監(jiān)視哨 ， 希爾排序的算法可描述如下： void shellsorting(recordtype R[],int n) {int i,j,d。 如何選取增量序列才能產(chǎn)生最好的排序效果 ， 至今仍無(wú)法從數(shù)學(xué)角度得出圓滿的結(jié)論；然而逐步縮小增量和最后一次增量為 1是大家不爭(zhēng)的事實(shí) 。 希爾排序中增量 di的選擇可以有不同的取法 ， 一般是采用希爾在最早時(shí)提出的方法 ， 即 d1=,di+1=(i=2， 3， 4 … )。 ?隨著 di減小 ， 組數(shù)變少組中記錄個(gè)數(shù)變多的同時(shí) ， 組中記錄也逐步變得基本有序 ， 使得在一趟中進(jìn)行直接插入排序時(shí)的效率大大地提高 。 希爾排序的方法 ?希爾排序的方法 是： ?先選取一個(gè)小于 n的整數(shù) d1作為第一個(gè)增量 ， 把待排序文件中的全部記錄分成 d1個(gè)組 ， 將所有距離為 d1倍數(shù)的記錄放在同一個(gè)組中 ， 在各組內(nèi)進(jìn)行直接插入排序； ?然后選取第二個(gè)增量 d2d1， 重復(fù)上述的分組和排序工作；如此不斷地選取更小的增量 d3，d4 …… 并重復(fù)上述的分組和排序工作 ， ?直到所選取增量 di=1(didi1… d2d1)時(shí)所有記錄放在同一組中進(jìn)行直接插入排序后為止 。 ?另外 ， 當(dāng) n的值很小時(shí) ， n2的值受 n的值的影響也不太大 ， 直接插入排序的效率也比較高 。 ?由直接插入排序的分析可知 ， 在待排序文件已按關(guān)鍵字值遞增有序時(shí)的時(shí)間復(fù)雜度為 O(n)， 在逆序時(shí)的時(shí)間復(fù)雜度為O(n2)。 它是 1959年由 的對(duì)直接插入排序的一種改進(jìn)方法 。由于對(duì)于相同關(guān)鍵字值的記錄在排序前后相對(duì)位置不會(huì)發(fā)生變化 （ 如上例中的 48和 ） ， 所以直接插入排序是一種穩(wěn)定的排序方法 。 直接插入排序的算法分析 (續(xù) ) ?若初始文件中各記錄是隨機(jī)排列 ， 即關(guān)鍵字的各種排列的出現(xiàn)概率相同時(shí) ， 我們可取上述最好與最壞情況的平均值作為比較和移動(dòng)的平均次數(shù) ， 約為 n2/4,由此可得直接插入排序的時(shí)間復(fù)雜度為 O(n2)。 ?在最好的情況下是待排序文件中各記錄已經(jīng)按關(guān)鍵字遞增有序 ， 每一趟只需一次比較操作和兩次移動(dòng)操作 （ 即 R[i]=R[0]和 R[0]=R[i]） ,無(wú)需記錄后移；其比較次數(shù)為 n1次 ， 移動(dòng)操作次數(shù)為 2（ n1） 次 ，算法的時(shí)間復(fù)雜度為 O(n)。 } }/*insertsorting end*/ 直接插入排序的算法分析 ?在上面的算法中 ， 外層 for循環(huán)控制 n1趟插入 ， 內(nèi)層 while循環(huán)完成一趟的關(guān)鍵字比較 、 記錄后移和確定位置后的插入操作 。 j。 j=i1。i=n。 直接插入排序的算法描述 ? 直接插入排序的算法描述如下： void insertsorting(recordtype R[],int n) {int i,j。 ?由于后移操作會(huì)覆蓋第 i個(gè)記錄 ， 在算法描述中可在進(jìn)行第 i個(gè)記錄插入之前 ， 先保存其于 R0中再進(jìn)行比較后移操作；這個(gè)附加的 R0還可起到 “ 監(jiān)視哨 ” 的作用 ， 即當(dāng) Ki小于前面有序序列中的每一個(gè)關(guān)鍵字時(shí) ， 在和 R0中關(guān)鍵字 （ 它本身 ）比較時(shí)不會(huì)小于 ， 既找到了正確的插入位置 ， 又避免了循環(huán)控制變量的越界檢查 。 直接插入排序 舉例 ?例如 ， 已知待排序文件中記錄的關(guān)鍵字序列為 （ 23，48， 32， 107， 86， 75， 68） ， 直接插入排序的過(guò)程可示意如下： ?其中 ， 方括號(hào)表示已排好序的序列 ， i表示插入第 i個(gè)記錄 。 ?它的 基本思路 是： ?依次把待排序的記錄逐個(gè)插入已排好序的序列中 。 ?本節(jié)介紹的插入排序方法有 直接插入排序 和 希爾排序 ；并簡(jiǎn)介二分法插入排序 、 二路插入排序和共享?xiàng)２迦肱判?。 /*關(guān)鍵字 */ elemtype otheritems。 排序的基本概念（續(xù)） ?在本章主要討論內(nèi)部排序算法 ， 以記錄數(shù)組作為待排序文件的組織形式 ， 并假定關(guān)鍵字均為整數(shù) ，按遞增次序討論排序算法 （ 即討論升序排序問(wèn)題 ） 。 ?由于所需的輔助空間的量一般都不大 ， 所以排序的時(shí)間代價(jià)是衡量排序算法的最重要的因素 。通常待排序文件的組織形式有三種方式： ?以一維數(shù)組作為組織形式 ， 排序過(guò)程是對(duì)記錄本身進(jìn)行物理重排 ， 通過(guò)比較和判定把記錄移動(dòng)到合適的位置； ?以鏈表 （ 動(dòng)態(tài)鏈表或靜態(tài)鏈表 ） 作為組織形式 ， 排序過(guò)程中無(wú)需移動(dòng)記錄 ， 僅需修改指針即可 ， 通常把這類排序稱為表排序； ?為待排序文件組織一個(gè)輔助表 ， 如組織一張含關(guān)鍵字和指向記錄指針的索引表 ， 在排序過(guò)程中只需對(duì)輔助表的表目進(jìn)行物理重排 ， 不需移動(dòng)記錄本身 ， 在排序結(jié)束后按輔助表調(diào)整記錄位置 。 ?外部排序多是采用多路歸并方法進(jìn)行排序 。 ?內(nèi)部排序 是指待排序文件放在內(nèi)存中進(jìn)行排序的排序；內(nèi)部排序 適用于 記錄個(gè)數(shù)不很多的較小待排序文件的排序； ?外部排序 是指在待排序文件很大時(shí) ， 內(nèi)存中不能一次容納全部記錄 ， 還要借助于外存存放待排序文件 ， 在排序過(guò)程中需要對(duì)外存進(jìn)行訪問(wèn)的排序；外部排序則 適用于 記錄個(gè)數(shù)太多不能一次全部放入內(nèi)存的較大待排序文件的排序 。 ?當(dāng)排序碼是組合關(guān)鍵字時(shí) ， 通常稱作 多關(guān)鍵字排序 ， 其排序結(jié)果的惟一性取決于組合關(guān)鍵字是否能惟一標(biāo)識(shí)一個(gè)記錄 。 ?當(dāng)排序碼是次關(guān)鍵字時(shí) ， 同一關(guān)鍵字值可能標(biāo)識(shí)了兩個(gè)或兩個(gè)以上的記錄 ， 所以排序結(jié)果不惟一 。 ?排序碼可以是記錄的主關(guān)鍵字 ， 也可以是次關(guān)鍵字 ， 或者是多個(gè)關(guān)鍵字的組合 （ 即組合關(guān)鍵字 ） 。 ?若關(guān)鍵字滿足遞增 （ 即不減 ） 關(guān)系時(shí) ， 稱作按關(guān)鍵字 升序排序 (ascending sort)； ?若關(guān)鍵字滿足遞減 （ 即不增 ） 關(guān)系時(shí) ， 稱作按關(guān)鍵字 降序排序 (descending sort)。 排序的基本概念（續(xù)） ? 排序 的確切定義可以描述為： ?設(shè) （ R1， R2 … Rn） 是某文件的 n個(gè)記錄 ， 其相應(yīng)的關(guān)鍵字為 （ K1， K2 … Kn） 。 例如在實(shí)際問(wèn)題的數(shù)據(jù)處理中常會(huì)遇到這樣的情況 ， 需要把若干名字如人名 、 地名 、 國(guó)名 、 書名 、 校名 、 物名等按字母順序列表；需要把若干數(shù)值如各種考試分?jǐn)?shù) 、 田賽的長(zhǎng)度 、 徑賽的時(shí)間等按成績(jī)次序排名；需要把若干不同屬性的記錄按照某種方法排列次序 …… 。 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡(jiǎn)介 排序的基本概念 ? 排序 是數(shù)據(jù)處理中的重要運(yùn)算 ， 其功能是將一組數(shù)據(jù)元素 （ 或記錄 ） 的任意序列 ， 經(jīng)重新排列整理成為按關(guān)鍵字值大小有序的序列 。 ?在現(xiàn)今的計(jì)算機(jī)系統(tǒng)中 ， 有相當(dāng)大的一部分 CPU時(shí)間開銷是用于對(duì)數(shù)據(jù)的排序整理上的 。而對(duì)于無(wú)序表只能進(jìn)行順序檢索 ， 其平均檢索長(zhǎng)度為 (n+1)/2。算法與數(shù)據(jù)結(jié)構(gòu) 第 8章 排序及基本算法 排序及基本算法 ?為了便于檢索 ， 人們通常希望能在計(jì)算機(jī)中保存的數(shù)據(jù)是按關(guān)鍵字值大小排列的有序表 。 ?這是因?yàn)閷?duì)于有序表可以采用檢索效率較高的二分法檢索算法 ， 其平均檢索長(zhǎng)度為 log2(n+1)1。 ?又如為了方便檢索 ， 需要構(gòu)造二叉檢索樹 、 B樹和 B+樹等樹表 ， 構(gòu)造這些樹表的過(guò)程本身就是一個(gè)排序的過(guò)程 。 ?因此 ， 學(xué)習(xí)和研究各種排序算法 ， 分析并設(shè)計(jì)出高效適用的排序算法 ， 是擺在計(jì)算機(jī)科學(xué)工作者面前的重要課題之一 。 ? 排序的實(shí)際應(yīng)用領(lǐng)域也是非常廣泛的 。 所有這些都是排序問(wèn)題 ， 都需要把一組數(shù)據(jù)元素或記錄按照某種特定的次序排列起來(lái) 。 ?排序 （ sort） 是這樣一種操作 ， 它確定文件中 n個(gè)記錄的一種排列 （ Rj1， Rj2 … Rjn） ， 使得其相應(yīng)關(guān)鍵字滿足遞增 （ 即不減 ） 關(guān)系 Kj1≤Kj2≤… ≤Kjn或遞減 （ 即不增 ） 關(guān)系 Kj1≥Kj2≥… ≥Kjn。 排序的基本概念（續(xù)） ?在前面定義中 ， 關(guān)鍵字 Ki(i=1， 2 … n)稱作 排序碼 （ sort code） 。 ?當(dāng)排序碼是主關(guān)鍵字時(shí) ， 由于主關(guān)鍵字可以惟一標(biāo)識(shí)一個(gè)記錄 ， 所以排序結(jié)果是惟一的 。 排序的基本概念（續(xù)） ?若相同關(guān)鍵字值的記錄在排序前后的相對(duì)位置不會(huì)發(fā)生改變 ， 即若 Ri與 Rj的關(guān)鍵字相同 （ Ki=Kj） 且在排序前 Ri在 Rj之前 ， 排序后的 Ri仍在 Rj之前 ， 則稱所用的排序算法是 穩(wěn)定的 (stable)； ?否則 ， 若排序前后相同關(guān)鍵字值的記錄其相對(duì)位置可能發(fā)生改變 ， 即排序之后的序列中有可能出現(xiàn) Rj在 Ri之前的情況 ， 則稱所用的排序算法是 不穩(wěn)定的 。 排序的分類 ?根據(jù)排序過(guò)程中待排序文件存放的位置不同 ， 可以把排序分為 內(nèi)部 和 外部排序 兩大類 。 排序的分類（續(xù)） ?按排序中所用策略的不同： ?內(nèi)部排序通常可以分為插入排序 、 選擇排序 、交換排序 、 歸并排序和分配排序這五類 ， 每一類中不同的排序算法都是基于同一策略的不同方法 。 內(nèi)部排序文件的組織形式 ? 每種內(nèi)部排序方法均可在不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn) 。 排序的基本概念（續(xù)） ?排序的方法很多 ， 每一種方法都有自己的優(yōu)缺點(diǎn) ，適用于在不同的環(huán)境下使用 ， 很難說(shuō)哪一種方法是最好的方法 。 ?內(nèi)部排序的時(shí)間代價(jià)主要用關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)來(lái)衡量； ?而外部排序的時(shí)間代價(jià)主要用訪問(wèn)外存儲(chǔ)器的次數(shù)來(lái)衡量 。 ?待排序文件中記錄結(jié)構(gòu)類型定義如下： typedef struct {int key。 /*其它域 */ }recordtype /*記錄類型標(biāo)識(shí)符 */ 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡(jiǎn)介 插入排序 ?插入排序 的基本方法是：每次將一個(gè)待排序的記錄 Ri， 按其關(guān)鍵字 Ki的大小插入到前面已經(jīng)排好序的部分文件中的適當(dāng)位置 ， 直到全部記錄插完整個(gè)文件已排好序?yàn)橹?。 插入排序 直接插入排序 希爾排序 其它插入排序簡(jiǎn)介 直接插入排序 ?直接插入排序 （ straight insertion sort） 是一種最簡(jiǎn)單的排序方法 。 ?一開始 ， 第一個(gè)記錄是一個(gè)長(zhǎng)度為 1的有序序列； ?從第二個(gè)記錄起 ， 每次用第 i(i=2， 3 … n)個(gè)記錄的關(guān)鍵字 Ki與前面有序序列中記錄的關(guān)鍵字 Ki Ki2 … K1進(jìn)行比較 ， 從而找到 Ki所在記錄應(yīng)該插入的位置并依次后移各記錄后插入之 ， 使得有序序列的長(zhǎng)度加 1； ?這樣插入 n1次就會(huì)得到 n個(gè)記錄的有序序列 ， 從而完成整個(gè)文件的排序工作 。 直接插入排序（續(xù)） ? 在插入第 i個(gè)記錄時(shí) ， 用 Ki和前面已排好序記錄的關(guān)鍵字比較 ， 若 Ki小則后移一個(gè)記錄 ， 直到 Ki不小于時(shí)插入位置找到了 ， 直接插入 Ki完成第 i個(gè)記錄的插入 。 ?設(shè)置 監(jiān)視哨 是一種程序設(shè)計(jì)技巧 ， 既使程序控制簡(jiǎn)單 ， 又節(jié)省了測(cè)試時(shí)間提高了檢索效率 。 for(i=2。i++) {R[0]=R[i]。 while(R[0].key R[j].key) {R[j+1] = R[j]。 } R[j+1]=R[0]。 ?算法中的主要時(shí)間開銷在于關(guān)鍵字的比較和記錄的后移操作上 。 直接插入排序的算法分析 (續(xù) ) ?在最壞的情況下是待排序文件中各記錄為關(guān)鍵字的逆序排列 （ 即遞減序列 ） ， 每一趟中需要和前面已排好序的 i1個(gè)記錄以及監(jiān)視哨中 R[0]進(jìn)行關(guān)鍵字值的比較 ， 即第 i趟中需進(jìn)行 i次比較操作； ?向后移動(dòng)次數(shù)為 i1次 ， 加上與監(jiān)視哨之間的兩次移 動(dòng) ， 第 i趟需要移動(dòng)記錄 i+1次；總的比較次數(shù)為 次 ， 總的移動(dòng)次數(shù)為 次 ， 算法的時(shí)間復(fù)雜度為 O(n2)。 ?由于直接插入排序在整個(gè)排序過(guò)程中只需一個(gè)記錄的輔助空間 （ 即 R[0]） ， 所以其空間復(fù)雜度為 O(1)。 插入排序 直接插入排序 希爾排序 其它插入排序簡(jiǎn)介 希爾排序 ?希爾排