计数排序实现及比较

计数排序利用的是数组的随机访问特性，将要排序的数k转换成数组的下标K，该数组中以k为下标的值A[k]代表这个数K的个数。这种排序非常快，但应用条件比较苛刻。

主要受需要排序的序列规模（n),序列最大值(max(n))影响，如果max(n)过大，算法空间复杂度比较高，也是该算法的一个制约因素。下面是两种方式实现:

1) 第一种方式速度比第2种快，但没有稳定性，而且不能用于基数计数排序。

private void CountSort(int[] A)
{
List<int> theC = new List<int>();
int theLen = A.Length;
int theMaxVal = 0;
for (int i = 0; i < theLen; i++)
{
if (A[i] > theMaxVal)
{
theMaxVal = A[i];
AddLength(theC, theMaxVal);
}
theC[A[i]-1]++;
theCount++;
}
int j = 0;
for (int i = 0; i < theMaxVal; i++)
{
for (int k = 0; k < theC[i] - 1; k++)
{
A[j] = i + 1;
j++;
}
}
}

2）教科书里的算法，优点是具有稳定性，可用于基数计数排序。速度比前一种要慢些。时间约为2(n+k)
private int[] CountSort2(int[] A)
{
//用列表主要是可以动态增加长度.
List<int> theC = new List<int>();
int theLen = A.Length;
int[] theB = new int[theLen];
int theMaxVal = 0;
for (int i = 0; i < theLen; i++)
{
if (A[i] > theMaxVal)
{
theMaxVal = A[i];
AddLength(theC, theMaxVal);
}
theC[A[i]-1]++;
theCount++;
}
for (int i = 1; i < theMaxVal; i++)
{
theC[i] += theC[i - 1];
theCount++;
}

for (int i = theLen-1; i>=0; i--)
{
theB[theC[A[i] - 1]-1] = A[i];
(theC[A[i]-1])--;
theCount++;

}
return theB;
}
private void AddLength(List<int> C, int MaxLen)
{
int iLen = MaxLen - C.Count;
for (int i = 0; i < iLen; i++)
{
C.Add(0);
theCount++;
}
}

后记：计数算法适合序列元素比较集中，差值不大的情况。如果知道一个序列的最大值和最小值，而且最大值与最小值相差不是很大的情况，比较适合用这种排序。

字母排序，简单数字符号（0-9）排序等。