计数排序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;}}