#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#include <memory.h>

void radix2(int* arr, int len, int k)
{
	k++;
	int* count_arr = (int*)malloc(sizeof(int)*k);
	for(int i = 0; i < k; i++)
	{
		count_arr[i] = 0;
	}
	for (int i = 0; i < len; i++)
	{
		count_arr[arr[i]]++;
	}
	for (int i = 1; i < k; i++)
	{
		count_arr[i] += count_arr[i-1];
	}
	for (int i = len-1; i >= 0; i--)
	{
		//a[i+1 ... len-1]的元素是已经确定最终位置的元素
		//求出arr[i]中元素的最终位置为j，如果i<j，则swap(a[i],a[j]),
		//继续寻找新arr[i]元素的最终位置，直到i>=j
		int j = count_arr[arr[i]] - 1;
		while (i < (j = count_arr[arr[i]] - 1))
		{
			int temp = arr[j];
			arr[j] = arr[i];
			arr[i] = temp;
			count_arr[arr[j]]--;
		}
	}
	free(count_arr);
}

int rand_int(int max)
{
	return (rand() % max);
}

void main()
{
	int a[100] = {0};
	int max = 20;
	srand(time(0));
	for (int i = 0; i < 100; i++)
	{
		a[i] = rand_int(max);
	}

	radix2(a, 100, max);
	for (int i = 0; i < 100; i++)
	{
		printf("%d ", a[i]);
	}
	getchar();
}