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