【正文】 移動都是 O(n)； 歸并趟數(shù)為 log2n。 時間復雜度為 O(nlog2n)。 (3) 空間復雜度是 O(n)。 ? 2路歸并排序算法分析 歸并排序 74 概述 插入排序 快速排序 選擇排序 歸并排序 基數(shù)排序 內(nèi)部排序方法的比較 第 9章 內(nèi)部排序 75 (1)基數(shù)起源于排序箱 (桶 )排序 ， 設(shè)置若干個箱子 (桶 ),依次掃描待排序的記錄 ,A[1],A[2],… ,A[n],把關(guān)鍵字為 k的記錄放在第 k個箱子里 ,按序號將非空的箱子里的記錄收集起來 。 (2)箱 (桶 )排序的缺點：如果關(guān)鍵字位數(shù)太大 ，這樣做空間復雜度和時間復雜度都太大 。 順序基數(shù)排序 ? 基數(shù)排序的起源 第 9章 內(nèi)部排序 76 Q[0] Q[1] Q[2] Q[3] Q[4] Q[5] Q[6] Q[7] Q[8] Q[9] 890 210 321 901 432 012 123 543 765 986 987 018 678 098 789 109 待排序關(guān)鍵字： 321 986 123 432 543 018 765 678 987 789 098 890 109 901 210 012 ? 事例演示 順序基數(shù)排序 第 9章 內(nèi)部排序 77 Q[0] Q[1] Q[2] Q[3] Q[4] Q[5] Q[6] Q[7] Q[8] Q[9] 901 109 210 012 018 321 123 432 543 765 678 986 987 789 890 098 890 210 321 901 432 012 123 543 765 986 987 018 678 098 789 109 ? 事例演示 順序基數(shù)排序 第 9章 內(nèi)部排序 78 Q[0] Q[1] Q[2] Q[3] Q[4] Q[5] Q[6] Q[7] Q[8] Q[9] 012 109 123 210 321 432 678 765 789 890 901 986 987 018 098 543 901 109 210 012 018 123 432 543 765 678 986 987 433 789 809 098 ? 事例演示 順序基數(shù)排序 第 9章 內(nèi)部排序 79 設(shè)待排記錄 A的關(guān)鍵字是 figure位的正整數(shù) 。 (1) 從最低位 (個位 )開始 ， 掃描關(guān)鍵字的 pass位 ,把等于 0的插入 Q[0],… ,等于 9的插入 Q[9]。 (3) pass+1直到 figure， 重復執(zhí)行 1， 2兩步 (2) 將 Q[0],… ,Q[9]中的數(shù)據(jù)依次收集到 A[]中 。 ? 排序過程 順序基數(shù)排序 第 9章 內(nèi)部排序 80 int RADIX(int k,int p) { return((k/pow10(p1))%10)。 } ? 求關(guān)鍵字 k的第 p位算法 順序基數(shù)排序 第 9章 內(nèi)部排序 81 void radixsort(int figure, QUEUE amp。A){ QUEUE Q[10]。records data。 int pass,r,i。 //pass用于位數(shù)循環(huán) ,r取位數(shù) for(pass=1。pass=figure。pass++) 把 10個隊列置空 while(!EMPTY(A)) { 取 A中元素 dada， 計算 data的關(guān)鍵字的第 pass位的值 r， 放入隊列 Q[r]中； } 把 10個隊列中的值依次收集到 A中 } ? 基數(shù)排序算法 順序基數(shù)排序 第 9章 內(nèi)部排序 82 void radixsort(int figure,QUEUE amp。A){ QUEUE Q[10]。records data。 int pass,r,i。 //pass用于位數(shù)循環(huán) ,r取位數(shù) for(pass=1。pass=firure。pass++){ for(i=0。i=9。i++) MAKENULL(Q[i]) while(!EMPTY(A)) { data=FRONT(A)。 DEQUEUE(A)。 r=RADIX(,pass)。 ENQUEUE(data,Q[r])。 } ? 基數(shù)排序算法 順序基數(shù)排序 第 9章 內(nèi)部排序 83 For(i=0。i=9。i++) While(!EMPTY(Q[i])) {data=FRONT(Q[i])。 DEQUEUE(Q[i])。 ENQUEUE(data,A)。 } } } ? 基數(shù)排序算法 順序基數(shù)排序 第 9章 內(nèi)部排序 84 如果采用數(shù)組表示隊列 ,隊列的長度很難確定 ,太大造成浪費 ,小了會產(chǎn)生溢出 。 一般采用鏈隊列 . 110 920 230 030 090 320 100 400 503 765 678 986 987 789 890 098 如果采用順序隊列 ， 隊列的長度怎么確定 ？ ? 問題分析 順序基數(shù)排序 第 9章 內(nèi)部排序 85 struct QUEUE{ celltype *front。 celltype *rear。 } struct celltype{ records element。 celltype *next } ? 存儲結(jié)構(gòu) 鏈式基數(shù)排序 第 9章 內(nèi)部排序 86 Q0 012 018 098 Q1 109 123 Q2 210 ^ ^ ? 事例演示 鏈式基數(shù)排序 第 9章 內(nèi)部排序 87 void CONCATENATE(QUEUE amp。Q[0], QUEUE amp。Q[1]){ if(!EMPTY(Q[1])){ Q[0].rearnext=Q[1].frontnext。 Q[0].rear=Q[1].rear。 } } ? 收集算法關(guān)鍵語句 鏈式基數(shù)排序 第 9章 內(nèi)部排序 88 順序收集算法 for(i=1。i=9。i++) CONCATENATE(Q[0],Q[i])。 A=Q[0]。 For(i=0。i=9。i++) While(!EMPTY(Q[i])) {data=FRONT(Q[i])。 DEQUEUE(Q[i])。 ENQUEUE(data,A)。 } 鏈式收集算法 鏈式基數(shù)排序 ? 兩種收集算法的比較 第 9章 內(nèi)部排序 89 ? 算法分析 基數(shù)排序是穩(wěn)定的 時間復雜性與空間復雜性分析： 設(shè)關(guān)鍵字位數(shù)為 d 則時間復雜性為 O(dn) 考慮到 d是一個常數(shù) 時間復雜性為 O(n) 空間復雜性 O(n) 鏈式基數(shù)排序 90 概述 插入排序 快速排序 選擇排序 歸并排序 基數(shù)排序 內(nèi)部排序方法的比較 第 9章 內(nèi)部排序 91 排序方法 比較次數(shù) 移動次數(shù) 穩(wěn)定 性 附加存儲 最好 最差 最好 最差 最好 最差 直接插入排序 冒泡排序 快速排序 簡單選擇排序 堆排序 歸并排序 基數(shù)排序 n n2 0 n2 √ 1 n n2 0 n2 √ 1 nlog2n n2 0 n2 log2n n n2 0 n √ 1 nlog2n nlog2n 1 nlog2n nlog2n √ n …… dn √ n 內(nèi)部排序方法的比較 第 9章 內(nèi)部排序 92 本章小結(jié) 熟練掌握 ： 直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序、基數(shù)排序的思想和算法。充分了解各種排序算法的應(yīng)用背景和優(yōu)缺點。 加強各種排序算法在實際應(yīng)用中的訓練，提高實際應(yīng)用水平。