基本介紹
- 中文名：基數排序
- 外文名：Radix sort
- 類別：分配式排序
- 別稱：“桶子法”
- 方法：最高位優先法和最低位優先
- 發明者：赫爾曼·何樂禮
- 領域：計算機算法
基本解法,第一步,第二步,第三步,效率分析,實現方法,實現原理,實現,C語言,Java語言,pascal,c++,C# 實現基數排序,python 實現,AAuto,第一步,第二步,第三步,第四步,第五步,第六步,第七步,
基本解法
第一步
以LSD為例，假設原來有一串數值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下來將這些桶子中的數值重新串接起來，成為以下的數列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接著再進行一次分配，這次是根據十位數來分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下來將這些桶子中的數值重新串接起來，成為以下的數列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。
LSD的基數排序適用於位數小的數列，如果位數多的話，使用MSD的效率會比較好。MSD的方式與LSD相反，是由高位數為基底開始進行分配，但在分配之後並不馬上合併回一個數組中，而是在每個“桶子”中建立“子桶”，將每個桶子中的數值按照下一數位的值分配到“子桶”中。在進行完最低位數的分配後再合併回單一的數組中。
效率分析
時間效率：設待排序列為n個記錄，d個關鍵碼，關鍵碼的取值範圍為radix，則進行鏈式基數排序的時間複雜度為O(d(n+radix))，其中，一趟分配時間複雜度為O(n)，一趟收集時間複雜度為O(radix)，共進行d趟分配和收集。 空間效率：需要2*radix個指向佇列的輔助空間，以及用於靜態鍊表的n個指針。
實現方法
最高位優先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之後，對後面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序後。再將各組連線起來，便得到一個有序序列。
最低位優先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重複，直到對k1排序後便得到一個有序序列。
實現原理
基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(Tabulation Machine)上的貢獻。它是這樣實現的：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。
基數排序的方式可以採用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
實現
C語言
#include<math.h>testBS(){ inta[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3}; int *a_p = a; //計算數組長度 intsize = sizeof(a) / sizeof(int); //基數排序 bucketSort3(a_p, size); //列印排序後結果 inti; for(i = 0; i < size; i++) { printf("%d\n", a[i]); } intt; scanf("%d", t);}//基數排序voidbucketSort3(int *p, intn){ //獲取數組中的最大數 intmaxNum = findMaxNum(p, n); //獲取最大數的位數，次數也是再分配的次數。 intloopTimes = getLoopTimes(maxNum); inti; //對每一位進行桶分配 for(i = 1; i <= loopTimes; i++) { sort2(p, n, i); }}//獲取數字的位數intgetLoopTimes(intnum){ intcount = 1; inttemp = num / 10; while(temp != 0) { count++; temp = temp / 10; } returncount;}//查詢數組中的最大數intfindMaxNum(int *p, intn){ inti; intmax = 0; for(i = 0; i < n; i++) { if(*(p + i) > max) { max = *(p + i); } } returnmax;}//將數字分配到各自的桶中，然後按照桶的順序輸出排序結果voidsort2(int *p, intn, intloop){ //建立一組桶此處的20是預設的根據實際數情況修改 intbuckets[10][20] = {}; //求桶的index的除數 //如798個位桶index=(798/1)%10=8 //十位桶index=(798/10)%10=9 //百位桶index=(798/100)%10=7 //tempNum為上式中的1、10、100 inttempNum = (int)pow(10, loop - 1); inti, j; for(i = 0; i < n; i++) { introw_index = (*(p + i) / tempNum) % 10; for(j = 0; j < 20; j++) { if(buckets[row_index][j] == NULL) { buckets[row_index][j] = *(p + i); break; } } } //將桶中的數，倒回到原有數組中 intk = 0; for(i = 0; i < 10; i++) { for(j = 0; j < 20; j++) { if(buckets[i][j] != NULL) { *(p + k) = buckets[i][j]; buckets[i][j] = NULL; k++; } } }}Java語言
public class RadixSort{ public static void sort(int[] number, int d) //d表示最大的數有多少位 { intk = 0; intn = 1; intm = 1; //控制鍵值排序依據在哪一位 int[][]temp = newint[10][number.length]; //數組的第一維表示可能的餘數0-9 int[]order = newint[10]; //數組orderp[i]用來表示該位是i的數的個數 while(m <= d) { for(inti = 0; i < number.length; i++) { intlsd = ((number[i] / n) % 10); temp[lsd][order[lsd]] = number[i]; order[lsd]++; } for(inti = 0; i < 10; i++) { if(order[i] != 0) for(intj = 0; j < order[i]; j++) { number[k] = temp[i][j]; k++; } order[i] = 0; } n *= 10; k = 0; m++; } } public static void main(String[] args) { int[]data = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100}; RadixSort.sort(data, 3); for(inti = 0; i < data.length; i++) { System.out.print(data[i] + ""); } }}pascal
type link=^node;node=recorddata:integer;next:link;end;vari,j,l,m,k,n:integer;a:array[1..100] of integer;s:string;q,head:array[0..9] of link;p,p1:link;beginreadln(n);writeln('Enterdata:');for i:=1 to n do read(a[i]);for i:=5 downto 1 dobeginfor j:=0 to 9 dobeginnew(head[j]);head[j]^.next:=nil;q[j]:=head[j]end;for j:=1 to n dobeginstr(a[j],s);for k:=1 to 5-length(s) dos:='0'+s;m:=ord(s[i])-48;new(p);p^.data:=a[j];p^.next:=nil;q[m]^.next:=p;q[m]:=p;end;l:=0;for j:=0 to 9 dobeginp:=head[j];while p^.next<>nil dobeginl:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data;end;end;end;writeln('Sorteddata:');for i:=1 to n dowrite(a[i]:6);end.c++
int maxbit(int data[], int n) //輔助函式，求數據的最大位數{ int d = 1; //保存最大的位數 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d;}void radixsort(int data[], int n) //基數排序{ int d = maxbit(data, n); int *tmp = newint[n]; int *count = newint[10]; //計數器 int i, j, k; int radix = 1; for(i = 1; i <= d; i++) //進行d次排序 { for(j = 0; j < 10; j++) count[j] = 0; //每次分配前清空計數器 for(j = 0; j < n; j++) { k = (data[j] / radix) % 10; //統計每個桶中的記錄數 count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶 for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; j++) //將臨時數組的內容複製到data中 data[j] = tmp[j]; radix = radix * 10; } delete[]tmp; delete[]count;}C# 實現基數排序
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace LearnSort{ class Program { static void Main(string[] args) { int[] arr = CreateRandomArray(10); //產生隨機數組 Print(arr);//輸出數組 RadixSort(refarr);//排序 Print(arr);//輸出排序後的結果 Console.ReadKey(); } public static void RadixSort(ref int[] arr) { int iMaxLength = GetMaxLength(arr); RadixSort(ref arr, iMaxLength); } //排序 private static void RadixSort(ref int[] arr, int iMaxLength) { List<int> list = newList<int>(); //存放每次排序後的元素 List<int>[] listArr = newList<int>[10]; //十個桶 char currnetChar;//存放當前的字元比如說某個元素123中的2 string currentItem;//存放當前的元素比如說某個元素123 for(int i = 0; i < listArr.Length; i++) //給十個桶分配記憶體初始化。 listArr[i] = newList<int>(); for(int i = 0; i < iMaxLength; i++) //一共執行iMaxLength次，iMaxLength是元素的最大位數。 { foreach(int number in arr)//分桶 { currentItem = number.ToString(); //將當前元素轉化成字元串 try { currnetChar = currentItem[currentItem.Length - i - 1]; //從個位向高位開始分桶 } catch { listArr[0].Add(number); //如果發生異常，則將該數壓入listArr[0]。比如說5是沒有十位數的，執行上面的操作肯定會發生越界異常的，這正是期望的行為，我們認為5的十位數是0，所以將它壓入listArr[0]的桶里。 continue; } switch(currnetChar)//通過currnetChar的值，確定它壓人哪個桶中。 { case'0': listArr[0].Add(number); break; case'1': listArr[1].Add(number); break; case'2': listArr[2].Add(number); break; case'3': listArr[3].Add(number); break; case'4': listArr[4].Add(number); break; case'5': listArr[5].Add(number); break; case'6': listArr[6].Add(number); break; case'7': listArr[7].Add(number); break; case'8': listArr[8].Add(number); break; case'9': listArr[9].Add(number); break; default: throw new Exception("unknowerror"); } } for(int j = 0; j < listArr.Length; j++) //將十個桶里的數據重新排列，壓入list foreach(int number in listArr[j].ToArray<int>()) { list.Add(number); listArr[j].Clear();//清空每個桶 } arr = list.ToArray<int>(); //arr指向重新排列的元素 //Console.Write("{0}times:",i); Print(arr);//輸出一次排列的結果 list.Clear();//清空list } } //得到最大元素的位數 private static int GetMaxLength(int[] arr) { int iMaxNumber = Int32.MinValue; foreach(int i in arr)//遍歷得到最大值 { if(i > iMaxNumber) iMaxNumber = i; } return iMaxNumber.ToString().Length;//這樣獲得最大元素的位數是不是有點投機取巧了... } //輸出數組元素 public static void Print(int[] arr) { foreach(intiinarr) System.Console.Write(i.ToString() + '\t'); System.Console.WriteLine(); } //產生隨機數組。隨機數的範圍是0到1000。參數iLength指產生多少個隨機數 public static int[] CreateRandomArray(int iLength) { int[] arr = new int[iLength]; Random random = new Random(); for(inti = 0; i < iLength; i++) arr[i] = random.Next(0, 1001); return arr; } }}python 實現
#!/usr/bin/env python#encoding=utf-8import mathdef sort(a, radix=10): """a為整數列表， radix為基數""" K = int(math.ceil(math.log(max(a), radix))) # 用K位數可表示任意整數 bucket = [[] for i in range(radix)] # 不能用 [[]]*radix for i in range(1, K+1): # K次循環 for val in a: bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整數第K位數字 （從低到高） del a[:] for each in bucket: a.extend(each) # 桶合併 bucket = [[] for i in range(radix)]
AAuto
第一步
io.open();//打開控制台
/*
*-------------------------------------------------------
* 基數排序
**------------------------------------------------------
*/
/*
第二步
其原理在於對於待排序的數據，整體權重未知的情況下，
先按權重小的因子排序，然後按權重大的因子排序。
例如比較時間，先按日排序，再按月排序，最後按年排序，僅需排序三次。
但是如果先排序高位就沒這么簡單了。
基數排序源於老式穿孔機，排序器每次只能看到一個列，
很多教科書上的基數排序都是對數值排序，數值的大小是已知的，與老式穿孔機不同。
將數值按位拆分再排序，是無聊並自找麻煩的事。
算法的目的是找到最佳解決問題的方案，而不是把簡單的事搞的更複雜。
基數排序更適合用於對時間、字元串等這些整體權值未知的數據進行排序。
這時候基數排序的思想才能體現出來，例如字元串，如果從高位（第一位）往後排就很麻煩。
而反過來，先對影響力較小，排序排重因子較小的低位（最後一位）進行排序就非常簡單了。
這時候基數排序的思想就能體現出來。
又或者所有的數值都是以字元串形式存儲，就象穿孔機一樣，每次只能對一列進行排序。
這時候基數排序也適用，例如：對{"193";"229";"233";"215"}進行排序
下面我們使用基數排序對字元串進行排序。
對每個位循環調用計數排序。
*/
第三步
//計數排序算法
radix_sort = function( array ,maxlen){
//我們首先找出最大的排序長度，然後對於不足此長度的字元串，尾部都假定以0補齊。
//對於超出此長度的位在比較時忽略
if(!maxlen){
maxlen =0;
for(i=1;#array;1){
maxlen = math.max(maxlen,#array[i] )
}
}
//else{
//最大排序長度也可以從參數中傳過來，這樣就不用遍歷所有字元串了
//}
第四步
//從字元串的最後一位開始，到第一位
for(pos=maxlen;1;-1){
var array_sorted ={};
var count = {};
for(i=0;256 ){
count[i] = 0;
}
var bytecode;
for(i=1;#array;1){
//如果pos大於字元串長度，AAuto會返回0，這使基數排序的實現更容易
bytecode = array[i][pos] ;
count[ bytecode ] ++; //count[n] 包含等於n的個數
}
第五步
//統計位置
for(i=1;256;1){
count[i] += count[i-1]; //count[i] 包含小於等於i的個數
}
var n;
for(i=#array;1;-1){
n = array[i][pos]
array_sorted[ count[n] ] = array[i];
count[n]--;//防止相同的元素n再次出現，將計數減一
}
array = array_sorted;
}
return array
}
io.print("----------------")
io.print("基數排序( 線性時間排序 )")
io.print("----------------")
array ={"AAuto is quicker and better,just try it!";"AAuto Quicker";"193";"229";"233";"215";"Hello Word";"abc";"abcd";"xd";"adcd";"eddd";"ah";"ai";"aj";"ajkk"};
第六步
//排序
array = radix_sort(array )
第七步
//輸出結果
for(i=1;#array;1){
io.print( array[i] )
}
execute("pause") //按任意鍵繼續
io.close();//關閉控制台
