算法導論之計數排序

1.計數排序是一種非常快捷的穩定性強的排序方法，時間複雜度O(n+k),其中n為要排序的數的個數，k為要排序的數的組大值。計數排序對一定量的整數排序時候的速度非常快，一般快于其他排序算法。但計數排序局限性比較大，隻限于對整數進行排序。計數排序是消耗空間複雜度來擷取快捷的排序方法，其空複雜度為O（K）同理K為要排序的最大值。

2.計數排序的基本思想為一組數在排序之前先統計這組數中其他數小于這個數的個數，則可以确定這個數的位置。例如要排序的數為 7 4 2 1 5 3 1 5；則比7小的有7個數，所有7應該在排序好的數列的第八位，同理3在第四位，對于重複的數字，兩個1分别排在第1位和第2位（暫且認為第一個1比第二個1小），兩個5同理排在第6位和第7位。

3.計數排序的實作辦法：

　　首先需要三個數組，第一個數組input Arr，第二個數組記錄比某個數小的數字的個數是以第二個數組的大小應當為K（數列中最大數的大小），第三個數組output Arr。

　　接着需要确定數組最大值并确定B數組的大小。并對每個數由小到大的記錄數列中每個數的出現次數。因為是有小到大通過出現次數可以通過前面的所有數的出現次數來确定比這個數小的數的個數，進而确定其位置。

　　對于重複的數，每排好一個數則對其位置數進行減減操作，以此對完成其餘相同的數字進行排位。

計數排序的要求是每個輸入的元素必須是小于k的整數。

//A是input，B是output，C的length是k
//這裡找出最大的是k，但是數組C【k】越界，是以這裡我們在排序的時候讓K+1，剛好就C【0】到C【k】了
//C中記錄的是比某個元素小的數字的個數，C中的坐标就是A中元素的值
//這裡是以待排序的數字必須比k小
//C[A[j]]表示小于等于A[j]的元素的個數，也就是排完序之後的該元素的位置
public class CountSort {

    int toFindk(int A[]){//找出A【】中最大元素k
        int max=A[0];
        for(int i=1;i<A.length;i++){
            if(A[i]>max){
                max=A[i];
            }
        }
        return max;
    }


    void countingSort(int A[],int B[],int k){//這裡的k是以前的K+1因為countSort.countingsort(A, B, k+1);
        int C[]=new int[k];
        for(int i=0;i<k;i++){
            C[i]=0;
        }

        for(int j=0;j<A.length;j++){
            C[A[j]]=C[A[j]]+1;//把A中的數值轉化為C中對應位置的個數，C就是統計A中相等的元素存儲在c中
        }

        for(int j=1;j<k;j++){
            C[j]=C[j]+C[j-1];//小于等于j的元素的個數
        }

        for(int j=A.length-1;j>=0;j--){
            B[C[A[j]]-1]=A[j];//注意這裡要減1，C[A[j]]表示小于等于A[j]的元素的個數，也就是排完序之後的目前元素A[j]的位置
            C[A[j]]=C[A[j]]-1;
        }
    }

    public static void main(String[] args){
        int A[]={2,5, 3,0,2,3,0,3};
        int B[]=new int[A.length] ;
        int k;
        CountSort countSort=new CountSort();
        k=countSort.toFindk(A);
        countSort.countingSort(A, B, k+1);
        for(int i=0;i<B.length;i++){
            System.out.print(B[i]+"   ");
        }
    }
}