基数排序（MSD、LSD）

#include 
#include 

void MSD_Sort(int s[], int left, int right, int d, int r);
void LSD_Sort(int s[], int left, int right, int D, int r);
int pow(int a, int b);

int main()
{
	int i;
	int s1[] = { 97, 53, 88,  59,  26,  41,  88,  31,  22 };
	int s2[] = { 97, 53, 88,  59,  26,  41,  88,  31,  22 };
	int n = 9, d = 2, r = 10;//n：9个数，d：2位， r：10进制

	MSD_Sort(s1, 0, n - 1, d, r);
	LSD_Sort(s2, 0, n - 1, d, r);
	for (i = 0; i < n; i++) {
		printf("%d ", s1[i]);
	}
	printf("n");
	for (i = 0; i < n; i++) {
		printf("%d ", s2[i]);
	}
	return 0;
}

int pow(int a, int b)
{
	if (b == 0) {
		return 1;
	}
	while (b != 1) {
		a *= a;
		b--;
	}
	return a;
}

void MSD_Sort(int s[], int left, int right, int d, int r) {
	int *count = new int [r];
	int i, n, k, kd;
	n = right - left + 1;
	k = pow(10, d - 1);

	for (i = 0; i < r; i++) {
		count[i] = 0;
	}//清零

	for (i = left; i < n + left; i++) {
		kd = (s[i] / k) % r;//第d位的数
		count[kd]++;
	}
	for (i = 1; i < r; i++) {
		count[i] = count[i] + count[i - 1];
	}//计数

	
	int *result = new int[n];
	for (i = n + left - 1; i >= left; i--) {
		kd = (s[i] / k) % r;
		count[kd]--;
		result[count[kd]] = s[i];
	}

	for (i = 0; i < n; i++) {
		s[i + left] = result[i];
	}//复制

	

	for (i = left; i < r - 1; i++) {
		if (d == 1)	break;

		left = count[i];
		right = count[i + 1] - 1;

		if (left < right)
		MSD_Sort(s, left, right, d - 1, r);
	}

	delete[]count;
	delete[]result;
}

void LSD_Sort(int s[], int left, int right, int D, int r)
{
	int i, n, k, d, kd;
	for (d = 0; d < D; d++) {
		n = right - left + 1;
		k = pow(10, d);
		int *count = new int[r];

		for (i = 0; i < r; i++) {
			count[i] = 0;
		}//清零

		for (i = left; i < n + left; i++) {
			kd = (s[i] / k) % r;//第d位的数
			count[kd]++;
		}
		for (i = 1; i < r; i++) {
			count[i] = count[i] + count[i - 1];
		}//计数

		int *result = new int[n];
		for (i = n + left - 1; i >= left; i--) {
			kd = (s[i] / k) % r;
			count[kd]--;
			result[count[kd]] = s[i];
		}

		for (i = 0; i < n; i++) {
			s[i + left] = result[i];
		}//复制

				
		delete[]count;
		delete[]result;
	}
	
}