常用排序算法的实现（C语言版）-基数排序

基数排序：

#include <stdlib.h> 
#include "algosort.h"
/*被排序元素的最大位数，4则意味着只能排序< 10000 的数*/
#define WIDTH 4 
#define MAXK 10 

void radixSort(int a[], int n) {
	int i;
	void innerCountingSort(int a[], int n, int d);
	for (i = 0; i < WIDTH; i++) {
		innerCountingSort(a, n, i);
	}
}

void innerCountingSort(int a[], int n, int d) {
	int i, j, x, k[MAXK] = {0};
	int *ip = (int *)malloc(n * sizeof(int));
	int *bp = (int *)malloc(n * sizeof(int));
	int getDValue(int value, int d);
	for (i = 0; i < n; i++) {
		ip[i] = getDValue(a[i], d);
		k[ip[i]]++;
	}

	for (j = 1; j < MAXK; j++) {
		k[j] = k[j] + k[j-1];
	}

	for (i = n - 1; i >= 0; i--) {
		bp[k[ip[i]] - 1] = a[i];
		k[ip[i]]--;
	}

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

	free(ip);
	free(bp);
}

int getDValue(int value, int d) {
	for (;d > 0 && value > 0; d--) {
		value = value / MAXK;
	}
	return value % MAXK;
}