天津科技大學(xué)數(shù)據(jù)結(jié)構(gòu)排序-資料下載頁(yè)
2024-10-19 15:10本頁(yè)面
【正文】 [j].key) R1[k++]=R[i++]。 else R1[k++]=R[j++]。 while (i=mid) R1[k++]=R[i++]。 while (j=high) R1[k++]=R[j++]。 } 歸并排序算法 MERGESORT(rectype R[]){ int length=1。 while (lengthn){ MERGEPASS(R,R1,length)。 length=2*length。 MERGEPASS(R1,R,length)。 length=2*length。 } } 算法復(fù)雜性分析 歸并排序在第 i 趟歸并后，有序子文件長(zhǎng)度為 2i，因此，因此，對(duì)于具有 n個(gè)記錄的序列來(lái)說(shuō)，必須做 high(log2n)趟歸并，每趟歸并所花的時(shí)間為 O(n)。所以，二路歸并排序算法的時(shí)間復(fù)雜度為 O(nlog2n)，輔助數(shù)組所需的空間為 O(n)。 歸并排序是穩(wěn)定的排序方法。 六、基數(shù)排序 基本原理，采用“分配”和“收集”的辦法，用對(duì)多關(guān)鍵字進(jìn)行排序的思想實(shí)現(xiàn)對(duì)單關(guān)鍵字進(jìn)行排序的方法。 下面先介紹多關(guān)鍵字排序 多關(guān)鍵字排序方法示例 如對(duì)撲克牌的排序 每張撲克牌有兩個(gè)“關(guān)鍵字”：花色和面值它們之間有次序的優(yōu)先。 對(duì)以上排序，可以先對(duì)花色排序，或先對(duì)面值排序。 多關(guān)鍵字有序的概念 考慮對(duì)象序列 {V0,V1,..., Vn1}，每個(gè)對(duì)象 Vi含 d個(gè)關(guān)鍵字 (Ki1,Ki2,..., Kid)。若對(duì)序列中的任意兩個(gè)對(duì)象 Vi和 Vj都有 (Ki1,Ki2,..., Kid) (Kj1,Kj2,..., Kjd) 則稱序列對(duì)關(guān)鍵字 (Ki1,Ki2,..., Kid)有序，且 K1稱為最高位關(guān)鍵字， Kd稱為最低位關(guān)鍵字。 多關(guān)鍵字排序 原理：根據(jù)組成關(guān)鍵字的各位的值進(jìn)行排序。 實(shí)現(xiàn)基數(shù)排序的兩種方法： 最高位優(yōu)先 (MSD)排序 ：從關(guān)鍵字的高位到低位 最低位優(yōu)先 (LSD)排序 ：從關(guān)鍵字的低位到高位 MSD方法通常是一個(gè)遞歸的過(guò)程。 LSD和 MSD方法也可應(yīng)用于對(duì)一個(gè)關(guān)鍵字進(jìn)行的排序。此時(shí)可將單關(guān)鍵字 Ki看成是一個(gè)子關(guān)鍵字組： (Ki1,Ki2,..., Kid) 如對(duì)關(guān)鍵字取值范圍為 0到 999的一組對(duì)象，可看成是 (K1,K2,K3)的組合。 MSD方法按 K1,K2,K3的順序?qū)λ袑?duì)象排序； LSD方法按 K3 ,K2 , K1的順序?qū)λ袑?duì)象排序。 鏈?zhǔn)降幕鶖?shù)排序 基數(shù)排序是一種典型的 LSD排序方法，它利用“分配”和“收集”兩種運(yùn)算對(duì)單關(guān)鍵字進(jìn)行排序。 此時(shí)可將單關(guān)鍵字 K看成是一個(gè)子關(guān)鍵字組： (Ki1,Ki2,..., Kid) 排序過(guò)程：設(shè)關(guān)鍵字共有 d位，讓 j= d, d1,...,1, 依次執(zhí)行 d次“分配”與“收集”。 179 208 306 93 859 984 55 9 271 33 B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e 271 93 33 984 55 306 208 179 859 9 271 93 33 984 55 306 208 179 859 9 B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e 33 984 306 208 9 55 859 271 179 93 306 208 9 33 55 859 271 179 984 93 B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e 179 306 984 859 9 33 55 93 208 271 9 33 55 93 179 208 271 306 859 984 分配排序算法 typedef struct { int key[d]。 int next。 datatype other。 } rectype。 rectype R[n]。 typedef struct { int f,e。 } queue。 queue B[m]。 for (j=d1。j=0。j) { for (i=0。im。i++) { B[i].f=1。 B[i].e=1。 } while (p!=1) { k=R[p].key[j]。 if (B[k].f==1) B[k].f=p。 else R[B[k].e].next=p。 B[k].e=p。 p=R[p].next。 } i=0。 while (B[i].f==1) i++。 t=B[i].e。 p=B[i].f。 while (im1) { i++。 if (B[i].f!=1) {R[t].next=B[i].f。 t=B[i].e。} } R[t].next=1。 } return p。 } int RADIXSORT(rectype R[]) { int i,j,k,t,p。 for (i=0。in1。i++) R[i].next=i+1。 R[n1].next=1。 p=0。 內(nèi)部排序方法的比較和選擇 選取排序方法時(shí)需要考慮的因素有： 待排序的記錄數(shù)目 記錄本身信息量的大小 關(guān)鍵字的結(jié)構(gòu)及其分布情況 對(duì)排序穩(wěn)定性的要求 語(yǔ)言工具的條件、輔助空間的大小 外部排序簡(jiǎn)介 如果待排序的記錄數(shù)很大，無(wú)法將所有記錄都調(diào)入內(nèi)存，只能將它們存放在外存上，我們稱這時(shí)的排序?yàn)橥獠颗判颉? 外部排序的實(shí)現(xiàn)，主要是依靠數(shù)據(jù)的內(nèi)外存交換和“內(nèi)部歸并”。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1