排序算法之计数排序

计数排序，顾名思义，就是把要排序的元素都一一计数，某个数值如果总共有10个相同的，该元素对应的个数就记为10；总共有5个相同的，就记为5...

在当待排序数组内有大量重复的数值并且这些数值较为集中时，使用计数排序就有很明显的优势了。

计数排序的主要思想是，对N个数据集进行排序，每个数据值的范围固定在[0,k），而k远远小于N，创建了k个代表[0,k)中每个值ki的有序的盒子，每个盒子存储待排序数列中与ki值相等的元素出现的次数。

其中，k=排序数组中最大值 - 最小值 + 1。

计数排序将对输入数列进行两次遍历：第1次遍历，主要是统计每个数的数量；第2次遍历，是通过处理桶中得到的全序的计数值，重写原始的数列。

其实原理非常简单，举一个例子，要对无序序列：10 , 6 , 7 , 11 , 9 , 8 ,  7 , 10 , 8 , 11 , 7 进行排序。

我先找出最大值max为11，最小值min为6，然后k=11-6+1=6，再定义一个长度为k的数组Array。

元素Array[0]表示6的个数，那么Array[0]＝1；

元素Array[1]表示7的个数，那么Array[1]＝3；

元素Array[2]表示8的个数，那么Array[2]＝2；

元素Array[3]表示9的个数，那么Array[3]＝1；

元素Array[4]表示10的个数，那么Array[4]＝2；

元素Array[5]表示11的个数，那么Array[5]＝2。

然后我利用Array这个数组，对原本的无序序列进行重写，按照Array里的数据，排序后的序列应该为：

1个6，然后3个7，然后2个8，然后1个9，然后2个10，然后2个11。

也就是：6，7，7，7，8 ，8，9，10，10，11，11。

这就是所谓的计数排序啦！是不是感觉很简单呢？

我们来总结一下步骤：

1. 找出待排序数组中的最大值和最小值（分别用max和min表示）；
2. 从min到max，统计序列中每个值的出现次数，存入到一个长度为k=max-min+1的数组Array中，其中Array[i]表示i+min出现的次数；
3. 反向填充目标数组，根据Array里的数据反向修改序列里的值，意思是从Array[0]到Array[k-1]，分别把Array[i]个  min+i  替换入原无序序列中。

下面是具体的算法实现：

#include<iostream>
#include<cstdlib>
using namespace std;


template<class T>void countingSort(T* Arr,int n)
{
	int i,k,idx=0;   
	//k是表示数组temp_Array的长度的，该数组用于记录每个数值的个数
	//idx是反向填充目标数组时，用来记录位置的 
	T max=Arr[0],min=Arr[0];
	for(i=0;i<n;i++)
	{
		//目的是为了找出最大值max和最小值min 
		if(Arr[i]>max)
		{
			max=Arr[i];
		}
		else if(Arr[i]<min)
		{
			min=Arr[i];
		}
	}
	
	k=max-min+1; 
	int *temp_Array=(int*)malloc(sizeof(int)*k);
	//以上是为了申请一块空间，用来存储数组temp_Array 
	
	
	for(i=0;i<k;i++)
	{
		//初始化数组 
		temp_Array[i]=0;
	}
	for(i=0;i<n;i++)
	{
		//用temp_Array数组记录每个值的个数 
		temp_Array[Arr[i]-min]++;
	}
	
	for(i=0;i<k;i++)
	{
		//此for循环用于反向填充数组
		while(temp_Array[i]>0)
		{
			//while循环的作用是填写temp_Array[i]个 i+min 
			Arr[idx]=i+min;
			idx++;
			temp_Array[i]--;
		}
	}
	free(temp_Array);   //释放该空间 
} 


int main()
{
	int data[]={11,15,14,12,14,13,12,10,16,11,15,16,14,13,10,11,10};
	int length=sizeof(data)/sizeof(int);
	cout<<"待排序数据为："<<endl;
	for(int i=0;i<length;i++)
	{
		cout<<data[i]<<" ";
	}
	
	cout<<endl<<"排序后的数据为："<<endl;
		
	countingSort(data,length);   //计数排序 
	for(int i=0;i<length;i++)
	{
		cout<<data[i]<<" ";
	}
	cout<<endl;
	
	return 0;	
}