#include <stdio.h>
#include <string.h>
/* 獲取輸入數(shù)字的索引值，dec指定數(shù)字的位數(shù)，3代表百位數(shù)，order指定需要獲取哪一位的索引，1代表個位，2代表十位，3代表百位 */
int get_index(int num, int dec, int order)
{
int i, j, n;
int index;
int div;
/* 根據(jù)位數(shù)，循環(huán)減去不需要的高位數(shù)字 */
for (i=dec; i>order; i--)
{
n = 1;
for (j=0; j<dec-1; j++)
n *= 10;
div = num/n;
num -= div * n;
dec--;
}
/* 獲得對應(yīng)位數(shù)的整數(shù) */
n = 1;
for (i=0; i<order-1; i++)
n *= 10;
/* 獲取index */
index = num / n;
return index;
}
/* 進(jìn)行基數(shù)排序 */
void radix_sort(int array[], int len, int dec, int order)
{
int i, j;
int index; /* 排序索引 */
int tmp[100]; /* 臨時數(shù)組，用來保存待排序的中間結(jié)果 */
int num[10]; /* 保存索引值的數(shù)組 */
memset(num, 0, 10*sizeof(int)); /* 數(shù)組初始清零 */
memset(tmp, 0, len*sizeof(int)); /* 數(shù)組初始清零 */
if (dec < order) /* 最高位排序完成后返回 */
return;
for (i=0; i<len; i++) {
index = get_index(array[i], dec, order); /* 獲取索引值 */
num[index]++; /* 對應(yīng)位加一 */
}
for (i=1; i<10; i++)
num[i] += num[i-1]; /* 調(diào)整索引數(shù)組 */
for (i=len-1; i>=0; i--) {
index = get_index(array[i], dec, order); /* 從數(shù)組尾開始依次獲得各個數(shù)字的索引 */
j = --num[index]; /* 根據(jù)索引計算該數(shù)字在按位排序之后在數(shù)組中的位置 */
tmp[j] = array[i]; /* 數(shù)字放入臨時數(shù)組 */
}
for (i=0; i<len; i++)
array[i] = tmp[i]; /* 從臨時數(shù)組復(fù)制到原數(shù)組 */
/* 繼續(xù)按高一位的數(shù)字大小進(jìn)行排序 */
radix_sort(array, len, dec, order+1);
}
int main(int argc, char *argv[])
{
int i;
int a[11] = {101,258, 976, 515, 337, 359, 701, 916, 494, 303, 175};
radix_sort(a, 11, 3, 3);
for (i=0; i<11; i++)
printf("%d ", a[i]);
printf("\n");
getchar();
return 0;
}