java 實現計數排序和桶排序實例代碼
目錄
比較和非比較的區別
常見的快速排序、歸并排序、堆排序、冒泡排序等屬于比較排序。在排序的最終結果里，元素之間的次序依賴于它們之間的比較。每個數都必須和其他數進行比較，才能確定自己的位置。
在 冒泡排序 之類的排序中，問題規模為n，又因為需要比較n次，所以平均時間復雜度為O(n²)。在 歸并排序、快速排序 之類的排序中，問題規模通過分治法消減為logN次，所以時間復雜度平均 O(nlogn) 。
比較排序的優勢是，適用于各種規模的數據，也不在乎數據的分布，都能進行排序。可以說，比較排序適用于一切需要排序的情況。
計數排序、基數排序、桶排序則屬于非比較排序。非比較排序是通過確定每個元素之前，應該有多少個元素來排序。針對數組arr，計算arr[i]之前有多少個元素，則唯一確定了arr[i]在排序后數組中的位置。
非比較排序只要確定每個元素之前的已有的元素個數即可，所有一次遍歷即可解決。算法時間復雜度 O(n) 。
非比較排序時間復雜度底，但由于非比較排序需要占用空間來確定唯一位置。所以對數據規模和數據分布有一定的要求。
計數排序
計數排序適用數據范圍
計數排序需要占用大量空間，它僅適用于數據比較集中的情況。比如 [0~100]，[10000~19999] 這樣的數據。
過程分析
計數排序的基本思想是： 對每一個輸入的元素arr[i]，確定小于 arr[i] 的元素個數。
所以可以直接把 arr[i] 放到它輸出數組中的位置上。假設有5個數小于 arr[i]，所以 arr[i] 應該放在數組的第6個位置上。
下面給出兩種實現：
算法流程（1）
需要三個數組:
待排序數組 int[] arr = new int[]{4,3,6,3,5,1};
輔助計數數組 int[] help = new int[max - min + 1]; //該數組大小為待排序數組中的最大值減最小值+1
輸出數組 int[] res = new int[arr.length];
1.求出待排序數組的最大值max=6， 最小值min=1
2.實例化輔助計數數組help，help數組中每個下標對應arr中的一個元素， help用來記錄每個元素出現的次數
3.計算 arr 中每個元素在help中的位置 position = arr[i] - min，此時 help = [1,0,2,1,1,1]; （3出現了兩次，2未出現）
4.根據 help 數組求得排序后的數組，此時 res = [1,3,3,4,5,6]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public static int[] countSort1(int[] arr){ if (arr == null || arr.length == 0) { return null; } int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; //找出數組中的最大最小值 for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } int help[] = new int[max]; //找出每個數字出現的次數 for(int i = 0; i < arr.length; i++){ int mapPos = arr[i] - min; help[mapPos]++; } int index = 0; for(int i = 0; i < help.length; i++){ while(help[i]-- > 0){ arr[index++] = i+min; } } return arr;} |
算法流程（2）
需要三個數組:
待排序數組 int[] arr = new int[]{4,3,6,3,5,1};
輔助計數數組 int[] help = new int[max - min + 1]; //該數組大小為待排序數組中的最大值減最小值+1
輸出數組 int[] res = new int[arr.length];
1.求出待排序數組的最大值max=6， 最小值min=1
2.實例化輔助計數數組help， help用來記錄每個元素之前出現的元素個數
3.計算 arr 每個數字應該在排序后數組中應該處于的位置，此時 help = [1,1,4,5,6,7];
4.根據 help 數組求得排序后的數組，此時 res = [1,3,3,4,5,6]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
public static int[] countSort2(int[] arr){ int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; //找出數組中的最大最小值 for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } int[] help = new int[max - min + 1]; //找出每個數字出現的次數 for(int i = 0; i < arr.length; i++){ int mapPos = arr[i] - min; help[mapPos]++; } //計算每個數字應該在排序后數組中應該處于的位置 for(int i = 1; i < help.length; i++){ help[i] = help[i-1] + help[i]; } //根據help數組進行排序 int res[] = new int[arr.length]; for(int i = 0; i < arr.length; i++){ int post = --help[arr[i] - min]; res[post] = arr[i]; } return res;} |
桶排序
網絡流傳桶排序算法勘誤
網絡各博文中流程的桶排序算法實際上都是計數排序，并非標準的桶排序。有問題的文章：
經典排序算法 - 桶排序Bucket sort
桶排序算法
排序算法 之 桶排序
最快最簡單的排序算法：桶排序
桶排序適用數據范圍
桶排序可用于最大最小值相差較大的數據情況，比如[9012,19702,39867,68957,83556,102456]。
但桶排序要求數據的分布必須均勻，否則可能導致數據都集中到一個桶中。比如[104,150,123,132,20000], 這種數據會導致前4個數都集中到同一個桶中。導致桶排序失效。
過程分析
桶排序的基本思想是： 把數組 arr 劃分為n個大小相同子區間（桶），每個子區間各自排序，最后合并 。
計數排序是桶排序的一種特殊情況，可以把計數排序當成每個桶里只有一個元素的情況。
1.找出待排序數組中的最大值max、最小值min
2.我們使用 動態數組ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲。桶的數量為(max-min)/arr.length+1
3.遍歷數組 arr，計算每個元素 arr[i] 放的桶
4.每個桶各自排序
5.遍歷桶數組，把排序好的元素放進輸出數組
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public static void bucketSort(int[] arr){ int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } //桶數 int bucketNum = (max - min) / arr.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList<Integer>()); } //將每個元素放入桶 for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } //對每個桶進行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); } System.out.println(bucketArr.toString()); } |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
