計數排序：從 Python 動畫逐步到穩定排序的完整實現解析（Hello Algo）

計數排序從 Python 動畫逐步到穩定排序的完整實現解析Hello Algo【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo計數排序counting sort透過統計元素數量而非比較大小來完成排序在整數範圍較小的場景下能達到接近線性的效率。《Hello 算法》以 Python 逐步實現、Python Tutor 逐步視覺化的方式講解該演算法本文以 zh-hant/codes/pythontutor/chapter_sorting/counting_sort.md 中的兩段可視化程式碼為主體結合 官方章節文件 與倉庫內多語言原始碼剖析「簡單實現」與「完整實現穩定排序」兩套寫法的差異、前綴和的關鍵作用、演算法特性與適用邊界。讀完本文你將能獨立寫出可排序物件的穩定計數排序並在n ≫ m的資料場景中正確選用它。計數排序的適用前提與整體思路計數排序針對的是非負整數陣列。它不比較元素大小而是依賴「陣列索引天然有序」這一性質先統計每個數字出現多少次再按數字由小到大、按出現次數逐一回填即可得到有序結果。以nums [1, 0, 1, 2, 0, 4, 0, 2, 2, 4]為例也是 Python 原始碼 與 Python Tutor 逐步演示使用的測試資料演算法分三步進行走訪nums找出最大值m建立長度為m 1的輔助陣列counter再次走訪nums統計各數字的出現次數counter[num]代表數字num出現的次數走訪counter依序把每個數字按其次數填回原陣列nums。下圖直觀地展示了「原陣列 → 計數陣列 counter → 排序結果」的對應關係數字0出現 3 次、1出現 2 次、2出現 3 次、4出現 2 次最終回填得到[0, 0, 0, 1, 1, 2, 2, 2, 4, 4]。從桶排序的角度看可以把計數陣列counter的每個索引視為一個桶統計數量的過程就是將各元素分配到對應的桶中。本質上計數排序是桶排序在整數資料下的一個特例見章節文件的「計數排序與桶排序的關聯」提示框。簡單實現只能排序數值、無法排序物件Python Tutor 文件 中收錄的第一段程式counting_sort_naive是演算法核心思想的最小可執行版本對應 Python 原始碼中的同名函式zh-hant/codes/python/chapter_sorting/counting_sort.py#L8-L23def counting_sort_naive(nums: list[int]): 計數排序 # 簡單實現無法用於排序物件 # 1. 統計陣列最大元素 m m max(nums) # 2. 統計各數字的出現次數 # counter[num] 代表 num 的出現次數 counter [0] * (m 1) for num in nums: counter[num] 1 # 3. 走訪 counter 將各元素填入原陣列 nums i 0 for num in range(m 1): for _ in range(counter[num]): nums[i] num i 1該版本的缺點在程式開頭註解已點明無法用於排序物件。假設輸入是商品物件、要依價格欄位排序上述演算法只會輸出一個「價格由小到大」的數值序列這些數值與原始物件之間的對應關係完全遺失因而無法得到「按價格排序的商品清單」。完整實現前綴和倒序走訪得到穩定排序要保留原始物件的相對關係需要能回答「每個num最後一次出現時應放在結果陣列的哪個位置」。counting_sort的關鍵技巧是先求counter的前綴和把「出現次數」轉換為「尾索引」zh-hant/codes/python/chapter_sorting/counting_sort.py#L26-L50def counting_sort(nums: list[int]): 計數排序 # 完整實現可排序物件並且是穩定排序 # 1. 統計陣列最大元素 m m max(nums) # 2. 統計各數字的出現次數 # counter[num] 代表 num 的出現次數 counter [0] * (m 1) for num in nums: counter[num] 1 # 3. 求 counter 的前綴和將“出現次數”轉換為“尾索引” # 即 counter[num]-1 是 num 在 res 中最後一次出現的索引 for i in range(m): counter[i 1] counter[i] # 4. 倒序走訪 nums 將各元素填入結果陣列 res # 初始化陣列 res 用於記錄結果 n len(nums) res [0] * n for i in range(n - 1, -1, -1): num nums[i] res[counter[num] - 1] num # 將 num 放置到對應索引處 counter[num] - 1 # 令前綴和自減 1 得到下次放置 num 的索引 # 使用結果陣列 res 覆蓋原陣列 nums for i in range(n): nums[i] res[i]其中前三步的推導如下求最大元素m建立長度m 1的counter保證所有num ∈ [0, m]都有對應的計數槽位。統計出現次數counter[num] 1累加使counter從「計數表」變成頻率分佈。累加前綴和索引i處的前綴和prefix[i] Σ_{j0}^{i} counter[j]即「所有 ≤ i 的數字總共出現多少次」。由此得到關鍵不變式prefix[num] - 1正是元素num在結果陣列res中最後一次出現的索引。倒序走訪nums每輪把元素num放到res[counter[num] - 1]隨後令counter[num]自減 1取得下一個相同元素應放置的索引。由於相同值的元素是從右往左依次填入的原陣列中靠右的相等元素仍落在結果陣列靠右的位置因此不會顛倒相等元素的相對次序——這是本版能成為穩定排序的根本原因。若改為正序走訪排序結果依然正確但相等元素相對位置可能被翻轉穩定性便會喪失。下圖展示了完整流程的最終收尾步驟res已完成排序最後用res覆蓋原陣列nums即得到有序結果此處 counter 呈現為前綴和[0, 3, 5, 8, 8]的形態。章節文件中以18八張逐步圖counting_sort.assets 目錄下的counting_sort_step1.png至counting_sort_step8.png逐幀刻畫「統計→前綴和→倒序填回→覆蓋」的完整過程讀者也可直接點開 Python Tutor 連結在原文件環境中按「下一步」單步執行觀察變數變化。演算法特性時間複雜度、空間複雜度與穩定性依照章節文件的歸納計數排序的特性可總結為下表特性結論原因時間複雜度$O(n m)$非自適應排序只需線性走訪nums與counter無關資料分佈空間複雜度$O(n m)$非原地排序需額外建立長度 $n$ 的res與長度 $m$ 的counter穩定性穩定排序倒序走訪 前綴和尾索引保證相等元素相對次序不變一般情況下 $n \gg m$時間複雜度趨於 $O(n)$這是計數排序在特定場景下能勝過 $O(n \log n)$ 比較排序的原因。但請注意當 $n \ll m$ 時counter與前綴和走訪耗費的 $O(m)$ 時間可能反而讓它比 $O(n \log n)$ 的排序更慢。此外它在建立輔助陣列res與counter時屬於非原地排序記憶體開銷也需一併納入考量。侷限性非負整數前提與資料範圍限制計數排序的巧妙之處在於「僅統計數量即完成排序」但其前置條件相對嚴格章節文件明確列出兩條只適用於非負整數若要排序其他型別需先確保資料能轉換為非負整數且轉換過程不改變元素間的相對大小關係。例如包含負數的整數陣列可先為所有數字加上一個常數使之變正排序完成後再減回該常數。適用於資料量大但資料範圍小的情況m過大時counter會佔用過多空間而 $n \ll m$ 時$O(m)$ 的時間成本可能不如 $O(n \log n)$ 的比較排序划算。倉庫中的多語言對照與實際運行計數排序並非 Python 獨有。在codes/目錄下C、C、Java、Go、TypeScript、JavaScript 等十餘種語言都提供了counting_sort_naive與counting_sort的等價實現方便對照演算法在不同語法下的寫法。以 C 語言版 為例其流程與 Python 版完全一致差別僅在於用calloc配置counter、用malloc配置結果陣列res並在結束後手動free釋放記憶體、以memcpy完成覆蓋——這正好對應 Python 版中res最後回寫nums的動作。運行方式同樣簡單Python 版可直接執行 zh-hant/codes/python/chapter_sorting/counting_sort.py其Driver Code會先後對counting_sort_naive與counting_sort施加相同的測試陣列[1, 0, 1, 2, 0, 4, 0, 2, 2, 4]並列印結果兩版輸出均為有序的[0, 0, 0, 1, 1, 2, 2, 2, 4, 4]若想逐步觀察變數狀態則可直接使用 Python Tutor 視覺化入口 中內嵌的逐步執行連結。小結計數排序的精髓在於把「比較」替換為「統計索引定位」簡單版用計數陣列按次數回填足以處理純數值完整版則透過前綴和將「出現次數」翻譯成「尾索引」再配合倒序走訪保證穩定性因而能推廣到物件排序與作為其他穩定排序的子程式。使用前務必核對兩項前提——資料可轉為非負整數、且資料範圍m相對於資料量n足夠小——唯有如此$O(n m)$ 的計數排序才能發揮接近線性的威力。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考