【正文】 [s]不滿足堆特性 ， 其它結(jié)點(diǎn)均滿足堆特性 ） 進(jìn)行篩選是至關(guān)重要的 。 i=s。(R[j].keyR[j+1].key)) j++。} else j=t+1。 for(i=n/2。i1。 heapadjust(R,1,i1)。 ?堆排序是一種 不穩(wěn)定的排序 方法 。 ?假設(shè)待排序文件中含有 n個(gè)記錄 ， 我們可以把它看作是 n個(gè)有序的子序列 ， 每個(gè)有序子序列的長度為 1；然后兩兩歸并得到個(gè)長度為 2（ 其中最后一個(gè)長度可能為 1） 的有序子序列；再兩兩歸并得到長度為 4的若干有序子序列 …… 如此這樣反復(fù)歸并 ， 直到得到一個(gè)長度為 n的有序序列時(shí)為止 。 歸并排序 歸并相鄰兩個(gè)有序序列 二路歸并排序的遞歸算法 二路歸并排序的非遞歸算法 歸并相鄰兩個(gè)有序序列 ?在前面分析的基礎(chǔ)上 ， 歸并相鄰兩個(gè)有序序列為一個(gè)有序序列的算法 merge可描述如下： void merge(recordtype R[],int L,int m,int h,recordtype R1[]) {int i,j,k。 /*k指向結(jié)果有序序列的第一個(gè)位置 */ while((i=m)amp。 歸并相鄰兩個(gè)有序序列（續(xù)） while(i=m) R1[k++]=R[i++]。 歸并排序 歸并相鄰兩個(gè)有序序列 二路歸并排序的遞歸算法 二路歸并排序的非遞歸算法 二路歸并排序的遞歸算法 ? 在前述算法 merge的基礎(chǔ)上 ， 可給出二路歸并排序的 遞歸算法 如下： void mergesortrecalg(recordtype R[],intL,int h,recordtype R1[]) {int m。 mergesortrecalg(R,m+1,h,R1)。 ?設(shè) R[1..n]中的有序子序列長度為 len， 只有最后一個(gè)有序子序列的長度有可能小于 len， 進(jìn)行兩兩有序的子序列歸并后的結(jié)果依次存放在 R1[1..n]中 。 i=i+2*len。 } } /*mergepass end*/ 二路歸并排序的非遞歸算法 (續(xù) ) ? 在一趟歸并排序的基礎(chǔ)上 ， 可以很方便地得到二路歸并排序的非遞歸算法如下： void mergesort(recordtype R[],int n) {int len=1。 mergepass(R1,len,n,R)。 ?二路歸并排序是一種 穩(wěn)定的排序 方法 。 ?撲克牌有兩個(gè)關(guān)鍵字 ， 即花色和點(diǎn)力；其次序定義為 花色：梅花 方塊 紅桃 黑桃 點(diǎn)力： 2345678910JQKA ?并且花色的優(yōu)先級別高于點(diǎn)力 ， 即高一級花色的最小點(diǎn)力 2大于低一級花色的最大點(diǎn)力 A。 多關(guān)鍵字排序（續(xù)） ?前面兩種理牌的方法便是兩種多關(guān)鍵字排序的方法 。 多關(guān)鍵字排序（續(xù)） ⑵ 是 低位優(yōu)先法 （ least significant digit first） ， 簡稱 LSD法 。 基數(shù)排序 多關(guān)鍵字排序 鏈?zhǔn)交鶖?shù)排序 鏈?zhǔn)交鶖?shù)排序 ?基數(shù)排序 就是按照 LSD法 ， 對待排序文件中各記錄用單邏輯關(guān)鍵字進(jìn)行分配和收集的一種排序方法 。 鏈?zhǔn)交鶖?shù)排序（續(xù)） ? 排序前先把待排序文件中各記錄置于單鏈表中 ， 單鏈表可用一維數(shù)組 R[1..n]存儲(chǔ)的靜態(tài)鏈表實(shí)現(xiàn) ， 每個(gè)結(jié)點(diǎn)除關(guān)鍵字域和數(shù)據(jù)域外 ， 還須有一個(gè)指向下一個(gè)結(jié)點(diǎn)的指針域 。 ?文件的初始狀態(tài)是一個(gè)單鏈表 ， 表頭指針指向第一個(gè)記錄 ，如下圖 (a)所示； ?第一趟分配按最低關(guān)鍵字位 （ 個(gè)位數(shù) ） 進(jìn)行 ， 改變記錄結(jié)點(diǎn)的指針值將文件中的所有記錄分配到 10個(gè)隊(duì)列中去 ， 每個(gè)隊(duì)列中記錄的關(guān)鍵字的個(gè)位數(shù)均相等 ， 如下圖 (b)所示； 鏈?zhǔn)交鶖?shù)排序舉例（續(xù)） ?第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄結(jié)點(diǎn)的指針域值 ， 使其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄結(jié)點(diǎn) ，重新將 10個(gè)隊(duì)列中的記錄鏈接成一個(gè)單鏈表 ， 如下圖(c)所示； ?第二趟的分配和收集以及第三趟的分配和收集 ， 是分別針對關(guān)鍵字中的十位數(shù)和百位數(shù)進(jìn)行的 ， 其分配和收集過程與個(gè)位數(shù)時(shí)相同 ， 分別如下圖 (d)~(g)所示 。 typedef struct {int key[d]。 reodetype R[n]。 p=0。jrd。 else R[e[k]].next=p。 while(f[j]==1) j++。 if(f[j]!=1) {R[t].next=f[j]。 } /*radixsort end*/ 鏈?zhǔn)交鶖?shù)排序的算法分析 ?在該算法中 ， 外層循環(huán)控制 d趟分配和收集 ， 時(shí)間復(fù)雜度為O(d)； ?內(nèi)層四個(gè)并列的循環(huán) ， for循環(huán)進(jìn)行隊(duì)列的隊(duì)頭指針初始化 ，時(shí)間復(fù)雜度為 O(rd。 } } R[t].next=1。 t=e[j]。 p=R[p].next。 鏈?zhǔn)交鶖?shù)排序的算法描述（續(xù)） while(p!=1) {k=R[p].key[i]。i=1。 鏈?zhǔn)交鶖?shù)排序的算法描述 ?算法中待排序文件在 R[0..n1]中以靜態(tài)鏈表方式存儲(chǔ) ， 第一個(gè)結(jié)點(diǎn)為 R[0]； f[0..9]和 e[0..9]分別為 rd個(gè)隊(duì)頭和隊(duì)尾指針數(shù)組 ， P始終指向待排序文件單鏈表的第一個(gè)結(jié)點(diǎn) ， 在經(jīng)過 d趟分配和收集后 ， 返回指向排序結(jié)果單鏈表的第一個(gè)結(jié)點(diǎn)的指針值 P。 int next。 鏈?zhǔn)交鶖?shù)排序舉例（續(xù)） 鏈?zhǔn)交鶖?shù)排序舉例（續(xù)） 鏈?zhǔn)交鶖?shù)排序舉例（續(xù)） 鏈?zhǔn)交鶖?shù)排序算法的數(shù)據(jù)定義 ?為了描述這種鏈?zhǔn)交鶖?shù)排序的算法 ， 我們先給出數(shù)據(jù)定義如下： define rd 10。 鏈?zhǔn)交鶖?shù)排序舉例 ?為了簡化說明過程 ， 對每個(gè)記錄結(jié)點(diǎn)只考慮關(guān)鍵字和指針域 。 基數(shù)的選擇和關(guān)鍵字位的分解因關(guān)鍵字的類型而異 。 多關(guān)鍵字排序（續(xù)） ?顯然前述的撲克牌排序中 ， ?第一種理排過程采用的是 最高位優(yōu)先法 （ MSD法 ） ， ?而第二種理牌過程是采用 最低位優(yōu)先法 （ LSD法 ） 。 多關(guān)鍵字排序（續(xù)） ? 多關(guān)鍵字排序的方法通常有兩種： ⑴ 最高位優(yōu)先法 （ most significant digit first） ， 簡稱 MSD法 。 多關(guān)鍵字排序（續(xù)） ? 如果要根據(jù)上述關(guān)系把一幅撲克牌整理為升序次序 ， 即梅花 梅花 3 … 梅花 A、 方塊 2 … 方塊 A、紅桃 2 … 紅桃 A、 黑桃 2 … 黑桃 A的次序 ， 通常有如下兩種整理方法： ?先按花色分成四堆 ， 然后再按點(diǎn)力把每堆整理有序 ， 最后按花色由低級花色到高級花色疊加在一起 。 ?基數(shù)排序 （ radix sort） 方法則不同 ， 它不用進(jìn)行關(guān)鍵字值的大小比較 ， 而是借助于多關(guān)鍵字排序的思想 ， 通過 對待排序記錄按單邏輯關(guān)鍵字進(jìn)行分配和收集來實(shí)現(xiàn) 的一種排序方法 。 } }/*mergesort end*/ 二路歸并排序的算法分析 ?如果把待排序文件 R中的 n個(gè)記錄看作葉子結(jié)點(diǎn) ， 把兩兩歸并得到的有序子序列看成是兩個(gè)歸并對象有序子序列的雙親結(jié)點(diǎn) ， 則歸并過程對應(yīng)由葉向根生成一棵二叉樹的過程 ， 所以歸并排序的趟數(shù)為 ； ?而每趟歸并需移動(dòng)記錄 n次 （ 關(guān)鍵字比較約 n次 ） ， 由乘法準(zhǔn)則知二路歸并排序的時(shí)間復(fù)雜度為 O(nlog2n)。 while(lenn) {mergepass(R,len,n,R1)。 else while(i=n) {R1[i]=R[i]。 二路歸并排序的非遞歸算法 (續(xù) ) ?一趟歸并排序算法可描述如下： void mergepass(recordtype R[],int len,int n,recordtype R1[]) {int i=1。 } } /*mergesortrecalg end*/ ?對待排序文件 R[1..n]中的 n個(gè)記錄排序 ， 只須用參數(shù) R、 n調(diào)用該遞歸算法 ， 即 mergesortrecalg(R,1,n,R1)即可 。 else {m=(L+h)/2。 }/*merge end*/ ?需要注意的是 ， 在由 R中傳送記錄到 R1中的同時(shí) ， 指示器變量 i（ 或 j） 與 k也自增值 1后指向下一個(gè)記錄位置 。(j=h)) if(R[i].keyR[j].key) R1[k++]=R[i++]。 /*i指向第一個(gè)有序子序列的第一個(gè)記錄 */ j=m+1。 歸并排序舉例 ?例如 ， 對于待排序文件的關(guān)鍵字序列 （ 22， 36， 06， 78，25， 43， 73， 18， 39， 62， 27， 66， 13） ， 利用二路歸并排序的過程如下： 歸并排序舉例 ? 由上述歸并排序過程可以看出 ， 二路歸并 的主要操作是把相鄰兩個(gè)有序序列歸并成為一個(gè)有序序列；對于 n個(gè)記錄的待排序文件 ， 需要?dú)w并趟才能完成排序；每趟歸并使有序子序列的長度增加一倍 ， 而使有序子序列的個(gè)數(shù)減少約一半 。 第 8章 排序及基本算法 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較和選擇 外部排序簡介 歸并排序 ?歸并排序 （ merge sort） 的 基本思想 是： ?將一些已排序的子文件進(jìn)行合并而得到一個(gè)完整的有序文件 。 所以在建好堆后 ， 排序過程的 n1次篩選中的比較次數(shù)不會(huì)超過下式的值： ?而在建立初始堆時(shí)的比較次數(shù)不會(huì)超過 4n次 ， 因此堆排序在最壞情況下的時(shí)間復(fù)雜度為 O(nlog2n)。 R[1]=R[i]。i) heapadjust(R,i,n)。 } /*heapadjust end*/ 堆排序的算法描述 ?有了上述調(diào)整堆的篩選算法 ， 就可以很方便地設(shè)計(jì)完整的堆排序算法如下： void heapsort(recordtype R[],int n) {int i。 i=j。 while(j=t) {if((jt)amp。 recordtype temp。 ?反復(fù)重復(fù)以上過程 ， 即可實(shí)現(xiàn)上例所給關(guān)鍵字序列所對應(yīng)的待排序文件的堆排序 ， 其堆排序過程如下圖所示 。 ?例如 對上例所給的關(guān)鍵字序列 ， 經(jīng)初始建堆后得到圖 (a)所示的堆 ， 同時(shí)得到堆頂?shù)淖钚￡P(guān)鍵字 11所在的記錄； ?然后輸出堆頂記錄 （ key=11） 并用最后一個(gè)記錄 （ key=82）替代堆頂 ， 如圖 (b)所示 。 建初始堆（最小根堆）過程舉例 ?下圖給出了完全二叉樹表示的一組關(guān)鍵字值建初始堆的示例 ， 所用關(guān)鍵字序列為 （ 47， 33， 61，82， 72， 11， 25， ） ；由于 n=8， 故從第 4個(gè)結(jié)點(diǎn)開始進(jìn)行調(diào)整 。 在 1964年弗洛伊德（ Floyd） 提出了 篩選法 ， 其具體方法是 ?將待排序記錄的關(guān)鍵字分放到一棵完全二叉樹的各個(gè)結(jié)點(diǎn)中 ， 此時(shí)的完全二叉樹一般不具備堆的特性 。 堆排序舉例 ?例如關(guān)鍵字序列 （ 12， 15， 35， 25， 39， 67） 和序列 （ 75， 38， 62， 28， 18， 49） 都是堆 ， 前者是最小值根堆而后者是最大值根堆 ， 其對應(yīng)的完全二叉樹分別如下圖的 (a)和 (b)所示 。 選擇排序 直接選擇排序 樹形選擇排序 堆排序 堆排序 ?為了克服樹形選擇排序需要較多輔助空間保存比較結(jié)果和與進(jìn)行多余比較的缺點(diǎn)； ?在 1964年威洛姆斯 （ ） 和弗洛伊德（ Floyd） 對樹形選擇排序進(jìn)行了改進(jìn) ， 提出了新的排序方法 ——堆排序 （ heap sort） 方法 ， 使其比較次數(shù)達(dá)到樹形選擇排序的水平 ， 同時(shí)又不會(huì)增加額外的存儲(chǔ)開銷 ， 只需一個(gè)記錄大小的空間用于記錄間的交換 。 接下來將最小關(guān)鍵字值改為 ， 然后沿該結(jié)點(diǎn)到樹根的路徑依次進(jìn)