計數排序法(Counting Sort)，只需線性時間就能完成的超快排序法

計數排序(Counting Sort)演算法是不需進行比較的排序演算法，顧名思義，它會去數元素的數量來進行排序。這種排序法只需要線性時間和空間的複雜度就可以完成排序，比時間複雜度為O(nlogn)的演算法還快，而且作法也不會太難。雖然如此，計數排序法是並不算是常見的排序演算法，因為它只能用來排序已知數值範圍的序列(由於要直接對應序列的索引值，所以這組數值通常會是一組整數)。舉例來說，已知序列中的每個元素(或是其它要用來作為排序依據的屬性)是數值範圍n到m中的任一整數，那麼我們便可以使用計數排序法來排序這個序列。

計數排序法(Counting Sort)

計數排序法的概念

計數排序法的思路排序元素的方式並不是去「比較」兩元素間的大小，而是先去計算每個元素(或是其作為排序依據的屬性)在序列中出現的次數，再利用這個次數資訊去進行更進一步的排序，以下將說明兩種不同的應用情形。

首先，第一種作法是，在取得次數資訊之後，直接把已知的那一組數值中的數，依序根據其出現的次數填寫到原本要排序的序列中，填寫完成後該序列也就排序完了。

舉例來說，已知序列中的元素均為1, 2, 3, 4的其中一個數值。這個序列中實際儲存的資料為[3, 2, 1, 2, 3, 3, 1]，我們可以先計算出這個序列共有2個1、2個2、3個3、和0個4。

接著就開始把數值依序填進這個相同的序列中，首先填入2個1，序列內容會變成[1, 1, 1, 2, 3, 3, 1]。再來填入2個2，序列內容會變成[1, 1, 2, 2, 3, 3, 1]。再來填入3個3，序列內容會變成[1, 1, 2, 2, 3, 3, 3]。最後的4由於原先就沒有出現，所以不用填寫，此時就完成這個序列的排序了。

這樣的排序方式十分簡單快速，屬於「原地」(in-place)的作法，適用在被排序的元素就是用來作為排序依據的數值。也就是說，若要排序一個整數陣列的話，可以直接使用這個方式。雖然這個排序方式不是穩定的，那也不重要，因為它本來就只能排序像整數這樣的純量型別。

接著，來說明一下第二種作法。第二種作法可以說是第一種作法的延伸，在取得次數資訊之後，還要先利用這個次數資訊來計算出元素的位置資訊。同樣以剛才的序列來舉例[3, 2, 1, 2, 3, 3, 1]，次數資訊為2個1、2個2、3個3、和0個4，所以我們可以藉由照順序走訪並累加每次迭代時的此項和前項的次數，來得出「有2 + 0 = 2個元素小於等於1」、「有2 + 2 = 4個元素小於等於2」、「有4 + 3 = 7個元素小於等於3」、「有7 + 0 = 7個元素小於等於4」這樣的位置資訊。

接著產生出另一個相同大小的空序列，並從原序列的尾端向前開始走訪這個原序列，一開始會看到元素1，根據位置資訊「有2個元素小於等於1」，我們可以直接把這個原序列的元素1複製進新序列的第2個位置(也就是索引1的位置)，此時新序列的內容為[?, 1, ?, ?, ?, ?, ?]，且位置資訊修改為「有2 - 1 = 1個元素小於等於1」，然後再繼續下次的迭代，重複一樣的動作，排序的結果就會存在新序列中了。

您可能會問：為什麼要從原序列的尾端向前開始走訪，而不是從頭開始呢？這是為了要保持相同元素之間的順序，來達成穩定排序的目的。

第二種排序方式要比第一種稍微複雜一點，而且會需要額外的空間來儲存結果，屬於「非原地」(out-of-place)的作法，但其適用於「用來作為排序依據的數值不直接是被排序的元素，而是該元素的某個屬性」的情形，且排序結果是穩定的。

計數排序法的過程

假設現在有個陣列資料，內容如下：

索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3

要如何將它遞增排列呢？

由於現在要排序的資料是整數資料，因此前面提到的第一種(不穩定)和第二種(穩定)的計數排序法皆可以使用。

然而不管使用哪種方式，都要先計算出數值組中的各項數值在陣列中出現的次數。

由於待排序陣列的元素都是0~9中的一個整數數值，因此陣列元素有(9 - 0 + 1) = 10種可能的數值，所以要建立出一個大小為10的整數陣列來儲存計數排序法要用的次數資訊。此陣列索引i的位置用來儲存元素i在待排序陣列中出現的次數。計算之後我們得到了如下的計數陣列：

索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(次數)    0   0   1   3   1   0   1   0   1   2

第一種計數排序法(不穩定)

利用次數資訊開始將元素值填寫進原陣列中。

由於0和1的數量都是0，因此無需填寫到原陣列中。

       ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    9   8   3   3   9   2   4   6   3
       ●

       ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    9   8   3   3   9   2   4   6   3
       ●

將1個2填寫到原陣列中。

       ○  ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    2   8   3   3   9   2   4   6   3
       ○  ●

將3個3填寫到原陣列中。

       ○  ○  ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    2   3   3   3   9   2   4   6   3
       ○  ○  ○  ○  ●

將1個4填寫到原陣列中。

       ○  ○  ○  ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    2   3   3   3   4   2   4   6   3
       ○  ○  ○  ○  ○  ●

由於5的數量是0，因此無需填寫到原陣列中。

       ○  ○  ○  ○  ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    2   3   3   3   4   2   4   6   3
       ○  ○  ○  ○  ○  ●

將1個6填寫到原陣列中。

       ○  ○  ○  ○  ○  ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    2   3   3   3   4   6   4   6   3
       ○  ○  ○  ○  ○  ○  ●

由於7的數量是0，因此無需填寫到原陣列中。

       ○  ○  ○  ○  ○  ○  ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    2   3   3   3   4   6   4   6   3
       ○  ○  ○  ○  ○  ○  ●

將1個8填寫到原陣列中。

       ○  ○  ○  ○  ○  ○  ○  ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    2   3   3   3   4   6   8   6   3
       ○  ○  ○  ○  ○  ○  ○  ●

將2個9填寫到原陣列中。

       ○  ○  ○  ○  ○  ○  ○  ○  ○  ○
數值    0   1   2   3   4   5   6   7   8   9
次數    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
數值    2   3   3   3   4   6   8   9   9
       ○  ○  ○  ○  ○  ○  ○  ○  ○

第二種計數排序法(穩定)

累加計數陣列來求出元素的位置資訊。

                 ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   3   1   0   1   0   1   2
             └＋┘

                     ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   3   1   0   1   0   1   2
                 └＋┘

                         ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   3   1   0   1   0   1   2
                     └＋┘

                             ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   4   1   0   1   0   1   2
                         └＋┘

                                 ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   4   5   0   1   0   1   2
                             └＋┘

                                     ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   4   5   5   1   0   1   2
                                 └＋┘

                                         ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   4   5   5   6   0   1   2
                                     └＋┘

                                             ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   4   5   5   6   6   1   2
                                         └＋┘

                                                 ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   4   5   5   6   6   7   2
                                             └＋┘

                                                     ●
索引(數值)    0   1   2   3   4   5   6   7   8   9
數值(位置)    0   0   1   4   5   5   6   6   7   9

建立與待排序陣列同等大小的新陣列。

索引    0   1   2   3   4   5   6   7   8 
數值    ?   ?   ?   ?   ?   ?   ?   ?   ?

從原來待排序陣列的尾端開始將所有元素放入新陣列。

                   ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   1   4↓ 5   5   6   6   7   9
----------------------------------------------
                                       ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
                   ○
索引    0   1   2   3   4   5   6   7   8
數值    ?   ?   ?   3   ?   ?   ?   ?   ?

                               ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   1   3   5   5   6↓ 6   7   9
----------------------------------------------
                                   ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
                   ○      ○ 
索引    0   1   2   3   4   5   6   7   8
數值    ?   ?   ?   3   ?   6   ?   ?   ?

                       ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   1   3   5↓ 5   5   6   7   9
----------------------------------------------
                               ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
                   ○  ○  ○ 
索引    0   1   2   3   4   5   6   7   8
數值    ?   ?   ?   3   4   6   ?   ?   ?

               ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   1↓ 3   4   5   5   6   7   9
----------------------------------------------
                           ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○          ○  ○  ○ 
索引    0   1   2   3   4   5   6   7   8
數值    2   ?   ?   3   4   6   ?   ?   ?

                                           ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   3   4   5   5   6   7   9↓
----------------------------------------------
                       ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○          ○  ○  ○          ○
索引    0   1   2   3   4   5   6   7   8
數值    2   ?   ?   3   4   6   ?   ?   9

                   ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   3↓ 4   5   5   6   7   8
----------------------------------------------
                   ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○      ○  ○  ○  ○          ○
索引    0   1   2   3   4   5   6   7   8
數值    2   ?   3   3   4   6   ?   ?   9

                   ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   2↓ 4   5   5   6   7   8
----------------------------------------------
               ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○  ○  ○  ○  ○  ○          ○
索引    0   1   2   3   4   5   6   7   8
數值    2   3   3   3   4   6   ?   ?   9

                                       ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   1   4   5   5   6   7↓ 8
----------------------------------------------
           ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○  ○  ○  ○  ○  ○  ○      ○
索引    0   1   2   3   4   5   6   7   8
數值    2   3   3   3   4   6   8   ?   9

                                           ●
數值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   1   4   5   5   6   6   8↓
----------------------------------------------
       ●
索引    0   1   2   3   4   5   6   7   8
數值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○  ○  ○  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8
數值    2   3   3   3   4   6   8   9   9

計數排序法的程式實作

第一種計數排序法(不穩定)的程式實作方式如下：

/// 計數排序法(遞增)，原地不穩定版本。
pub fn counting_sort_unstable(array: &mut [i32], min: i32, max: i32) {
    let mut count = vec![0usize; (max - min + 1) as usize];

    for n in array.iter().copied() {
        count[(n - min) as usize] += 1;
    }

    let mut p = 0;
    let length = array.len();

    for (i, c) in count.into_iter().enumerate() {
        for _ in 0..c {
            array[p] = i as i32 + min;
            p += 1;
        }

        if p == length {
            break;
        }
    }
}

/// 計數排序法(遞減)，原地不穩定版本。
pub fn counting_sort_unstable_desc(array: &mut [i32], min: i32, max: i32) {
    let mut count = vec![0usize; (max - min + 1) as usize];

    for n in array.iter().copied() {
        count[(n - min) as usize] += 1;
    }

    let mut p = 0;
    let length = array.len();

    for (i, c) in count.into_iter().enumerate().rev() {
        for _ in 0..c {
            array[p] = i as i32 + min;
            p += 1;
        }

        if p == length {
            break;
        }
    }
}

/**
 * 計數排序法(遞增)，原地不穩定版本。
 */
public static void countingSortUnstable(final int[] array, final int min, final int max) {
    final int[] count = new int[max - min + 1];

    for (final int n : array) {
        ++count[n - min];
    }

    int p = 0;

    for (int i = 0; i < count.length; ++i) {
        final int c = count[i];

        for (int j = 0; j < c; ++j) {
            array[p++] = i + min;
        }

        if (p == array.length) {
            break;
        }
    }
}

/**
 * 計數排序法(遞減)，原地不穩定版本。
 */
public static void countingSortUnstableDesc(final int[] array, final int min, final int max) {
    final int[] count = new int[max - min + 1];

    for (final int n : array) {
        ++count[n - min];
    }

    int p = 0;

    for (int i = count.length - 1; i >= 0; --i) {
        final int c = count[i];

        for (int j = 0; j < c; ++j) {
            array[p++] = i + min;
        }

        if (p == array.length) {
            break;
        }
    }
}

/**
 * 計數排序法(遞增)，原地不穩定版本。
 */
function countingSortUnstable(array: number[], min: number, max: number) {
    const count = new Array<number>(max - min + 1).fill(0);
 
    for (const n of array) {
        count[n - min] += 1;
    }
 
    let p = 0;
 
    for (let i = 0;i < count.length;++i) {
        const c = count[i];
 
        for (let j = 0;j < c;j++) {
            array[p] = i + min;
            p += 1;
        }
 
        if (p === array.length) {
            break;
        }
    }
}
 
/**
 * 計數排序法(遞減)，原地不穩定版本。
 */
function countingSortUnstableDesc(array: number[], min: number, max: number) {
    const count = new Array<number>(max - min + 1).fill(0);
 
    for (const n of array) {
        count[n - min] += 1;
    }
 
    let p = 0;
 
    for (let i = count.length - 1;i >= 0;i--) {
        const c = count[i];
 
        for (let j = 0;j < c;++j) {
            array[p] = i + min;
            p += 1;
        }
 
        if (p === array.length) {
            break;
        }
    }
}

// 計數排序法(遞增)，原地不穩定版本。
func CountingSortUnstable(array []int, min int, max int) {
	count := make([]int, max-min+1)

	for _, n := range array {
		count[n-min] += 1
	}

	p := 0
	length := len(array)

	for i, c := range count {
		for j := 0; j < c; j += 1 {
			array[p] = i + min
			p += 1
		}

		if p == length {
			break
		}
	}
}

// 計數排序法(遞減)，原地不穩定版本。
func CountingSortUnstableDesc(array []int, min int, max int) {
	count := make([]int, max-min+1)

	for _, n := range array {
		count[n-min] += 1
	}

	p := 0
	length := len(array)

	for i := max - min; i >= 0; i -= 1 {
		c := count[i]

		for j := 0; j < c; j += 1 {
			array[p] = i + min
			p += 1
		}

		if p == length {
			break
		}
	}
}

第二種計數排序法(穩定)的程式實作方式如下：

/// 計數排序法(遞增)，穩定版本。
pub fn counting_sort_stable(array: &mut [i32], min: i32, max: i32) {
    let size = (max - min + 1) as usize;

    let mut count = vec![0usize; size];

    for n in array.iter().copied() {
        count[(n - min) as usize] += 1;
    }

    for i in 1..size {
        count[i] += count[i - 1];
    }

    let origin = array.to_vec();

    for n in origin.into_iter().rev() {
        let c = count.get_mut((n - min) as usize).unwrap();
        *c -= 1;
        array[*c] = n;
    }
}

/// 計數排序法(遞減)，穩定版本。
pub fn counting_sort_stable_desc(array: &mut [i32], min: i32, max: i32) {
    let size = (max - min + 1) as usize;

    let mut count = vec![0usize; size];

    for n in array.iter().copied() {
        count[(n - min) as usize] += 1;
    }

    for i in (0..(size - 1)).rev() {
        count[i] += count[i + 1];
    }

    let origin = array.to_vec();

    for n in origin.into_iter().rev() {
        let c = count.get_mut((n - min) as usize).unwrap();
        *c -= 1;
        array[*c] = n;
    }
}

/**
 * 計數排序法(遞增)，穩定版本。
 */
public static void countingSortStable(final int[] array, final int min, final int max) {
    final int size = max - min + 1;

    final int[] count = new int[size];

    for (final int n : array) {
        ++count[n - min];
    }

    for (int i = 1; i < size; ++i) {
        count[i] += count[i - 1];
    }

    final int[] origin = array.clone();

    for (int i = array.length - 1; i >= 0; --i) {
        final int n = origin[i];

        array[--count[n - min]] = n;
    }
}

/**
 * 計數排序法(遞減)，穩定版本。
 */
public static void countingSortStableDesc(final int[] array, final int min, final int max) {
    final int size = max - min + 1;

    final int[] count = new int[size];

    for (final int n : array) {
        ++count[n - min];
    }

    for (int i = size - 2; i >= 0; --i) {
        count[i] += count[i + 1];
    }

    final int[] origin = array.clone();

    for (int i = array.length - 1; i >= 0; --i) {
        final int n = origin[i];

        array[--count[n - min]] = n;
    }
}

/**
 * 計數排序法(遞增)，穩定版本。
 */
function countingSortStable(array: number[], min: number, max: number) {
    const size = max - min + 1;

    const count = new Array<number>(size).fill(0);

    for (const n of array) {
        count[n - min] += 1;
    }

    for (let i = 1;i < size;++i) {
        count[i] += count[i - 1];
    }

    const origin = array.slice();

    for (let i = array.length - 1;i >= 0;i--) {
        const n = origin[i];
        const ii = n - min;

        count[ii] -= 1;

        array[count[ii]] = n;
    }
}

/**
 * 計數排序法(遞減)，穩定版本。
 */
function countingSortStableDesc(array: number[], min: number, max: number) {
    const size = max - min + 1;

    const count = new Array<number>(size).fill(0);

    for (const n of array) {
        count[n - min] += 1;
    }

    for (let i = size - 2;i >= 0;i--) {
        count[i] += count[i + 1];
    }

    const origin = array.slice();

    for (let i = array.length - 1;i >= 0;i--) {
        const n = origin[i];
        const ii = n - min;

        count[ii] -= 1;

        array[count[ii]] = n;
    }
}

// 計數排序法(遞增)，穩定版本。
func CountingSortStable(array []int, min int, max int) {
	size := max - min + 1

	count := make([]int, size)

	for _, n := range array {
		count[n-min] += 1
	}

	for i := 1; i < size; i += 1 {
		count[i] += count[i-1]
	}

	length := len(array)

	origin := make([]int, length)
	copy(origin, array)

	for i := length - 1; i >= 0; i -= 1 {
		n := origin[i]

		c := &count[n-min]
		*c -= 1
		array[*c] = n
	}
}

// 計數排序法(遞減)，穩定版本。
func CountingSortStableDesc(array []int, min int, max int) {
	size := max - min + 1

	count := make([]int, size)

	for _, n := range array {
		count[n-min] += 1
	}

	for i := size - 2; i >= 0; i -= 1 {
		count[i] += count[i+1]
	}

	length := len(array)

	origin := make([]int, length)
	copy(origin, array)

	for i := length - 1; i >= 0; i -= 1 {
		n := origin[i]

		c := &count[n-min]
		*c -= 1
		array[*c] = n
	}
}

計數排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。以#{{k}}#來表示要排序的資料可能的值的數量。

項目	值	備註
最差時間複雜度	#{{O(n + k)}}#
最佳時間複雜度	#{{O(n + k)}}#
平均時間複雜度	#{{O(n + k)}}#
最差空間複雜度	#{{O(k)}}# #{{O(n + k)}}#	第一種計數排序法(原地不穩定)。第二種計數排序法(穩定)。
是否穩定	否是	第一種計數排序法(原地不穩定)。第二種計數排序法(穩定)。