计数排序-蒲公英云

计数排序

计数排序：
假设n个输入元素中的每一个都是在0~区间内的一个整数，其中k为某个整数。当k=O(n)是，排序时间为O（n）.
基本思想：对每个输入元素x,确定小于x元素的个数。利用这一信息，可以直接把x放到输出数组的位置上。例如，有17个元素小于x，则x就应该在第18个输出位置上。
输入：数组A[1,n] 借助数组C[0，k]存放元素x的个数
输出：数组B[1,n]

COUNTING-SORT(A,B,k)
创建数组C[0,k]
初始化数组C[i]=0 
for i=0 to k
    C[i]=0
//C[i]为每个元素的个数
for j=1 to A.length
    C[A[j]]= C[A[j]]++;
//C[i]为每个比i小或等于i的元素个数
for i=1 to k
    C[i]=C[i]+C[i-1]
for j=A.length downto 1
    B[C[A[j]]]=A[j]
    C[A[j]]= C[A[j]]-1；

Java实现

import java.util.Random;
public class Main {
    private static int N=10;
    private static int k=20;
    static Random rand = new Random();
    //计数排序适用于数组中的最大数k==n
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        test_Counting_sort();
    }
    private static void test_Counting_sort() {
        // TODO Auto-generated method stub
        int[] A=new int[N];
        for(int i=0;i<A.length;i++){
            A[i]=rand.nextInt(k);
        }
        System.out.println("排序前：");
        print(A);
        int[] B=new int[N];
        Counting_Sort(A,B);
        System.out.println("排序后：");
        print(B);
    }
    private static void Counting_Sort(int[] A, int[] B) {
        // TODO Auto-generated method stub
        //注意：A中的每个元素均小于等于k
        int[] C=new int[k];
        //初始化C使得数组C的，每个元素初始值为0
        for(int i=0;i<C.length;i++){
            C[i]=0;
        }
        //C[i]为元素i的个数
        for(int i=0;i<A.length;i++){
            C[A[i]]++;
        }
        //C[i]为小于等于元素i的个数
        for(int i=1;i<C.length;i++){
            C[i]=C[i]+C[i-1];
        }
        //得到输出的元素B[i]
        for(int i=A.length-1;i>=0;i--){
            B[C[A[i]]-1]=A[i];//索引从0开始 故需要减1
            C[A[i]]--;
        }
    }
    // 打印数组
    private static void print(int[] A) {
        // TODO Auto-generated method stub
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + "\t");
        }
        System.out.println();
    }
}