計數排序的簡單理解

詳細描述

計數排序作為一種線性時間複雜度的排序演算法,其要求輸入的數據必須是有確定範圍的整數,核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。

計數排序詳細的執行步驟如下:

  1. 找出原數組中元素值最大的,記為 max
  2. 創建一個新數組 count,其長度是 max+1,其元素默認值都為 0
  3. 遍歷原數組中的元素,以原數組中的元素作為 count 數組的索引,以原數組中的元素出現次數作為 count 數組的元素值;
  4. 創建結果數組 result,起始索引 index
  5. 遍歷 count 數組,找出其中元素值大於 0 的元素,將其對應的索引作為元素值填充到 result 數組中去,每處理一次,count 中的該元素值減 1,直到該元素值不大於 0,依次處理 count 中剩下的元素;
  6. 返回結果數組 result

演算法圖解

計數排序

問題解疑

計數排序的時間複雜度是多少?

計數排序的時間複雜度可以達到 \(O(n+k)\),其中 k 是 count 數組的長度。

從這裡可以知道,count 數組元素的取值越集中,演算法耗費的時間越短。

計數排序有什麼限制嗎?

計數排序有兩個前提需要滿足:

  • 排序的元素必須是整數,否則無法對應數組的索引下標
  • 排序元素的取值要在一定範圍內,並且比較集中,否則 count 數組將會非常大

只有這兩個條件都滿足,才能最大程度發揮計數排序的優勢。

程式碼實現

package cn.fatedeity.algorithm.sort;

/**
 * 計數排序演算法
 */
public class CountSort {
    public static int[] sort(int[] numbers) {
        if (numbers.length == 0) {
            return numbers;
        }

        int min = numbers[0], max = numbers[0];
        for (int number : numbers) {
            if (number < min) {
                min = number;
            } else if (number > max) {
                max = number;
            }
        }

        int[] count = new int[max - min + 1];
        for (int number : numbers) {
            int index = number - min;
            count[index]++;
        }

        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                numbers[index++] = i + min;
                count[i]--;
            }
        }

        return numbers;
    }
}