基數排序 (Radix Sort).

Presentation on theme: "基數排序 (Radix Sort)."— Presentation transcript:

1 基數排序 (Radix Sort)

2 前面的排序技巧都是基於比較和移動欲排序的元素，而基數排序法(Radix sort)不做任何比較。若使用連結資料結構時，也不需移動元素。

3 定義 基數排序法的基本運算是將元素自一個連結串列上取出，加至另一個連結串列上。
若每個元素的排序項目最多含有k個字元，而每個元素將重新連結n次。所以共需k*n次重新連結運算的工作量。 這是一個很有用的解決方法，因為對於任意資料的排序，比較大小的的方式來排序的演算法則，至少(nlogn)次元素比較才能完成排序的。

4 基本運算 尚未排序： 字元值：

5 個位數排序： 字元值： 第一步是根據整數的最小位數，將整數加到某個串列上，我們稱為字元串(character lists)。對於每個可能出現的字元值必須存在一個字元串列。在本例串列出現的字元值是0、1、…、9。

6 十位數排序： 字元值： 第二步是取出個位數排序的整數，將它們依據其十位數值，加入適當的字元串列上，其結果如圖2示。將這些串列依序連結起來可以產生十位數排序的資料。

7 最後排序的結果如下： 015，56，107，228，312，371，452，456，575，714，749，833 最後第三步，是將每個整數依據其最大位數(百位數)值，放入適當的字元串列中，其過程如圖9-8-3所示。將這些串列依序連結之後，就完成了基數排序法

8 演算法 演算法＝＞C語言程式碼 msd_sort(int a[ ], int b [ ], int l, int r, int factor) { int i, j, v, count [l ], c [ l ] ; for ( i =0 ; i < l ; i + +) count [ i ] = 0 ; for ( i =l ; i <= r ; i + +) v = a [ i ] / factor % 10 ; count [ v + l ] + + ; }

9 c [ 0 ] = 0 ; for ( i = 1 ; i < l ; i + + ) { count [ i ] += count [ i – 1 ] ; c [ i ] = count [ i ]; } for ( i = 1 ; i <= r ; i + + ) j = a [i ] / factor % 10 ; b [count [ j ] + + ] = a [ i ] ;

10 for ( i = 1 ; i <= r ; i + + ) a [i ] = b [ i –1 ] ; factor /= 10 ; for ( i = 0 ; i < 10 ; i + + ) { j = c [i ] + l ; v = c[i +l ] +l –1 ; if ( v > j && factor > 0 ) msd_sort( a, b, j, v, factor ) ; }

11 ＝＞時間複雜度分析 基數排列的分類是穩定的情況 所需的平均的時間複雜度均為O(nlogr m)，r是所採用的數字系統基底，m是堆數。
在某些情況下，所需的時間是O(n)，所需的空間很大，需要(n * n)，ｎ為記錄數。

12 程式範例－基數排序 #include <studio.h> void adjust ( int [ ], int ) ;
int data [10] = { 75, 23, 98, 44, 57, 12, 29, 64, 38, 82 } ; void main ( ) { int i , j, k - 0, lst, temp [10] [10]

13 int order ([10]) = {75,23,98,44,57,12,29,64,38,82} ; printf ( “\n << Rp sort >>\n ) ; printf ( “Number : “ ) for ( i = 0; i <= 10; i ++) printf ( “%d “, data [i] ); puts (“ “); for ( i = 0 ; i < 60, i ++ ) printf ( “－“) ; while ( n <= 10 ) {

14 for ( i = 0 ; i < 10; i ++) { lst = ((data [i] / n ) % 10 ) temp [lsd] [order [lsd] ] = data [i] ; order [lsd] ++; } printf ( “\nAccess : “ ) ; for ( i = 1; i < 10; i ++) for ( j = 0 ; j < order [i] ; j ++ ) data [k] = temp [ i ] [ j ] ; printf ( “%d “, data [k] ) ; k ++ ;

15 order [ i ] = 0 ; } n * = 10 ; k = 0 ; puts ( “ “ ) ; for ( i = 0; i < 60; i ++) printf ( “-“ ) ; printf ( “\nSorting : “ ) ; for ( i = 1; i < 10; i ++) printf ( “%d “, data [ i ]) ;

16 外部排序法 External Sort

17 當資料量太大時，我們無法將資料一次全部放在主記憶體中做處理，又由於現今電腦的主記憶容量增加的速度遠低於儲存設備，所有大量的資料還是儲存於外部儲存裝置中。

18 定義 外部排序最常用的方法是合併排序法，它先將檔案分段，每一段檔案用內部排序法加以排序之後再將它們寫到外部儲存裝置；
排序過後的各段資料稱為行程runs)，將各行程利用合併排序法逐漸合併，直到最後一個行程為止。

19 各種排序法的比較 考慮下列幾方面： 時間複雜度 空間複雜度 穩定性 演算法簡單程度 資料數目 資料記錄本身的大小

20 時間複雜度與穩定性 類別 排序法 平均時間 最差狀況 穩定度 內部 氣泡排序 Bubble O(n2) 不穩定 插入排序 Insertion
選擇排序 Selection 謝爾排序 Shell O(nlogn) O(ns)1<S<2 快速排序 Quick 累堆排序 Heap 二元排序 Binary tree 不一定 外部 合併排序 Merge

21 穩定度:相同的數值排序後順序是否和排序前順序相同.若'是'稱為穩定,若'不是'稱為不穩定.
平均時間：程式平均執行次數. 最差狀況:程式最差執行次數. 穩定度:相同的數值排序後順序是否和排序前順序相同.若'是'稱為穩定,若'不是'稱為不穩定. 類別:分為2類 內部排序 適合於所有資料可以寫入記憶體中. 外部排序 適合於所有資料無法全部寫入記憶體中，需使用輔助記憶體。

22 空間複雜度 合併排序法與基數排序法的空間複雜度為O(N) 快速排序法需要O(logN) 而其他排序法皆為O(1)。

23 簡單性 插入、選擇、及泡沫排序法的演算法都比較直接而簡單，而改良排序法則比較複雜。 當資料的數目很小時，由於N2與Nlog N的值差異不大
可以選擇較簡單易寫的排序法 當資料數目很大時 應該採用改良後的排序法