反饋

基數排序

基數排序（radix sort）屬於“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。

中文名: 基數排序
外文名: Radix sort
別名: “桶子法”

類別: 分配式排序
方法: 最高位優先法和最低位優先
發明者: 赫爾曼·何樂禮
領域: 計算機算法

基數排序基本解法

基數排序第一步

以LSD為例，假設原來有一串數值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：

1 81

2 22

3 73 93 43

4 14

5 55 65

8 28

9 39

基數排序第二步

接下來將這些桶子中的數值重新串接起來，成為以下的數列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再進行一次分配，這次是根據十位數來分配：

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相反，是由高位數為基底開始進行分配，但在分配之後並不馬上合併回一個數組中，而是在每個“桶子”中建立“子桶”，將每個桶子中的數值按照下一數位的值分配到“子桶”中。在進行完最低位數的分配後再合併回單一的數組中。

基數排序效率分析

時間效率^[1] ：設待排序列為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表示最大的數有多少位
    {
        int k = 0;
        int n = 1;
        int m = 1; //控制鍵值排序依據在哪一位
        int[][]temp = new int[10][number.length]; //數組的第一維表示可能的餘數0-9
        int[]order = new int[10]; //數組order[i]用來表示該位是i的數的個數
        while(m <= d)
        {
            for(inti = 0; i < number.length; i++)
            {
                int lsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }
            for(int i = 0; i < 10; i++)
            {
                if(order[i] != 0)
                    for(int j = 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(int i = 0; i < data.length; i++)
        {
            System.out.print(data[i] + "");
        }
    }
}

基數排序pascal

type link=^node;
node=record
data:integer;
next:link;
end;
var
i,j,l,m,k,n:integer;
a:array[1..100] of integer;
s:string;
q,head:array[0..9] of link;
p,p1:link;
begin
readln(n);
writeln('Enterdata:');
for i:=1 to n do read(a[i]);
for i:=5 downto 1 do
begin
for j:=0 to 9 do
begin
new(head[j]);
head[j]^.next:=nil;
q[j]:=head[j]
end;
for j:=1 to n do
begin
str(a[j],s);
for k:=1 to 5-length(s) do
s:='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 do
begin
p:=head[j];
while p^.next<>nil do
begin
l:=l+1;
p1:=p;
p:=p^.next;
dispose(p1);
a[l]:=p^.data;
end;
end;
end;
writeln('Sorteddata:');
for i:=1 to n do
write(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-8

import math

def 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){

//AAuto在字符串索引越界時，會返回0，這使基數排序的實現更加簡單。

//我們首先找出最大的排序長度，然後對於不足此長度的字符串，尾部都假定以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();//關閉控制枱

參考資料

1. Data Structures and Algorithms:Radix Sorting ．The University of Auckland．1998[引用日期2015-02-28]

基數排序的概述圖（1張）

詞條統計

瀏覽次數：次
編輯次數：59次歷史版本
最近更新：饮水此（2023-12-24）

基數排序

目錄

基數排序基本解法

基數排序第一步

基數排序第二步

基數排序第三步

基數排序效率分析

基數排序實現方法

基數排序實現原理

基數排序實現

基數排序C語言

基數排序Java語言

基數排序pascal

基數排序c++

基數排序C# 實現基數排序

基數排序python 實現

基數排序AAuto

基數排序第一步

基數排序第二步

基數排序第三步

基數排序第四步

基數排序第五步

基數排序第六步

基數排序第七步