企业官网建设流程全解析

《Hello 算法》桶排序深度解析：线性时间非比較排序的流程、特性與平均分配策略

【免费下载链接】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

桶排序（bucket sort）是《Hello 算法》排序章節中介紹的第一種「非比較排序演算法」，它跳脫了「比較元素大小」的框架，改用「分桶 + 桶內排序 + 依序合併」的思路，在理想情況下將時間複雜度從比較排序的 $\Omega(n \log n)$ 下界推進到 $O(n)$。本文以繁體中文版 桶排序章節 為主體，結合倉庫內 Python、C、C++、Java、Go、JavaScript、C# 等多語言實作，完整講解桶排序的演算法流程、複雜度特性、穩定性判斷，以及「如何實現平均分配」這一決定效能上限的關鍵問題，讀者讀完後能獨立理解並手寫出可運行的桶排序程式碼。

從比較排序到非比較排序：突破 $\Omega(n \log n)$ 下界

本篇文章之前介紹的幾種排序演算法——如氣泡排序、插入排序、合併排序、快速排序等——都屬於「基於比較的排序演算法」。它們透過比較元素之間的大小來決定次序，而此類演算法在最壞情況下的時間複雜度存在理論下界 $\Omega(n \log n)$。

桶排序則屬於「非比較排序演算法」家族，與後續章節會提到的計數排序（counting sort）、基數排序（radix sort）一樣，它不依賴元素間兩兩比較，而是利用數據本身的數值範圍與分佈特徵直接「歸位」，因此有機會達到線性階時間複雜度。這一思路的典型工程化體現可以在倉庫的 計數排序 與 基數排序 中看到——三者共享「先分組、再處理」的非比較思想。

桶排序的核心思想：分治策略的典型應用

桶排序是分治策略（divide and conquer）的一個典型應用，其基本思路是：

1. 設定桶：設定一些具有大小順序的桶，每個桶對應一個數據範圍；
2. 分桶：將資料按數值範圍平均分配到各個桶中；
3. 桶內排序：在每個桶內部分別執行排序；
4. 合併：按照桶的順序將所有資料依序合併，得到完整有序陣列。

直觀上，這相當於把「一次大規模排序」拆解成「若干次小規模排序」。由於每個桶內的資料量遠小於整體，桶內排序的成本大幅下降，最終整體時間複雜度接近線性。

演算法流程詳解與完整程式碼

考慮一個長度為 $n$ 的陣列，其元素是範圍 $[0, 1)$ 內的浮點數。桶排序的完整流程如下：

1. 初始化$k$ 個桶，將 $n$ 個元素分配到 $k$ 個桶中；
2. 桶內排序：對每個桶分別執行排序（實作中採用程式語言的內建排序函式，也可替換為其他排序演算法）；
3. 合併結果：按照桶從小到大的順序合併所有桶中的元素。

以 Python 實作為例，完整可運行程式碼位於 bucket_sort.py：

def bucket_sort(nums: list[float]): """桶排序""" # 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素 k = len(nums) // 2 buckets = [[] for _ in range(k)] # 1. 將陣列元素分配到各個桶中 for num in nums: # 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1] i = int(num * k) # 將 num 新增進桶 i buckets[i].append(num) # 2. 對各個桶執行排序 for bucket in buckets: # 使用內建排序函式，也可以替換成其他排序演算法 bucket.sort() # 3. 走訪桶合併結果 i = 0 for bucket in buckets: for num in bucket: nums[i] = num i += 1 if __name__ == "__main__": # 設輸入資料為浮點數，範圍為 [0, 1) nums = [0.49, 0.96, 0.82, 0.09, 0.57, 0.43, 0.91, 0.75, 0.15, 0.37] bucket_sort(nums) print("桶排序完成後 nums =", nums)

程式碼中有兩個關鍵設計細節值得注意：

• 桶數量取 $k = n / 2$：這是「預期每個桶分配到 2 個元素」的經驗設定。以範例輸入 $n = 10$ 為例，$k = 5$，每個桶平均 2 個元素，桶內排序成本極低；
• 映射式分桶 $i = \lfloor num \times k \rfloor$：由於輸入範圍是 $[0, 1)$，num * k恰好落在 $[0, k)$，取整後即為桶索引 $[0, k-1]$。這一步是「非比較」的關鍵——不比較元素之間的大小，而是直接由數值計算出歸屬桶。

多語言實作的一致性

《Hello 算法》倉庫在繁中版目錄下提供了多達 12 種語言的同構實作，全部遵循「$k = n/2$ 分桶 → 內建排序 → 依序合併」的同一套邏輯，只是套用了各語言慣用的資料結構與排序 API：

從這組對照可以歸納出兩個工程要點：

1. JS 的sort預設按字典序（字串）排序，對浮點數必須顯式傳入比較函式(a, b) => a - b，否則會得到錯誤結果；
2. C 語言沒有內建「排序容器」，需要自行用malloc配置二維動態陣列、以sizes陣列記錄每個桶的實際元素數目，並在合併後逐桶free釋放記憶體——這正好展示了桶排序「額外空間」的底層實現形態。

演算法特性：複雜度、空間與穩定性

桶排序的演算法特性可從三個維度分析：

• 時間複雜度 $O(n + k)$：假設元素在各個桶內平均分佈，那麼每個桶內的元素數量為 $\frac{n}{k}$。假設排序單個桶使用 $O(\frac{n}{k} \log\frac{n}{k})$ 時間，則排序所有桶使用 $O(n \log\frac{n}{k})$ 時間。當桶數量 $k$ 比較大時，時間複雜度趨向於 $O(n)$。合併結果時需要走訪所有桶和元素，花費 $O(n + k)$ 時間。在最差情況下，所有資料被分配到一個桶中，且排序該桶使用 $O(n^2)$ 時間（例如桶內使用插入排序等平方級演算法）。
• 空間複雜度 $O(n + k)$、非原地排序：需要藉助 $k$ 個桶和總共 $n$ 個元素的額外空間。以 C 實作為例，這份空間正是 bucket_sort.c 中malloc出的桶陣列。
• 穩定性取決於桶內排序演算法：桶排序本身是否穩定，取決於排序桶內元素的演算法是否穩定。若桶內使用穩定的排序（如插入排序、合併排序），則整體穩定；若使用不穩定的排序（如快速排序），則整體不穩定。因此「桶排序是否穩定」並非一個固定答案，而是一個依賴實作的性質。

典型應用場景：超大規模資料的外部排序

桶排序最適合處理體量很大的資料。例如，輸入資料包含 100 萬個元素，由於空間限制，系統記憶體無法一次性載入所有資料。此時，可以將資料分成 1000 個桶，然後分別對每個桶進行排序，最後將結果合併。這種「分批載入、逐桶處理、依序合併」的機制讓桶排序天然適合外部排序（external sorting）場景——每個桶可以獨立存放於磁碟，排序時逐個讀入記憶體即可，有效避開記憶體容量瓶頸。

如何實現平均分配：決定 $O(n)$ 能否成立的關鍵

桶排序的時間複雜度理論上可以達到 $O(n)$，關鍵在於將元素均勻分配到各個桶中，因為實際資料往往不是均勻分佈的。若資料高度集中，多數元素擠入少數桶中，桶內排序成本急劇上升，整體複雜度便會退化。

以電商場景為例：我們想要將淘寶上的所有商品按價格範圍平均分配到 10 個桶中，但商品價格分佈不均——低於 100 元的非常多，高於 1000 元的非常少。若將價格區間平均劃分為 10 個，各個桶中的商品數量差距會非常大，前幾個桶可能塞滿了絕大多數商品。

策略一：遞迴劃分桶

為實現平均分配，可以先設定一條大致的分界線，將資料粗略地分到 3 個桶中。分配完畢後，再將商品較多的桶繼續劃分為 3 個桶，直至所有桶中的元素數量大致相等。

如下圖所示，這種方法本質上是建立一棵遞迴樹，目標是讓葉節點的值（即最終每個桶的元素數量）儘可能平均。當然，不一定要每輪將資料劃分為 3 個桶，具體劃分方式可根據資料特點靈活選擇——可以是 2 分、3 分或更多分，層數也可動態調整。這一策略的優點是不需要事先了解資料分佈，透過「觀察分配結果再細分」的自適應方式逼近均勻。

策略二：根據機率分佈劃分桶

如果提前知道商品價格的機率分佈，則可以根據資料機率分佈設定每個桶的價格分界線。值得注意的是，資料分佈並不一定需要特意統計，也可以根據資料特點採用某種機率模型進行近似。

例如，假設商品價格服從正態分佈，那麼價格在均值附近最密集、兩端稀疏。此時若按等寬區間分桶，中間桶會過載；而若依照正態分佈的累積機率設定分界線（在均值附近加密分桶、兩端放寬），就能將商品平均分配到各個桶中。這種「先建模、再定界」的思路比遞迴劃分更精準，代價是需要對資料分佈有一定的先驗知識。

總結

桶排序以「分桶 → 桶內排序 → 合併」三階段流程，實現了理想情況下 $O(n)$ 的線性時間複雜度，突破了比較排序 $\Omega(n \log n)$ 的下界，是分治策略在排序領域的典範應用。它的效能天花板由「元素是否均勻分配到各桶」決定，實務上可透過遞迴細分或機率分佈建模兩種策略逼近均勻分配。其空間代價為 $O(n + k)$ 的額外記憶體，穩定性則視桶內排序演算法的選擇而定。

若想進一步鞏固理解，建議動手運行倉庫內對應語言的 bucket_sort 實作，並將其與同屬非比較排序家族的 計數排序、基數排序 對照學習，可更完整地掌握「以空間換時間」的非比較排序體系。

【免费下载链接】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