package linetimesort;  
    /** 
     * 計數(shù)排序假設(shè)n個輸入元素中的每一個都是介于0到k之間的某個整數(shù)，k為某個整數(shù)；它 
     * 通過確定小于等于一個數(shù)的數(shù)的個數(shù)來確定這個數(shù)應(yīng)該放在哪個位置 
     * @author yuncong 
     * 
     */  
    public class CountSort {  
        /** 
         *  
         * @param a 排序前的數(shù)組 
         * @param b 排序后的數(shù)組 
         * @param k 排序數(shù)組中最大元素的值 
         */  
        public void sort(int[] a, int[] b, int k){  
            // 創(chuàng)建數(shù)組c，并初始化  
            int[] c = new int[k + 1];  
            for (int i = 0; i < c.length; i++) {  
                c[i] = 0;  
            }  
            // 統(tǒng)計數(shù)組a中每個元素出現(xiàn)的次數(shù)  
            for (int i = 0; i < a.length; i++) {  
                c[a[i]]++;  
            }  
            /** 
             * 統(tǒng)計數(shù)組a中小于等于某一個數(shù)的數(shù)的個數(shù); 
             * 因為小于等于0的數(shù)的個數(shù)就是等于0的數(shù)的個數(shù)，所迭代從1開始 
             */  
            for (int i = 1; i < c.length; i++) {  
                c[i] = c[i] + c[i - 1];  
            }  
            for (int i = 0; i < a.length; i++) {  
                /** 
                 * 小于等于a[i]的數(shù)的個數(shù)為x就應(yīng)該將該數(shù)放在數(shù)組b的第x-1個位置， 
                 * 因為數(shù)組的下標(biāo)從0開始 
                 */  
                b[c[a[i]] - 1] = a[i];  
                /** 
                 * 下一個a[i]排在這個a[i]的前面; 
                 * 下一個a[i]排在前面的原因是前面為所有小于等于a[i]的數(shù)留足了空間 
                 */  
                c[a[i]]--;  
            }  
        }  
          
        public static void main(String[] args) {  
            int[] a = new int[]{3, 1, 14, 5, 6};  
            int[] b = new int[5];  
            new CountSort().sort(a, b, 14);  
            for (int i = 0; i < b.length; i++) {  
                System.out.println(b[i]);  
            }  
        }  
      
    }  

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。