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