说起排序，大多数人在实际项目中很少自己去写一个排序，一般来说，qsort一行话就可以了。我也很少在实际项目中用到过基数排序，最近，写了一篇博客文章叫做： 字符串之全文索引 ，这篇文章的下一篇文章 要用到一个倍增算法。这个倍增算法，就可以非常巧妙的运用基数排序。作为那篇文章的一个铺垫，我专门写了一篇基数排序的文章。这篇文章里面的基数排序肯定是一个变形。
大多数网上 或者 书上的基数排序都是从下面的例子开始的：
排序下面的数列：
73 22 93 43 55 14 28 65 39 81
然后对这些数字，用个位数进行排序：
| 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
再对10位数进行排序：
| 0 | |||||||||
| 1 | 14 | ||||||||
| 2 | 22 | 28 | |||||||
| 3 | 39 | ||||||||
| 4 | 43 | ||||||||
| 5 | 55 | 65 | |||||||
| 6 | |||||||||
| 7 | 73 | ||||||||
| 8 | 81 | ||||||||
| 9 | 93 |
从这个二维数组里面顺序取出：
14 22 28 39 43 55 65 73 81 93
上面的思路写成代码也非常的容易写：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int data[10]={73,22,93,43,55,14,28,65,39,81};
int temp[10][10]= {0};
int order[10]={0};
int i,j,k,n,lsd;
printf("\n排序前: ");
for (i=0; i<10; i++) printf("%d ",data[i]);
putchar('\n');
n=1;
while (n<=10)
{
for (i=0;i<10;i++)
{
lsd=((data[i]/n)%10);
temp[lsd][order[lsd]]=data[i];
order[lsd]++;
}
printf("\n重新排列: ");
k = 0;
for (i=0;i<10;i++)
{
if(order[i]!=0)
{
for (j=0;j<order[i];j++)
{
data[k]=temp[i][j];
printf("%d ",data[k]);
k++;
}
order[i]=0;
}
}
n *= 10;
}
putchar('\n');
printf("\n排序后: ");
for (i=0; i<10; i++) printf("%d ",data[i]);
return 0;
}
既然这个基数排序理论上性能比较的高，这样的话，我们就写个程序比较一下实际上快速排序和基数排序的速度。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <algorithm>
#define MAX_N 5000000
int sort[10][MAX_N];
int data[MAX_N];
int data2[MAX_N];
int data3[MAX_N];
int radix_sort(int data[], int max_index, int max_number);
static int range_rand(int min, int max);
int intcmp(const void *a, const void *b)
{
return *((int *)a) - *((int *)b);
}
int main()
{
int i;
int max = -1;
clock_t t;
for (i = 0; i < MAX_N; i++)
{
data[i] = range_rand(1, 0xFFFFFFF);
if (max < data[i]) max = data[i];
}
memcpy(data2, data, sizeof(data));
memcpy(data3, data, sizeof(data));
t = clock();
qsort(data, MAX_N, sizeof(int), intcmp);
printf("qsort cost : %d \n", clock() - t);
t = clock();
radix_sort(data2, MAX_N, max);
printf("radix cost : %d \n", clock() - t);
t = clock();
std::sort(data3, data3 + MAX_N);
printf("std::sort cost : %d \n", clock() - t);
for (i = 0; i < 20; i++)
{
printf("%d ", data[i]);
}
printf("\n");
for (i = 0; i < 20; i++)
{
printf("%d ", data2[i]);
}
printf("\n");
for (i = 0; i < 20; i++)
{
printf("%d ", data3[i]);
}
printf("\n");
}
int radix_sort(int data[], int max_index, int max_number)
{
int number[10];
int lsd, i, k, j, n;
n = 1;
memset(number, 0, sizeof(number));
while (n <= max_number)
{
for (i = 0; i < max_index; i++)
{
lsd = (data[i]/n) % 10;
sort[lsd][number[lsd]] = data[i];
number[lsd]++;
}
k = 0;
for (i = 0; i < 10; i++)
{
if(number[i] != 0)
{
for (j = 0; j < number[i];j++)
{
data[k] = sort[i][j];
k++;
}
number[i] = 0;
}
}
n *= 10;
}
return 0;
}
static int range_rand(int min, int max)
{
double r = 0;
int i;
double mul = 1;
for (i = 0; i < 3; i++)
{
mul *= 0.0001;
r += (rand() % 10000) * mul;
}
//0 - 1 中的一个随机数
return (int)(r * (max - min)) + min;
}
我用了500万数据进行测试，在我电脑上的运行结果是：
你会发现C++ stl 里面的sort 是最快的（没有函数调用的损失）。radix sort 和 qsort 性能差不多。所以，在某个数字可能很大的时候，上面的这个算法没有任何性能上的优势，还会浪费非常多的内存。
基数排序大多数情况下面只适用于下面的情景，一组数，这组数的最大值不是很大，更加准确的说，是要排序的对象的数目 和 排序对象的最大值之间相差不多。比如，这组数 1 4 5 2 2，要排序对象的数目是 5 ，排序对象的最大值也是 5. 这样的情况很适合。我们原来的排序的数，默认是以10为基数，现在，这个改进算法是这样的，我以最大的那个数为基数，这样，所有的数都是“个位数”，问题就简单了。
说了这样多，我觉得还是用程序来表达比较的清晰：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <algorithm>
#define MAX_N 5000000
int sort[10][MAX_N];
int quick_radix_sort[MAX_N];
int data[MAX_N];
int data2[MAX_N];
int data3[MAX_N];
int data4[MAX_N];
int qradix_sort(int data[], int max_index);
int radix_sort(int data[], int max_index, int max_number);
static int range_rand(int min, int max);
int intcmp(const void *a, const void *b)
{
return *((int *)a) - *((int *)b);
}
int main()
{
int i;
int max = -1;
clock_t t;
//初始化随机数种子
srand ( time(NULL) );
for (i = 0; i < MAX_N; i++)
{
data[i] = range_rand(1, MAX_N - 1);
if (max < data[i]) max = data[i];
}
memcpy(data2, data, sizeof(data));
memcpy(data3, data, sizeof(data));
memcpy(data4, data, sizeof(data));
t = clock();
qsort(data, MAX_N, sizeof(int), intcmp);
printf("qsort cost : %d \n", clock() - t);
t = clock();
radix_sort(data2, MAX_N, max);
printf("radix cost : %d \n", clock() - t);
t = clock();
std::sort(data3, data3 + MAX_N);
printf("std::sort cost : %d \n", clock() - t);
t = clock();
qradix_sort(data4, MAX_N);
printf("quick radix sort cost : %d \n", clock() - t);
for (i = 0; i < 20; i++)
{
printf("%d ", data[i]);
}
printf("\n");
for (i = 0; i < 20; i++)
{
printf("%d ", data2[i]);
}
printf("\n");
for (i = 0; i < 20; i++)
{
printf("%d ", data3[i]);
}
printf("\n");
for (i = 0; i < 20; i++)
{
printf("%d ", data4[i]);
}
printf("\n");
}
int qradix_sort(int data[], int max_index)
{
int i, j, n = 0;
for (i = 0; i < max_index; i++)
{
quick_radix_sort[data[i]]++;
}
for (i = 0; i < max_index; i++)
{
for (j = 0; j < quick_radix_sort[i]; j++)
{
data[n++] = i;
}
}
return 0;
}
int radix_sort(int data[], int max_index, int max_number)
{
int number[10];
int lsd, i, k, j, n;
n = 1;
memset(number, 0, sizeof(number));
while (n <= max_number)
{
for (i = 0; i < max_index; i++)
{
lsd = (data[i]/n) % 10;
sort[lsd][number[lsd]] = data[i];
number[lsd]++;
}
k = 0;
for (i = 0; i < 10; i++)
{
if(number[i] != 0)
{
for (j = 0; j < number[i];j++)
{
data[k] = sort[i][j];
k++;
}
number[i] = 0;
}
}
n *= 10;
}
return 0;
}
static int range_rand(int min, int max)
{
double r = 0;
int i;
double mul = 1;
for (i = 0; i < 3; i++)
{
mul *= 0.0001;
r += (rand() % 10000) * mul;
}
//0 - 1 中的一个随机数
return (int)(r * (max - min)) + min;
}
这个代码其实就是在上面的测试代码的基础上加上了一个qradix_sort 函数，这个函数非常的简单：
int qradix_sort(int data[], int max_index)
{
int i, j, n = 0;
for (i = 0; i < max_index; i++)
{
quick_radix_sort[data[i]]++;
}
for (i = 0; i < max_index; i++)
{
for (j = 0; j < quick_radix_sort[i]; j++)
{
data[n++] = i;
}
}
return 0;
}
循环体里面就两句话，和我们前面的那个基数排序不是很一样，这里，已经不用一个二维数组保存排序的数字了，只是标记一下这个数字有几个，因为，下标其实就是被排序的数字。
重新排序这个循环也很简单，仔细冥想一下怎么回事，不懂就在草稿纸上画画草图吧。这里主要的思想还是，下标就是排序的数字。
最后的排序测试结果：
我们发现，现在普通的radix性能也提高了，因为，现在数字变小了，循环的次数也变少了。快速基数排序的性能提高还是非常的明显。普通基数排序的两倍，std::sort 的3倍，qsort的 5倍，最重要的是代码非常的简单，基本上是你见过的最简单的一个排序了。
对一个真正的程序员来说，很少这样要死抠一个程序的性能，一般情况下，也是得不偿失。只有，在某个东西真正成了一个性能瓶颈的时候，我们才需要去关心一下：是不是可以这样改进一下。
这个排序算法，将来会应用到 字符串处理的倍增算法里面，这个倍增算法，要反复的进行排序。如果，排序能快一点，这个程序就能快很多。
相关推荐
基数排序基数排序基数排序基数排序基数排序
时间效率：待排序列为n个记录，10个关键码，关键码的取值范围为0-9，则进行链式基数排序的时间复杂度为O(4(n+10))，其中，一趟分配时间复杂度为O(2（n+10)，一趟收集时间复杂度为O(2（n+10)，共进行2趟分配和收集。
数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序
数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序
基数排序过程及程序基数排序过程及程序基数排序过程及程序基数排序过程及程序
基数排序(radix sort)又称桶排序（bucket sort），相对于常见的比较排序，基数排序是一种分配式排序，需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序，这种方法不需要进行比较操作。 为了尽可能少的...
基数排序法用链表完成使用C语言适用于刚入门的学者
基数排序C语言实现
算法导论之基数排序，桶排序。基数排序是利用在各个位上进行计数排序，是一种线性排序
插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
基数排序算法 java实现 还有基数排序的原理文档
这边所要介绍的「基数排序法」（radix sort）则是属于「分配式排序」（distribution sort），基数排序法又称「桶子法」（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些「桶...
排序算法中的基数排序，更重要的是会算时间复杂度,基数排序可以说是以计数排序位基础的，只不过变成了一位一位来或者一个字节一个字节来，每位或者每个字节都过了一遍，则排序完毕。很简单的程序，在code::block IDE...
Radix Sort （基数排序）排序算法
基数排序算法，这是分不错的算法，实现起来有点难，用静态链表实现，每次改变结点的指向，希望有用，多多指教
网上的一些基数排序都是用链表的，写了个非链表的例子
基数排序
常用排序效率PK 冒泡 快排 选择排序 基数排序 希尔排序 折半插入排序 等
排序算法很多，下面有基数排序，堆排序，希尔排序，直接插入排序的代码和思路
每行输出每趟每次分配收集后排序的结果，数据之间用一个空格分隔 Sample Input 10 278 109 063 930 589 184 505 069 008 083 Sample Output 930 063 083 184 505 278 008 109 589 069 505 008 109 930 063 069 278...