算法把一个数字每一位当作一个基数进行排序，从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后， 数列就变成一个有序序列。每个基数的排序使用计数排序。
#include#include int max_bit(int a[], int size) /* get the max bit of number */ { int i, max, b; for (i = 1, max = a[0]; i < size; i++) { if (a[i] > max) { max = a[i]; } } b = 1; while (max / 10) { b++; max /= 10; } return b; } void radix_sort(int a[], int size) { int d = max_bit(a, size); int i, j, k, range, radix; int *c, *b; range = 10; /* for counting sort, the range of every bit is 0 - 9 */ radix = 1; c = (int *)malloc(sizeof(int) * range); b = (int *)malloc(sizeof(int) * size); for (i = 0; i < d; i++, radix *= 10) { /* use counting sort */ /* clear count before every sort */ for (j = 0; j < range; j++) { c[j] = 0; } /* c[k] content the num of elements which equal to k */ for (j = 0; j < size; j++) { k = (a[j] / radix) % 10; c[k]++; } /* c[j] content the num of elements which equal or less than j */ for (j = 1; j < range; j++) c[j] += c[j-1]; /* put a[j] into the space of b[c[k] - 1] */ for (j = size - 1; j >= 0; j--) { k = (a[j] / radix) % 10; b[c[k] - 1] = a[j]; c[k]--; } /* copy the 'sorted' list to a[j] */ for (j = 0; j < size; j++) a[j] = b[j]; } free(c); free(b); } main() { int a[] = {329, 457, 657, 839, 436, 720, 355}, i; int size = sizeof(a) / sizeof(int); radix_sort(a, size); for (i = 0; i < size; i++) printf("%d ", a[i]); }
Reference
[1].http://blog.csdn.net/houapple/article/details/6480042