【正文】 167。 二路歸并排序 167。 多段 2路合并 167。 二路合并 167。 堆排序 167。 直接選擇排序 167。 冒泡算法的改進 167。 快速排序 * 167。 冒泡排序 167。 167。 直接插入排序 167。 外排排簡介 167。 167。 選擇排序 167。 交換排序 167。 插入排序 167。 概述 第 11 章 排序算法 從操作角度看 ， 排序是線性結(jié)構(gòu)的一種操作 ， 在當(dāng)今的計算機系統(tǒng)中 ， 花費在排序上的時間占系統(tǒng) CPU運行時間的比重很大 。有資料表明 ， 在一些商用計算機上 ， 用在排序上的 CPU時間達(dá)到20%至 60%。 為了提高排序效率 ，人們已對排序進行了許多研究 ，提出了許多方法 /算法 。 從算法設(shè)計角度看 。 排序算法不僅對排序本身重要 ， 而且展示了算法設(shè)計的某些重要原則和高超的技巧 ，所以也是重要的算法設(shè)計方法 。因此 ， 對于計算機專業(yè)人員來說 ，認(rèn)真研究和掌握排序算法是十分重要的 。 167。 概述 排序 （ Sorting） （ 也稱整序 ） 通常被理解為按規(guī)定的原則重新安排一組給定的對象的的排列次序 。 排序的主要目的是便于以后在已排序的集合中查找 /檢索某一成員 。 日常生活中 ， 通過排序以便于檢索的例子屢見不鮮 。 例如 ， 電話號碼簿 、 目錄表 、 圖書館 、 詞典 、倉庫以及一切需對所存貯的對象進行檢索的地方都要先將對象加以排序 。 下面先介紹若干概念 。 1． 關(guān)鍵字 ：關(guān)鍵字形式上是記錄中的某個字段 （ 或某些字段的組合 ） ， 在具體的操作中 ， 用于代表其所在的記錄 。 對排序操作 ，是以關(guān)鍵字字段的內(nèi)容的大小進行排序的 。 記錄中關(guān)鍵字字段的值稱為鍵值 。 鍵值一般為數(shù)值或字符串 。 2． 排序 ：在數(shù)據(jù)結(jié)構(gòu)中 ， 排序被認(rèn)為是定義在數(shù)據(jù)集合上的一種運算 ， 其功能是將一組任意排列的數(shù)據(jù)元素 （ 在排序中稱為記錄 ） 重新排列成一個按鍵值有序的序列 。 具體地 ， 排序定義如下定義： 設(shè) ｛ R1， R2， … ， Rn｝ 為含 n個記錄的序列 ， 其相應(yīng)的鍵值序列為 ｛ k1， k2， … kn｝ 。 排序是將這些記錄重新排列為 ｛ Ri1，Ri2， … ， Rin｝ ， 使得相應(yīng)的鍵值滿足條件 ki1≤ ki2≤ … ≤ kin（ 升序 ） ， 或滿足 ki1≥ ki2≥ … ≥ kin（ 降序 ） 。 這里的比較運算 （ ≤ 或≥ ） ， 或是數(shù)值比較 ， 或是字符串比較 。 3． 排序的穩(wěn)定性： 假定在待排序的記錄集中 ， 存在多個具有相同鍵值的記錄 ， 若經(jīng)過排序 ， 這些記錄的相對次序仍然保持不變（ 即在原序列中 ki=kj， i＜ j；而在排序后的序列中 ， Ri 仍在 Rj之前 ） ， 則稱這種排序方法是 穩(wěn)定的 ， 否則稱為不穩(wěn)定的 。 4． 內(nèi)排序： 由于記錄的形式 、 數(shù)量和所存放的存儲設(shè)備不同 ， 排序所采用的方法也不同 。 按照排序過程涉及的存儲設(shè)備的不同 ， 排序分為內(nèi)排序（ internal sorting） 和外排序 （ external sorting） 兩大類 。 內(nèi)排序 是指在排序的整個過程中 ， 數(shù)據(jù)全部存放在計算機的內(nèi)存中 ， 排序所需所有操作只需在內(nèi)存中進行 ， 不需進行內(nèi)外存交換 。 內(nèi)排序適用于記錄個數(shù)不太多的小文件 ，同時也是外排序的基礎(chǔ) 。 5． 外排序 ：是指在排序過程中 ， 待排序的數(shù)據(jù)較多 ， 不能一次全部裝入內(nèi)存繼續(xù)排序 ， 需進行內(nèi)外存交換 （ 即讀入部分?jǐn)?shù)據(jù) ， 處理后寫回外存 ， 然后再讀入其他部分 ） 。 外排序適用于記錄個數(shù)很多 ， 不能一次將其全部都放入內(nèi)存的大文件 。 本章先集中討論內(nèi)排序的各種典型方法和算法 ， 最后再簡單介紹一下外排序 。 6． 多鍵排序 ：按多個關(guān)鍵字排序 。 這主要針對關(guān)鍵字值有重復(fù)的情況 。 首先按第一關(guān)鍵字排序 ， 對第一關(guān)鍵字相等的記錄 ， 按第二關(guān)鍵字排序 ， 而第二關(guān)鍵字也相等的記錄再按第三關(guān)鍵字排 ， 余類推 。 多鍵排序有兩種方式 （ 設(shè)第 1到第 n個關(guān)鍵字分別為 k1, k2, … , kn） ： a) 依次對記錄進行 n次排序 ， 第一次按 kn排序 ， 第二次按 kn1， … , 最后一次按 k1排 。 這種方法要求各趟排序所用算法是穩(wěn)定的 。 b) 先將關(guān)鍵字 k1, k2, … , kn分別視為字符串 ， 將它們依次首尾連接在一起 ， 形成一個字符串 ， 然后 ， 對記錄集按新形成的字符串排序 。 不論那種無法 ， 多鍵排序都被轉(zhuǎn)化為了單鍵排序 ， 所以 ， 我們只討論單鍵排序的情況 。 顯然 ， 方法 b)的速度要快于 a). 內(nèi)排序的方法很多，如果按排序過程中依據(jù)的不同原則對內(nèi)排序方法進行分類，則主要分為為：插入排序、交換排序、選擇排序、歸并排序等四類，另一類是分配排序。 為了比較各種排序算法的優(yōu)劣，要分析算法的時間復(fù)雜性。為此，通常只考慮鍵值的比較次數(shù)和記錄的移動次數(shù)，即以鍵值比較和記錄移動為標(biāo)準(zhǔn)操作。當(dāng)鍵值是字串的時候，比較要占用較多的時間，是影響時間復(fù)雜性的主要因素。而當(dāng)記錄很大時，為了交換記錄的位置，移動記錄也要占用較多的時間，是影響時間復(fù)雜性的另一個主要因素。評價排序的另一個主要標(biāo)準(zhǔn)是執(zhí)行算法所需的附加空間。 排序一般在記錄集上進行，也可以認(rèn)為是在線性結(jié)構(gòu)上進行。為了突出主題，我們不失一般性地假定，待排序的記錄為一維數(shù)組 a[]，數(shù)組的每個元素是整數(shù)。另外，如無特別說明，都假定是按升序排序。 167。 插入排序 插入排序類似玩紙牌時整理手中紙牌的過程 。插入排序的基本方法是：每步將一個待排序的記錄按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當(dāng)位置 ， 直到全部記錄插入完畢為止 。 167。 直接插入排序 直接插入排序（ straight insertion sort）是一種最簡單的排序方法，它的基本思想是，將待排序的記錄集分成兩部分，第一部分已排好序，第二部分未排好序。排序中，每次都是從第二部分中取出一條記錄，就將其插入到第一部分，并使其保持有序。初始時，任取一條記錄作為第一部分（一條記錄總是有序的） ,而其他記錄作為第二部分。顯然，隨著排序過程的進行，第一部分不斷擴大，第二部分不斷縮小?？傆幸淮?，第二部分變?yōu)榭眨瑒t第一部分包含了所有的記錄，并且是有序的。 圖 111給出了一個插入排序執(zhí)行過程的例子 。 下面考慮插入排序的計算機程序?qū)崿F(xiàn) 。 很自然地 ， 我們可以將插入排序粗略地描述為： SortInsertion(int a[], long n) { for (i=1。 in。 i++) 將 a[i]插入到 a[0]—a[i1]中 ， 并使其保持有序 } 至于 “ 將 a[i]插入到 a[0]—a[i1]中 ， 并使其保持有序 ” 的實現(xiàn) ， 可如下進行： x=a[i]。 j=i1。 while (j=0 amp。amp。 xa[j]) { a[j+1] = a[j]。 //a[j]后移一位 j。 } a[j+1] = x。 綜合起來 ， 就得到插入排序的程序： int SortInsertion(int a[], long n) { int x, i,j。 for (i=1。 in。 i++) { x=a[i]。 j=i1。 while (j=0 amp。amp。 xa[j]) { a[j+1] = a[j]。 j。 }//while a[j+1] = x。 } //for return 0。 } 如果為了提高 while循環(huán)的循環(huán)控制條件的判別速度 ， 可在while進行前 ， 將當(dāng)前待插入的元素 a[i]放在 a數(shù)組中的第一個元素位置 （ 代替語句 x=a[i]） ， 這樣 ， while控制條件中的“ j=0”就不需要了 ， 從而起到節(jié)省時間的作用 。 初始鍵值序 [46] 58 15 45 90 18 10 62 i=2 [46 58] 15 45 90 18 10 62 i=3 [15 46 58] 45 90 18 10 62 i=4 [15 45 46 58] 90 18 10 62 i=5 [15 45 46 58 90] 18 10 62 i=6 [15 18 45 46 58 90] 10 62 i=7 [10 15 18 45 46 58 90] 62 i=8 [10 15 18 45 46 58 62 90] 圖 111直接插入排序過程示例 顯然 ， 該算法是穩(wěn)定的 ， 且時間復(fù)雜性為 O（ n2） 。 從空間來看 ， 它只需要一個記錄的輔助空間 。 167。 除了直接插入排序外，還有其他形式的插入排序，如折半插入排序、表插入排序和希爾排序等。它們是對直接插入排序的改進。改進的關(guān)鍵點是，如何盡快地找到插入位置。例如，折半插入排序是每次將當(dāng)前待插入元素與第一部分的中點位置上的元素比較，這樣當(dāng)記錄數(shù)目很多時，可大大減少為尋找插入點而進行的比較次數(shù)。 167。 交換排序 這里的交換 ， 就是根據(jù)記錄集中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置 。 交換排序的特點是：將鍵值較大的記錄向記錄集的一端移動 ，鍵值較小的記錄向另一端移動 。 167。 冒泡排序 一個最簡單的交換排序方法是冒泡排序法（ bubble sort），它和氣泡從水中往上冒的情況有些類似。具體做法是：先將第 1個記錄的鍵值和第 1個記錄的鍵值進行比較，如 a[0]＞ a[1]，則將兩個記錄交換。然后比較第 2個和第 3個記錄的鍵值，依同樣的方法處理，接著同法處理第 3個和第 4個記錄，等等，直到第 n1個記錄和第 n個記錄進行比較交換，這稱為一趟冒泡。一趟冒泡后，鍵值最大的記錄傳到了第 n個位置。然后，對前 n1個記錄進行同樣操作，則具有第二大鍵值的記錄被安置在第 n1個位置上。重復(fù)以上過程，每趟負(fù)責(zé)排好一個記錄，經(jīng) n1趟后 n個記錄中有n1個記錄被排好，相當(dāng)于全部 n個記錄排好。 例如 ，