[数据结构与算法]计数排序算法

int GetMax(int* list,int n)
{
	int max = list[0];
	for (int i = 1; i < n; i++)
	{
		if (list[i] > max)
			max = list[i];
	}
	return max;
}

int GetMin(int* list, int n)
{
	int min = list[0];
	for (int i = 1; i < n; i++)
	{
		if (list[i] < min)
			min = list[i];
	}
	return min;
}

void CountingSort(int* list,int n)
{
	int max = GetMax(list, n);
	int min = GetMin(list, n);
	int* count = (int*)malloc(sizeof(int) * (max -min+ 1));
	int* output = (int*)malloc(sizeof(int) * n);
	if (!count||!output)
	{
		printf("失败");
		exit(-1);
	}
	for (int i = 0; i < max - min + 1; i++)
	{
		count[i] = 0;
	}
	
	for (int i = 0; i < n; i++)
	{
		count[list[i]-min]++;
	}
	for (int j = 1; j <=max -min; j++)
	{
		count[j] += count[j - 1];
	}
	for (int k = n - 1; k >= 0; k--)
	{
		output[count[list[k]-min]-1] = list[k];
		count[list[k]-min]--;
	}
	for (int i = 0; i < n; i++)
	{
		list[i] = output[i];
	}
}