【正文】 方法為：若各元素在數(shù)組中的序號(hào)為 1~n， 則對(duì)序號(hào)為 i的結(jié)點(diǎn) ， 它的父親的序號(hào)為 [i/2]， 它的左兒的序號(hào)為 2i（ 當(dāng) 2in時(shí)無(wú)左兒 ） ， 它的右兒的序號(hào)為 2i+1（ 當(dāng) 2i+1n時(shí)無(wú)右兒 ） 。 圖 111給出一個(gè)堆和它的數(shù)組存儲(chǔ)的例子 。 那么 ， 如何存儲(chǔ)堆結(jié)構(gòu) （ 順序二叉樹(shù) ） 呢 ？ 根據(jù)我們?cè)?“ 樹(shù)形結(jié)構(gòu) ” 一章中的介紹 ， 最簡(jiǎn)單的方法是 ， 按順序二叉樹(shù)的順序存儲(chǔ) ， 即將樹(shù)中各元素 ， 按從上到下 （ 從根的方向到葉子方向 ） ， 同層中從左到右的次序 ， 存儲(chǔ)在一維數(shù)組中 。 堆 ：若某堆結(jié)構(gòu)中 ， 每個(gè)結(jié)點(diǎn)的值均小于它的兩個(gè)兒子的值 ，則稱該堆結(jié)構(gòu)為堆 。 首先給出幾個(gè)概念 。 如果專門(mén)設(shè)立樹(shù) ， 則造成存儲(chǔ)浪費(fèi) 。 在選擇出最小鍵值后 ， 將其輸出 ， 然后 ， 再在剩余的樹(shù)結(jié)點(diǎn)中 ，按類似的方法選擇最小者 ， 這樣 ， 一共經(jīng)過(guò) n1選擇 ， 就將全部記錄按升序輸出了 。 樹(shù)中的 n個(gè)葉子代表待排序記錄的鍵值 。如此重復(fù)，直至選出最小鍵值的記錄為止。樹(shù)形選擇排序可以克服這一缺點(diǎn)，它的基本思想是：首先對(duì) n個(gè)記錄的鍵值進(jìn)行兩兩比較。需進(jìn)行 n2次比較，等等。 堆排序 (一 ) 基本思想 對(duì)直接選擇排序來(lái)說(shuō)，為了從 n個(gè)鍵值中找出最小的，需要進(jìn)行 n1次比較。 例如 ， 對(duì)具有初始輸入序列 8， 4， 3， 6， 9， 2，7的記錄 ， 采用直接選擇排序進(jìn)行排序 ， 過(guò)程如下 （ 方拓號(hào)表示無(wú)序區(qū) ） ： [8 4 3 6 9 2 7] 2 [4 3 6 9 8 7] 2 3 [4 6 9 8 7] 2 3 4 [6 9 8 7] 2 3 4 6 [9 8 7] 2 3 4 6 7 [8 9] 2 3 4 6 7 8 [9] 該選擇排序算法主要部分是兩層嵌套的 for循環(huán) ，顯然其時(shí)間復(fù)雜性為 O（ n2） 。 //交換 a[k]=a[i]。 j++) if (a[k]a[j]) k = j。 //將 k做為一面 “ 旗幟 ” ， 指向當(dāng)前掃描發(fā)現(xiàn)的最小記錄 for (j=i+1。 in1。至此，所有記錄都按升序排列了。 167。 167。這里， n為待排序的數(shù)據(jù)元素個(gè)數(shù)。另外，該算法對(duì)于較大的數(shù)據(jù)集效果明顯。但在最壞情況下，即對(duì)幾乎是排序好的輸入序列，該算法的效率很低，近似于 O（ n2）。 可以證明，快速排序平均比較次數(shù)是 O（ nlog2n）。方括號(hào)表示無(wú)序區(qū)。 } 下面給出利用上面的非遞歸快速排序程序進(jìn)行排序的過(guò)程。 } i = p+1。 top++。 } else {//后部較小，前部進(jìn)棧，下次先分割后部 if (p1i) //如果待進(jìn)棧的部分元素個(gè)數(shù)不足 2， 則不進(jìn)棧 {top++。 s[top] = j。 s[top] = p+1。 //分割 a[i]~a[j], 返回分 割點(diǎn)到 p中。每次都是將 [i,j]一分為三，前后兩部分中較大者進(jìn)棧待分割， //較小部分繼續(xù)在下次循環(huán)中分割，而分割點(diǎn)的位置已排好，不需再調(diào)整。 top。top。 s[top]=p2。 s[top]=p1。 top=0。實(shí)際申請(qǐng)量可以 是 log2(2*(p2p1+1))。 s=new long[2*(p2p1+1)]。 long SortQuick2(int a[], long p1, long p2) {//對(duì) a[p1]~a[p2]中元素排序 long *s, top。那么 ， 待分割部分 （ 的界限 ） 如何保存呢 ？ 為簡(jiǎn)單 ， 可以保存在一個(gè)棧中 。 由于每次只能分割一部分 ， 所以就需要將另一待分割的部分的界限保存起來(lái) ， 當(dāng)當(dāng)前分割的部分被分割完后 ， 再分割這部分 。 } 為了寫(xiě)出非遞歸算法 ， 我們先分析一下快速排序的過(guò)程 。 return p2p1+1。 SortQuick(a, p1, p1)。 long SortQuick(ing a[], long p1, long p2) {// 對(duì) a[p1]~a[p2]中元素排序 long p。 我們?cè)诘?2章中已介紹過(guò)分割算法 ， 給出了其實(shí)現(xiàn)函數(shù) long Partition (long a[], long p1, long p2) 其功能是對(duì) a[p1]~a[p2]進(jìn)行分割，返回分割點(diǎn)的序號(hào)。然后，對(duì)所分成的第一和第三組再分別重復(fù)上述方法，直到所有記錄都排在適當(dāng)位置為止。這個(gè)過(guò)程稱為一趟分割。 快速排序 * (一 ) 基本思想 快速排序（ Quick Sort）是交換排序的另一種，實(shí)際上它是冒泡排序的另一種改進(jìn)。特別地，若數(shù)據(jù)集已排好序，則該算法只需掃描一次數(shù)據(jù)集。 }//while return 0。 //記錄比較的位置 。 a[j+1] = t。 j++) if (a[j]a[j+1]) {t = a[j]。 for (j=0。 k=n1。 long SortBubble2(int a[], long n) {//將 a[0]~a[n1]中的數(shù)按升序排列 long k, j, kk。在冒泡比較中 ， 每交換一對(duì)元素 ， 就將這對(duì)元素的第一個(gè)的序號(hào) （ 設(shè)為 k） 記下 ， 當(dāng)一趟冒泡后 ， k就是該趟中最后一次的交換位置 ， 下趟比較的終點(diǎn)就可以設(shè)置為 k。 據(jù)此 ，我們可以通過(guò)控制冒泡次數(shù)改進(jìn)前面的冒泡算法 。 這表明 ， 序號(hào) 3以后的元素 ， 已經(jīng)排好序 ， 因此 ， 下趟冒泡的終點(diǎn)到 2號(hào)位置就可以了 。事實(shí)上，若在某一次冒泡中，從某個(gè)位置起，后面都未進(jìn)行過(guò)交換，則表明該位置后面的各元素已排好序。 167。 } return 0。 a[j] = a[j+1]。 ji。i0。 long i, j。 a[j+1] = t。 j++) if (a[j]a[j+1]) { t = a[j]。 i) 對(duì) a[0]—a[i]進(jìn)行冒泡 ； 進(jìn)一步地 ， “ a[0]—a[i]進(jìn)行冒泡 ” 的實(shí)現(xiàn)為： for (j=0。 接下來(lái) ， 進(jìn)行其他 (n2)趟冒泡 （ 只 寫(xiě)出每趟的結(jié)果 ） ： 10 20 25 22 30 45 50 55 //第 2趟 10 20 22 25 30 45 50 55 //第 3趟 10 20 22 25 30 45 50 55 //第 4趟 10 20 22 25 30 45 50 55 //第 5趟 10 20 22 25 30 45 50 55 //第 6趟 10 20 22 25 30 45 50 55 //第 7趟 10 20 22 25 30 45 50 55 //第 8趟 根據(jù)上面的討論 ， 冒泡排序的算法的框架為 （ 設(shè)元素在 a[0]~a[n1]中 ） ； for (i=n1。重復(fù)以上過(guò)程，每趟負(fù)責(zé)排好一個(gè)記錄，經(jīng) n1趟后 n個(gè)記錄中有n1個(gè)記錄被排好，相當(dāng)于全部 n個(gè)記錄排好。一趟冒泡后，鍵值最大的記錄傳到了第 n個(gè)位置。具體做法是：先將第 1個(gè)記錄的鍵值和第 1個(gè)記錄的鍵值進(jìn)行比較，如 a[0]＞ a[1]，則將兩個(gè)記錄交換。 167。 交換排序 這里的交換 ， 就是根據(jù)記錄集中兩個(gè)記錄鍵值的比較結(jié)果來(lái)對(duì)換這兩個(gè)記錄在序列中的位置 。例如，折半插入排序是每次將當(dāng)前待插入元素與第一部分的中點(diǎn)位置上的元素比較，這樣當(dāng)記錄數(shù)目很多時(shí)，可大大減少為尋找插入點(diǎn)而進(jìn)行的比較次數(shù)。它們是對(duì)直接插入排序的改進(jìn)。 167。 初始鍵值序 [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直接插入排序過(guò)程示例 顯然 ， 該算法是穩(wěn)定的 ， 且時(shí)間復(fù)雜性為 O（ n2） 。 } //for return 0。 j。amp。 j=i1。 in。 綜合起來(lái) ， 就得到插入排序的程序： int SortInsertion(int a[], long n) { int x, i,j。 //a[j]后移一位 j。amp。 j=i1。 in。 下面考慮插入排序的計(jì)算機(jī)程序?qū)崿F(xiàn) ?？傆幸淮危诙糠肿?yōu)榭?，則第一部分包含了所有的記錄，并且是有序的。初始時(shí)，任取一條記錄作為第一部分（一條記錄總是有序的） ,而其他記錄作為第二部分。 直接插入排序 直接插入排序（ straight insertion sort）是一種最簡(jiǎn)單的排序方法，它的基本思想是，將待排序的記錄集分成兩部分，第一部分已排好序，第二部分未排好序。插入排序的基本方法是：每步將一個(gè)待排序的記錄按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當(dāng)位置 ， 直到全部記錄插入完畢為止 。 167。為了突出主題，我們不失一般性地假定，待排序的記錄為一維數(shù)組 a[]，數(shù)組的每個(gè)元素是整數(shù)。評(píng)價(jià)排序的另一個(gè)主要標(biāo)準(zhǔn)是執(zhí)行算法所需的附加空間。當(dāng)鍵值是字串的時(shí)候，比較要占用較多的時(shí)間，是影響時(shí)間復(fù)雜性的主要因素。 為了比較各種排序算法的優(yōu)劣，要分析算法的時(shí)間復(fù)雜性。 不論那種無(wú)法 ， 多鍵排序都被轉(zhuǎn)化為了單鍵排序 ， 所以 ， 我們只討論單鍵排序的情況 。 這種方法要求各趟排序所用算法是穩(wěn)定的 。 首先按第一關(guān)鍵字排序 ， 對(duì)第一關(guān)鍵字相等的記錄 ， 按第二關(guān)鍵字排序 ， 而第二關(guān)鍵字也相等的記錄再按第三關(guān)鍵字排 ， 余類推 。 6． 多鍵排序 ：按多個(gè)關(guān)鍵字排序 。 外排序適用于記錄個(gè)數(shù)很多 ， 不能一次將其全部都放入內(nèi)存的大文件 。 內(nèi)排序適用于記錄個(gè)數(shù)不太多的小文件 ，同時(shí)也是外排序的基礎(chǔ) 。 按照排序過(guò)程涉及的存儲(chǔ)設(shè)備的不同 ， 排序分為內(nèi)排序（ internal sorting） 和外排序 （ external sorting） 兩大類 。 3． 排序的穩(wěn)定性： 假定在待排序的記錄集中 ， 存在多個(gè)具有相同鍵值的記錄 ， 若經(jīng)過(guò)排序 ， 這些記錄的相對(duì)次序仍然保持不變（ 即在原序列中 ki=kj， i＜ j；而在排序