算法总结系列之三 : 计数排序(CountingSort

计数排序, 基数排序, 桶排序等非比较排序算法,平均时间复杂度都是O(n). 这些排序因为其待排序元素本身就含有了定位特征,因而不需要比较就可以确定其前后位置,从而可以突破比较排序算法时间复杂度O(nlgn)的理论下限.

计数排序是最简单的特例,它要求待排序元素是位于0到k之间的正整数, 因而它是很特殊的情况,基本上没有特别的应用价值; 但是另一方面, 它又是基数排序的基础,或者说是一部分,所以简单的描述一下:

输入数组 A : 元素特征是 0-k的正整数,可以有重复值;

输出数组 B : 输出A的一个非减序列

中间数组 C : 大小是k, 它的i( 0<= i <= k)索引位置存储的是A元素集合中值是k的元素的个数有关.

算法的基本思想是:

• 统计A中元素的值的集合, 以A中元素的值为索引, 将值的个数填写到中间数组C的对应处.
• 对C从头开始自累加, 这样C中存储的就是, 当输入数组A中的值为当前索引时, 它前面的元素数量(包含重复元素).
• 将C依次输出到输出数组中.

算法的C#实现是:

note: 该算法对上述思想做了稍微的修改, 考虑到数组起始坐标是0, 所以中间数组的大小修正为 k+1

/// <summary>

/// counting sort

/// </summary>

/// <param name="arrayA">input array</param>

/// <param name="arrange">the value arrange in input array</param>

/// <returns></returns>

public static int[] CountingSort(int[] arrayA, int arrange)

{

//array to store the sorted result, 

//size is the same with input array.

int[] arrayResult = new int[arrayA.Length];

//array to store the direct value in sorting process

//include index 0;

//size is arrange+1;

int[] arrayTemp = new int[arrange+1];

//clear up the temp array

for(int i = 0; i <= arrange; i++)

{

arrayTemp[i] = 0;

}

//now temp array stores the count of value equal

for(int j = 0; j < arrayA.Length; j++)

{

arrayTemp[arrayA[j]] += 1;

}

//now temp array stores the count of value lower and equal

for(int k = 1; k <= arrange; k++)

{

arrayTemp[k] += arrayTemp[k - 1];

}

//output the value to result

for (int m = arrayA.Length-1; m >= 0; m--)

{

arrayResult[arrayTemp[arrayA[m]] - 1] = arrayA[m];

arrayTemp[arrayA[m]] -= 1;

}

return arrayResult;

}

简单的测试程序:

static void Main(string[] args)

{

int[] ary = new int[]{ 2, 3, 3, 5, 4, 7, 4 };

int[] res = CountingSort(ary, 7);

foreach(int vr in res)

{

Console.Write(vr.ToString() + " ");

}

Console.ReadLine();

}

欢迎指正.

作者：Jeffrey Sun
出处：http://sun.cnblogs.com/
本文以“现状”提供且没有任何担保，同时也没有授予任何权利。本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。