Java 十大排序算法之計數排序刨析
計數排序是非比較的排序算法,用輔助數組對數組中出現的數字計數,元素轉下標,下標轉元素
計數排序優缺點
優點:快
缺點:數據范圍很大,比較稀疏,會導致輔助空間很大,造成空間的浪費
使用范圍:數據較為密集或范圍較小時適用。
思路
1.找出最大元素max
2.初始化一個max+1的數組
3.將每個元素的計數存儲在數組中各自的索引處
4.存儲計數數組元素的累積和
5.數組中找到原始數組的每個元素的索引
計數排序代碼實現
public class CountingSort { private static int[] countingSort(int[] arr) { //1、求取最大值和最小值,計算中間數組的長度:中間數組是用來記錄原始數據中每個值出現的頻率 int min = arr[0], max = arr[0]; for (int i : arr) { if (i > max) { max = i; } if (i < min) { min = i; } } //2、有瞭最大值和最小值能夠確定中間數組的長度 //例如存儲 5-0+1=6 int[] countArray = new int[max - min + 1]; //3、循環遍歷舊數組計數排序: 就是統計原始數組值出現的頻率到中間數組B中 for (int i : arr) { countArray[i - min] += 1; //數的位置上+1 } //4、統計數組做變形,後邊的元素等於前面的元素之和 for (int i = 1; i < countArray.length; i++) { countArray[i] += countArray[i - 1]; } //5、倒序遍歷原始數組,從統計數組中找到正確的位置,輸出到結果數組 int[] resultArray = new int[arr.length]; for (int i = arr.length - 1; i >= 0; i--) { //給resultArray的當前位置賦值 resultArray[countArray[arr[i] - min] - 1] = arr[i]; //給countArray的位置的值-- countArray[arr[i] - min]--; } return resultArray; } public static void main(String[] args) { int[] arr = {1,28,3,21,11,7,6,18}; int[] sortedArr = countingSort(arr); System.out.println(Arrays.toString(sortedArr)); } }
時間復雜度:O(n+k)
到此這篇關於Java 十大排序算法之計數排序刨析的文章就介紹到這瞭,更多相關Java 計數排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!