计数排序Java兑现

计数排序Java实现

计数排序的下界优于任意一个比较排序算法。它是一个不需要比较两个元素大小的排序算法。

计数排序在百度百科中有详细的介绍http://baike.baidu.com/view/1209480.htm。

这里编写了计数排序的Java版本：

	public static void main(String args[])
	{
		int[] a = new int[] { 2,5,3,0,2,3,0,3 };
		int[] b = new int[8];
		CountSort(a, b, 6);
		for (int i = 0; i < 8; i++)
		{
			System.out.print(b[i] + " ");
		}
	}

	private static void CountSort(int a[], int b[], int k)
	{
		//初始化计数数组
		int c[] = new int[k];
		for(int i = 0; i<k; i++)
			c[i] = 0;
		//计算数组中重复的次数
		for(int i=0; i<a.length; i++)
		{
			c[a[i]] = c[a[i]]+1;
		}
		for(int i = 1; i<k; i++)
		{
			c[i] = c[i]+c[i-1];
		}
		//将a数组中的元素按照顺序复制到b中
		for(int i = a.length-1; i>=0; i--)
		{
			b[c[a[i]]-1] = a[i];
			c[a[i]] = c[a[i]]-1;
		}
	}