跳转至

計數排序

提醒

本頁面要介紹的不是 基數排序。

本頁面將簡要介紹計數排序。

定義

計數排序（英語：Counting sort）是一種線性時間的排序算法。

過程

計數排序的工作原理是使用一個額外的數組 \(C\)，其中第 \(i\) 個元素是待排序數組 \(A\) 中值等於 \(i\) 的元素的個數，然後根據數組 \(C\) 來將 \(A\) 中的元素排到正確的位置。1

它的工作過程分為三個步驟：

  1. 計算每個數出現了幾次；
  2. 求出每個數出現次數的 前綴和；
  3. 利用出現次數的前綴和，從右至左計算每個數的排名。

計算前綴和的原因

閲讀本章內容只需要瞭解前綴和概念即可

直接將 \(C\) 中正數對應的元素依次放入 \(A\) 中不能解決元素重複的情形。

我們通過為額外數組 \(C\) 中的每一項計算前綴和，結合每一項的數值，就可以為重複元素確定一個唯一排名：

額外數組 \(C\) 中每一項的數值即是該 key 值下重複元素的個數，而該項的前綴和即是排在最後一個的重複元素的排名。

如果按照 \(A\) 的逆序進行排列，那麼顯然排序後的數組將保持 \(A\) 的原序（相同 key 值情況下），也即得到一種穩定的排序算法。

counting sort animate example

性質

穩定性

計數排序是一種穩定的排序算法。

時間複雜度

計數排序的時間複雜度為 \(O(n+w)\)，其中 \(w\) 代表待排序數據的值域大小。

代碼實現

偽代碼

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ positive integers no greater than } w. \\ 2 & \textbf{Output. } \text{Array }A\text{ after sorting in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for }i\gets0\textbf{ to }w\\ 5 & \qquad cnt[i]\gets0\\ 6 & \textbf{for }i\gets1\textbf{ to }n\\ 7 & \qquad cnt[A[i]]\gets cnt[A[i]]+1\\ 8 & \textbf{for }i\gets1\textbf{ to }w\\ 9 & \qquad cnt[i]\gets cnt[i]+cnt[i-1]\\ 10 & \textbf{for }i\gets n\textbf{ downto }1\\ 11 & \qquad B[cnt[A[i]]]\gets A[i]\\ 12 & \qquad cnt[A[i]]\gets cnt[A[i]]-1\\ 13 & \textbf{return } B \end{array} \]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
const int N = 100010;
const int W = 100010;

int n, w, a[N], cnt[W], b[N];

void counting_sort() {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
N = W = 100010
n = w = 0
a = b = [0] * N
cnt = [0] * W

def counting_sort():
    for i in range(1, n + 1):
        cnt[a[i]] += 1
    for i in range(1, w + 1):
        cnt[i] += cnt[i - 1]
    for i in range(n, 0, -1):
        b[cnt[a[i]] - 1] = a[i]
        cnt[a[i]] -= 1

參考資料與註釋

  1. 計數排序 - 維基百科，自由的百科全書 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用