【正文】 int i, j, k。 ?兩個有序表的歸并稱為二路歸并。 ?堆排序是不穩(wěn)定的。對 n個元素，樹的深度 k=?log2n? +1，篩選算法中關(guān)鍵字的比較次數(shù)最多為 2（ k1），共調(diào)用了 n1次，所以總的比較次數(shù)小于 2n（ ?log2n?）次；在建初始堆時，因為第 h（ 1≤h≤k1）層最多有 2h1個元素，而每一個元素的最大調(diào)整次數(shù)為 kh，故總的調(diào)整次數(shù)不大于 4n。 /*堆頂元素和最后一個 sift (r, 1, i1)。 i1。 i) sift (r, i, n)。 for (i=n/2。 ?把一個 n個元素的無序序列看成一棵完全二叉樹，則最后一個內(nèi)部結(jié)點的下標(biāo)是 ?n/2? .因此，只需從第 ?n/2? 個元素開始，直到第 1個元素，依次調(diào)用 sift, 即可建成一個堆。 /*x不大于左右兒子 ， 即已找到 } /*了合適的位置 i， 循環(huán)結(jié)束 r[i]=x。 /*左右兒子中較小者上移 ， i=j。 r[j].keyr[j+1].key)) j++。 /*堆 ， 現(xiàn)要調(diào)整 R[i]， 使整個序列 while (j=m) /*R[i： m]成為一個堆 { if ((jm amp。 例： void sift (r[], i, m) /*把 R[i： m]看成完全二叉樹 ， 以 { j=2*i。 ?實現(xiàn)堆排序需要解決兩個問題： 1. 把一組待排序的元素構(gòu)建成堆； 2. 輸出堆頂后 , 如何將剩下的 n1個元素 調(diào)整成一個新的堆 . 先介紹第 2個問題 設(shè)堆頂輸出后，以堆的最后一個元素代替之，此時的左子樹、右子樹都是堆，則只需自上而下地調(diào)整即可。根據(jù)順序表示二叉樹的特點，除下標(biāo)為 1的結(jié)點 (根結(jié)點 )沒有父結(jié)點以外，其余下標(biāo)為 j 的結(jié)點（ 2≤j≤n）都有父結(jié)點，父結(jié)點的下標(biāo)為 i= 。 ?由于堆是完全二叉樹，采用將結(jié)點順序編號存入一維數(shù)組中的表示法比鏈接表示法節(jié)省存儲空間，也便于計算。 返回 堆排序 ?堆的概念 ?堆排序（ Heap Sort）是利用二叉樹的一種排序方法。 ?快速排序更偏愛一個“ 雜亂無章 ”的序列。 1969年，辛格爾頓就遵循了這一建議，采用R[1].key, R[n].key, R[n/2].key的中間值，故稱作“三者取中”法。在所有已發(fā)表的排序算法中，該算法是研究最深的。 Quicksort(r, k+1, hig)。 If(lowhig) { k=quickonepass(r, low, hig)。 return(i)。 } } while (ij)。 if (ij) /*已找到了滿足 r[i].keyx的 r[i] { r[j]=r[i]。amp。 /*r[j].keyx的 r[j] i++。 (ij)) j。 do { while( r[j].key= amp。 圖 一趟數(shù)據(jù)比較和互換 ( 13 ) 15 7 10 30 4 8 ( 25 ) ( 13 ) 15 7 10 30 4 ( 8) 25 8 ( 15 ) 7 10 30 4 ( 13 ) 25 8 ( 13 ) 7 10 30 ( 4) 15 25 8 4 ( 7) 10 30 ( 13 ) 15 25 8 4 7 ( 10 ) 30 ( 13 ) 15 25 8 4 7 10 ( 30 ) ( 13 ) 15 25 8 4 7 10 ( 13 ) 30 15 25 一趟快速排序 void quickOnePass ( r[ ], low, hig) { i=low, j=hig。 ?圖中括號中的數(shù)據(jù)表示正進行比較的兩個數(shù)據(jù)，左面一個的下標(biāo)為 i，右面一個的下標(biāo)為j。 i先不動使 j逐步前移，每次對二者所指的數(shù)據(jù)進行比較，當(dāng)遇到 r[i]大于 r[j]的情況時，就將二者對調(diào)位置；然后令 j固定使 i逐步后移做數(shù)據(jù)比較，當(dāng)遇到 r[i]大于 r[j] 時，又進行位置對調(diào)；然后又是 i不動使 j前移作數(shù)據(jù)比較； …… ； ?如此反復(fù)進行，直至 i與 j兩者相遇為止。 圖 快速排序 [ 13 15 7 10 30 4 8 25 ] [ 8 4 7 10] 13 [ 30 15 25 ] [ 7 4 ] 8 [ 10] 13 [ 30 15 25 ] 4 7 8 10 13 [ 30 15 25 ] 4 7 8 10 13 [ 25 15] 30 4 7 8 10 13 15 25 30 ?一趟快速排序采用從兩頭向中間掃描的辦法。依此遞歸地做下去，直至每個小部分中的數(shù)據(jù)個數(shù)為 1時，排序過程就結(jié)束了。 ?基本思想：在待排序的 n個數(shù)據(jù)中任取一個數(shù)據(jù)（通常取第一個數(shù)據(jù)），把該數(shù)據(jù)和文件中的所有記錄比較，所有比該數(shù)據(jù)小的放置在前一部分，所有比它大的放置在后一部分，即該數(shù)據(jù)排在這兩部分的中間。 ?希爾排序是不穩(wěn)定的。 } } ?文件的分割不是簡單地“逐段分割”，而是將相隔某個“增量”的記錄組成一個子文件，這樣可以使元素 跳躍式地移動 ；每個子文件中的元素個數(shù)不必相等。 k=kd。amp。 k=id。 for (i=d+1, i=n。 i++) shellpass(r[], n, dk[i])。 ?例： 9 13 8 2 5 13 7 1 4 11 希爾排序算法 Void shellsort (r[], n, dk[], t) /*dk[]增量數(shù)組 /*t:增量數(shù)組的元素數(shù) { for (i=1。 希爾排序 ?希爾（ Shell Sort)又稱“縮小增量排序”，它也時一種插入排序類的方法。 直接插入排序 和 簡單選擇排序 的比較 ?直接插入 1. 輸入序列是未知的； 2. 排序結(jié)束之前，不能確定任何元素的 最終位置。 ?簡單選擇排序簡單并且容易實現(xiàn)，適宜于 n較小的情況。 if ( i!=k) r[i] ? r[k]。 j=n。 i++) { k=i。 for (i=1。這樣掃描 n1次，處理元素的個數(shù)從 n逐次減 1。 ?在每一趟掃描時，用一個整型變量 i 跟蹤當(dāng)前最小元素的位置。 冒泡排序算法分析 ?最好情況： 比較次數(shù)： n1 交換次數(shù)： 0 ?最壞情況