Java排序算法之計數排序如何實現

這篇文章主要為大家展示了“Java排序算法之計數排序如何實現”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“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排序算法之計數排序如何實現”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！