计数排序

淡淡的烟草味﹌ 2021-09-23 03:22 322阅读 0赞

**计数排序：**  
假设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();
        }
    }

运行结果