学步园

一段线性时间的排序程序：

排序中我们都知道，在一般情况下最好的时间复杂度是n*log(n)的时间复杂度，但是对于很多情况下，我们的数值范围是有限的，所以可以采用技术排序的方式将实际应用从这个时间复杂度减少到O（n）级别：

A表示原始数据，C表示统计个数，B表示排序后的数据，k表示数值的最大范围，l表示数据个数。

int CountSort(int A[],int B[],int k,int l)
{
	int *C = new int[k];
	for (int i = 0; i <k; i++)
	{
		C[i]=0;
	}
	for (int j = 0; j < l; j++)
	{
		C[A[j]] +=1;
	}
	for (int i = 1; i < k; i++)
	{
		C[i]= C[i]+C[i-1];
	}
	cout<<endl;
	for (int j = l-1; j >=0; j--)
	{
		B[C[A[j]]-1]=A[j];
		C[A[j]]=C[A[j]]-1;
	}
	delete[]C;
	C=nullptr;


	return 0;
}

下面加入测试的代码：

int A[11]={2,2,3,4,5,6,7,8,9,0,1};
	int B[11];

	CountSort(A,B,10,11);

	for (int i = 0; i < 11; i++)
	{
		cout<<B[i]<<"\t";
	}
	cout<<endl;

O(∩_∩)O~ 这个小程序也很有爱！