十大經典排序算法之八>>>計數排序

計數排序

分類 ​​算法​​

計數排序的核心在于将輸入的資料值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的資料必須是有确定範圍的整數。

1. 計數排序的特征

當輸入的元素是 n 個 0 到 k 之間的整數時，它的運作時間是 Θ(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計數的數組C的長度取決于待排序數組中資料的範圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于資料範圍很大的數組，需要大量時間和記憶體。例如：計數排序是用來排序0到100之間的數字的最好的算法，但是它不适合按字母順序排序人名。但是，計數排序可以用在基數排序中的算法來排序資料範圍很大的數組。

通俗地了解，例如有 10 個年齡不同的人，統計出有 8 個人的年齡比 A 小，那 A 的年齡就排在第 9 位,用這個方法可以得到其他每個人的位置,也就排好了序。當然，年齡有重複時需要特殊處理（保證穩定性），這就是為什麼最後要反向填充目标數組，以及将每個數字的統計減去 1 的原因。

• （1）找出待排序的數組中最大和最小的元素
• （2）統計數組中每個值為i的元素出現的次數，存入數組C的第i項
• （3）對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
• （4）反向填充目标數組：将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1

 動圖示範

代碼實作

JavaScript

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

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

    return arr;
}      

Python

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr      

Java

public class CountingSort implements IArraySort {

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

        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private 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 int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

}