嗨，欢迎来到异星球，我是小怪同志。这篇文章主要讲认识算法，请一起学习吧。

一、基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

二、代码实现

include<stdio.h>

define MAX 20

//#define SHOWPASS

define BASE 10

void print(int *a, int n) {
int i;
for (i = 0; i < n; i++) {

printf("%d\t", a[i]);

}
}

void radixsort(int *a, int n) {
int i, b[MAX], m = a[0], exp = 1;

for (i = 1; i < n; i++) {

if (a[i] > m) {
  m = a[i];
}

}

while (m / exp > 0) {

int bucket[BASE] = { 0 };

for (i = 0; i < n; i++) {
  bucket[(a[i] / exp) % BASE]++;
}

for (i = 1; i < BASE; i++) {
  bucket[i] += bucket[i - 1];
}

for (i = n - 1; i >= 0; i--) {
  b[--bucket[(a[i] / exp) % BASE]] = a[i];
}

for (i = 0; i < n; i++) {
  a[i] = b[i];
}

exp *= BASE;

ifdef SHOWPASS

printf("\nPASS   : ");
print(a, n);

endif

}
}

int main() {
int arr[MAX];
int i, n;

printf("Enter total elements (n <= %d) : ", MAX);
scanf("%d", &n);
n = n < MAX ? n : MAX;

printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++) {

scanf("%d", &arr[i]);

}

printf("\nARRAY : ");
print(&arr[0], n);

radixsort(&arr[0], n);

printf("\nSORTED : ");
print(&arr[0], n);
printf("\n");

return 0;
}