计数排序

思想

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。

计数排序对输入的数据有附加的限制条件：

1、输入的线性表的元素属于有限偏序集S；

2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。

在这两个条件下，计数排序的复杂性为O(n)

代码：

#pragma once

//在范围中排序
void CountSortBetMaxAndMin(int *a, int min, int max,int size)
{
	int gap = max - min + 1;
	int *temparray = new int[gap];
	memset(temparray,0,sizeof(int)*(gap+1));

	for (int count = 0; count < size; ++count)
	{
		temparray[a[count]]++;
	}


	//temparray是一个
	int index = 0;
	for (int i = min; i < size; ++i)
	{
		while (temparray[i] != 0)
		{
			a[index++] = i;
			temparray[i]--;
		}
	}
}


//计数排序
void CountSort(int *a,int size)
{
	//找一个范围 即就是数组的元素的最大和最小值
	int max = a[0];  //最大
	int min = a[0];  //最小

	for (int i = 1; i < size; ++i)
	{
		if (a[i] > max)
		{
			max = a[i];
		}

		else if (a[i] < min)
		{
			min = a[i];
		}
	}

	//在这个范围中计数排序
	CountSortBetMaxAndMin(a, min, max,size);
}