計數(shù)排序是一種穩(wěn)定的線性時間排序算法，原理是使用一個額外的數(shù)組，其中第i個元素是待排序數(shù)組中值等于i的元素的個數(shù)。

計數(shù)排序的局限性：

• 計數(shù)排序只適用于 整數(shù) 排序；
• 計數(shù)排序只適用于一定范圍，如果待排序整數(shù)最大值和最小值差較大則不適用（引發(fā)大量存儲空間浪費）。

復雜度分析

代碼中遍歷過原始待排序數(shù)列和臨時的統(tǒng)計數(shù)列，假設原始待排序數(shù)列規(guī)模是N，臨時統(tǒng)計數(shù)列規(guī)模是M，則時間復雜度是O(N+M)，空間復雜度O(M)。

Java 代碼實現(xiàn)

import java.util.Arrays;

public class CountSort {

    public static void sort(int[] data) {
        if (data == null || data.length == 0) {
            return;
        }
        // 獲取數(shù)列最大值
        int max = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] > max) {
                max = data[i];
            }
        }
        // 創(chuàng)建長度為“最大值+1”的統(tǒng)計數(shù)組
        int[] count = new int[max + 1];
        // 遍歷待排序元素，填充統(tǒng)計數(shù)組
        for (int i = 0; i < data.length; i++) {
            count[data[i]]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0) {
                for (int j = 0; j < count[i]; j++) {
                    data[index++] = i;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] data = {5, 8, 2, 9, 1, 0, 3, 4, 7, 4, 6, 2, 5};
        sort(data);
        System.out.println(Arrays.toString(data));
    }
}

運行結果

[0, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 9]

思考：以上代碼存在什么問題？如果待排序整數(shù)都是大整數(shù)，如針對121, 123, 101, 119, 110, 149, 136排序，一共需要排序的整數(shù)有7個，但是按照以上代碼邏輯會創(chuàng)建一個容納150個整數(shù)的額外數(shù)組，大部分存儲空間實際是浪費了。
優(yōu)化方法：不再以最大值 + 1作為數(shù)組長度，以最大值 - 最小值 + 1作為數(shù)組長度，同時數(shù)組最小位存儲偏移量。以121, 123, 101, 119, 110, 149, 136為例，數(shù)組長度為149 - 101 + 1 = 49，偏移量為最小值101。優(yōu)化后代碼實現(xiàn)如下：

import java.util.Arrays;

public class CountSort {

    public static void sort(int[] data) {
        if (data == null || data.length == 0) {
            return;
        }
        // 獲取數(shù)列最大值
        int max = data[0];
        int min = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] > max) {
                max = data[i];
            } else if (data[i] < min) {
                min = data[i];
            }
        }
        // 創(chuàng)建長度為“最大值+1”的統(tǒng)計數(shù)組
        int[] count = new int[max - min + 1];
        // 遍歷待排序元素，填充統(tǒng)計數(shù)組
        for (int i = 0; i < data.length; i++) {
            count[data[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0) {
                for (int j = 0; j < count[i]; j++) {
                    data[index++] = i + min;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] data = {121, 123, 101, 119, 110, 123, 149, 136};
        sort(data);
        System.out.println(Arrays.toString(data));
    }
}

運行結果

[101, 110, 119, 121, 123, 123, 136, 149]