數據結構與算法：計數排序

作者：日拱一卒程序猿 2023-03-10 08:07:39

開發前端

假設數組中有10個整數，取值范圍為0～10，要求用最快的速度把這10個整數從小到大進行排序。可以根據這有限的范圍，建立一個長度為11的數組。數組下標從0到10，元素初始值全為0。

一、定義

計數排序，這種排序算法是利用數組下標來確定元素的正確位置的。

二、思路

假設數組中有10個整數，取值范圍為0～10，要求用最快的速度把這10個整數從小到大進行排序。

可以根據這有限的范圍，建立一個長度為11的數組。數組下標從0到10，元素初始值全為0。

假設數組數據為：9，1，2，7，8，1，3，6，5，3 。

下面就開始遍歷這個無序的隨機數列，每一個整數按照其值對號入座，

同時，對應數組下標的元素進行加1操作。

例如第1個整數是9，那么數組下標為9的元素加1。

最終，當數列遍歷完畢時，數組的狀態如下：

該數組中每一個下標位置的值代表數列中對應整數出現的次數。

直接遍歷數組，輸出數組元素的下標值，元素的值是幾，就輸出幾次，0不輸出。

則順序輸出是：1、1、2、3、3、5、6、7、8、9。

計數排序：計數排序只能用在數據范圍不大的場景中，如果數據范圍k比要排序的數據n大很多，就不適合用計數排序了。

而且，計數排序只能給非負整數排序，如果要排序的數據是其他類型的，要將其在不改變相對大小的情況下，轉化為非負整數。

如果起始數不是從0開始，為了不浪費空間，可以采用偏移量的方式解決。

比如，如果考生最低成績0分，最高900分，但成績要精確到小數后一位，我們就需要將所有的分數都先乘以10，轉化成整數，然后再放到9010個桶內。

比如，如果要排序的數據中有負數，數據的范圍是[-1000, 1000]，那我們就需要先對每個數據都加1000，轉化成非負整數。

比如，分數排序： 95，94，91，98，99，90，99，93，91，92 ，數組起始數為90，這樣數組前面的位置就浪費了。可以采用偏移量的方式：

三、代碼實現

import java.util.Arrays;

public class CountingSort{

    public static void main(String[] args) throws Exception {
        int[] scores = {9, 3, 4, 9, 1, 2, 7, 8,1,3, 3, 4, 0, 10, 9, 7, 9};
        for (int n : sort(scores)) {
            System.out.println(n);
        }
    }

    public static int[] sort(int[] sourceArray) throws Exception {
        // 對 arr 進行拷貝，不改變參數內容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
                //
        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private static int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }
}

四、復雜度

時間復雜度是O(n+m) n: 數據個數 m: 數據范圍；

空間復雜度是O(m)；

穩定性：穩定排序。

責任編輯：武曉燕來源：今日頭條

數據結構算法計數排序