计数排序

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

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

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

[cpp] int CountSort(int A[],int B[],int k,int l)
{
int *C = new int[k];
for (int i = 0; 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< 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 CountSort(int A[],int B[],int k,int l)
{
int *C = new int[k];
for (int i = 0; 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< 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;
}
下面加入测试的代码：

[cpp] 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< }
cout<

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< }
cout< O(∩_∩)O~ 这个小程序也很有爱！