計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。 作為一種線性時間復(fù)雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

計數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法。計數(shù)排序使用一個額外的數(shù)組C，其中第i個元素是待排序數(shù)組A中值等于i的元素的個數(shù)。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。它只能對整數(shù)進行排序。

算法描述

• 找出待排序的數(shù)組中最大和最小的元素；
• 統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項；
• 對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）；
• 反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1。

動圖演示

代碼實現(xiàn)

下面的排序算法統(tǒng)一使用的測試代碼如下，源碼GitHub鏈接

public static void main(String[] args) {int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};// 只需要修改成對應(yīng)的方法名就可以了countingSort(array);System.out.println(Arrays.toString(array)); }/*** Description: 計數(shù)排序** @param array* @return void* @author JourWon* @date 2019/7/11 23:42*/ public static void countingSort(int[] array) {if (array == null || array.length <= 1) {return;}int length = array.length;int max = array[0];int min = array[0];for (int i = 0; i < length; i++) {if (max < array[i]) {max = array[i];}if (min > array[i]) {min = array[i];}}// 最大最小元素之間范圍[min, max]的長度int offset = max - min + 1;// 1. 計算頻率，在需要的數(shù)組長度上額外加1int[] count = new int[offset + 1];for (int i = 0; i < length; i++) {// 使用加1后的索引，有重復(fù)的該位置就自增count[array[i] - min + 1]++;}// 2. 頻率 -> 元素的開始索引for (int i = 0; i < offset; i++) {count[i + 1] += count[i];}// 3. 元素按照開始索引分類，用到一個和待排數(shù)組一樣大臨時數(shù)組存放數(shù)據(jù)int[] aux = new int[length];for (int i = 0; i < length; i++) {// 填充一個數(shù)據(jù)后，自增，以便相同的數(shù)據(jù)可以填到下一個空位aux[count[array[i] - min]++] = array[i];}// 4. 數(shù)據(jù)回寫for (int i = 0; i < length; i++) {array[i] = aux[i];} }

算法分析

當(dāng)輸入的元素是n 個0到k之間的整數(shù)時，它的運行時間是 O(n + k)。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時間和內(nèi)存。

最佳情況：T(n) = O(n+k) 最差情況：T(n) = O(n+k) 平均情況：T(n) = O(n+k)

優(yōu)課達(dá)：面試被問排序不知道怎么辦？給你史上最全經(jīng)典排序算法總結(jié)(Java實現(xiàn))

優(yōu)課達(dá)：程序員面試Java編程知識大全：最新版Java基礎(chǔ)知識面試題（一）

優(yōu)課達(dá)：程序員面試Java編程知識大全：最新版Java集合容器面試題（一）

聽說給好內(nèi)容點贊，知乎就會繼續(xù)給你推薦相關(guān)的優(yōu)質(zhì)回答，再也不怕沒學(xué)習(xí)素材了~~

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的java最全基础知识_Java编程入门，计数排序（Counting Sort）怎么做？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。