Biegral Blog

      计数排序思想很美妙，不需要进行元素间大小的比较，时间复杂度是线性的，在实践中，经常采用计数排序，该排序稳定。计数排序要求元素大小限定在一定范围内，比如[0, k]， 算法代码如下：

#include<iostream>
using namespace std;

// 0 <= a[i] <= k (其中i = 0, 1, 2,..., n-1)
void countSort(int a[], int n, int k)
{
	int *c = new int[k + 1]; //用于计数
	int *b = new int[n];     //用于保存最终结果

	int i;
	for(i = 0; i <= k; i++)  //勿忘置0
		c[i] = 0;

	for(i = 0; i < n; i++)	 //单独计数
		c[a[i]]++;

	for(i = 1; i <= k; i++)  //累加计数
		c[i] += c[i - 1];

	for(i = 0; i < n; i++)   //a[i]归位
		b[--c[a[i]]] = a[i];  //--是必要的
	
	for(i = 0; i < n; i++)   //保存结果
		a[i] = b[i];

	delete [] b;
	delete [] c;
}

int main()
{
	int a[] = {0, 1, 5, 3, 2, 2, 3, 0, 2, 6};
	int n = 10;
	int k = 6;

	countSort(a, n, k);
	
	int i;
	for(i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;

	return 0;
}