排序算法（七）非比较排序：计数排序、基数排序、桶排序

             1
            public
            static
            void countSort(int[] array, int downBound, int upperBound) {  
 2int[] countArray = newint[upperBound - downBound + 1];  
 3if (upperBound < downBound)  
 4return;  
 5for (int i = 0; i < array.length; i++) {  
 6         countArray[array[i] - downBound]++;  
 7    }  
 8int posSum = 0;  
 9for (int i = 0; i < upperBound - downBound + 1; i++) {  
10         posSum += countArray[i];  
11         countArray[i] = posSum;  
12    }  
13int[] result = newint[array.length];  
14for (int i = array.length - 1; i >= 0; i--) {  
15         result[countArray[array[i] - downBound] - 1] = array[i];  
16         countArray[array[i] - downBound]--;  
17    }  
18for (int i = 0; i < array.length; i++) {  
19         array[i] = result[i];  
20    }  
21 }  

             1
            public
            static
            void bucketSort(int[] arr){  
 2 3int max = Integer.MIN_VALUE;  
 4int min = Integer.MAX_VALUE;  
 5for(int i = 0; i < arr.length; i++){  
 6         max = Math.max(max, arr[i]);  
 7         min = Math.min(min, arr[i]);  
 8    }  
 910//桶数  11int bucketNum = (max - min) / arr.length + 1;  
12     ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);  
13for(int i = 0; i < bucketNum; i++){  
14         bucketArr.add(new ArrayList<Integer>());  
15    }  
1617//将每个元素放入桶  18for(int i = 0; i < arr.length; i++){  
19int num = (arr[i] - min) / (arr.length);  
20        bucketArr.get(num).add(arr[i]);  
21    }  
2223//对每个桶进行排序  24for(int i = 0; i < bucketArr.size(); i++){  
25        Collections.sort(bucketArr.get(i));  
26    }  
27 ｝     

             1
            public
            static
            void radixSort(int[] array, int maxDigit) {  
 2int len = array.length;  
 3int digitCount = 1;  
 4int digitDev = 1;  
 5int[] tmp = newint[len];  
 6int[] count = newint[10];  
 7while (digitCount <= maxDigit) {  
 8         Arrays.fill(count, 0);  
 9         Arrays.fill(count, 0);  
10for (int i = 0; i < len; i++) {  
11             count[(array[i] / digitDev) % 10]++;  
12        }  
13int sum = 0;  
14for (int i = 1; i < 10; i++) {  
15             count[i] = count[i] + count[i - 1];  
16        }  
17for (int i = len - 1; i >= 0; i--) {  
18             tmp[count[(array[i] / digitDev) % 10] - 1] = array[i];  
19             count[(array[i] / digitDev) % 10]--;  
20        }  
21for (int i = 0; i < len; i++) {  
22             array[i] = tmp[i];  
23        }  
24         digitDev *= 10;  
25         digitCount++;  
26    }  
27 }