基数排序
“基数排序法”（radix sort）则是属于“分配式排序”（distribution sort），基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
解法
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
以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相反，是由高位数为基底开始进行分配，其他的演算方式则都相同。
实作
* C
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
int temp[10][10] = ;
int order[10] = ;
int i, j, k, n, lsd;
k = 0;
n = 1;
printf("
排序前: ");
for(i = 0; i < 10; i++)
printf("%d ", data);
putchar('
');
while(n <= 10) {
for(i = 0; i < 10; i++) {
lsd = ((data / n) % 10);
temp[lsd][order[lsd]] = data;
order[lsd]++;
}
printf("
重新排列: ");
for(i = 0; i < 10; i++) {
if(order != 0)
for(j = 0; j < order; j++) {
data[k] = temp[j];
printf("%d ", data[k]);
k++;
}
order = 0;
}
n *= 10;
k = 0;
}
putchar('
');
printf("
排序后: ");
for(i = 0; i < 10; i++)
printf("%d ", data);
return 0;
}
* Java
public class RadixSort {
public static void sort(int[] number, int d) {
int k=0;
int n=1;
int m=1;
int[][] temp = new int[number.length][number.length];
int[] order = new int[number.length];
while(m <= d) {
for(int i = 0; i < number.length; i++) {
int lsd = ((number[i] / n) % 10);
temp[lsd][order[lsd]] = number[i];
order[lsd]++;
}
for(int i = 0; i < d; 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, 10);
for(int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
}
c++实现基数排序int maxbit(int data[],int n) //辅助函数，求数据的最大位数
{
int d = 0;
int * tmp = new int[n];
for(int i = 0 ;i < n;i++)
tmp[i]= data[i];
for(int i = 0;i < n;i++)
{
int p =1;
while(tmp[i]/10 > 0)
{
p++;
tmp[i]= tmp[i]/10;
}
if(d < p) d = p;
}
delete [] tmp;
return d;
}
void radixsort(int data[],int n) //基数排序
{
int d = maxbit(data,n);
int * tmp = new int[n];
int * count = new int[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;
count[k]--;
tmp[count[k]] = data[j];
}
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(ref arr);//排序
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 = new List<int>();//存放每次排序后的元素
List<int>[] listArr = new List<int>[10];//十个桶
char currnetChar;//存放当前的字符 比如说 某个元素123 中的2
string currentItem;//存放当前的元素 比如说 某个元素123
for (int i = 0; i < listArr.Length; i++)//给十个桶分配内存初始化。
listArr[i] = new List<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); continue; }//如果发生异常，则将该数压入listArr[0]。比如说5 是没有十位数的，执行上面的操作肯定会发生越界异常的，这正是期望的行为，我们认为5的十位数是0，所以将它压入listArr[0]的桶里。
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("unknow error");
}
}
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 (int i in arr)
System.Console.Write(i.ToString()+'');
System.Console.WriteLine();
}
//产生随机数组。随机数的范围是0到1000。 参数iLength指产生多少个随机数
public static int[] CreateRandomArray(int iLength)
{
int[] arr = new int[iLength];
Random random = new Random();
for (int i = 0; i < iLength; i++)
arr[i] = random.Next(0,1001);
return arr;
}
}
}