基數排序（Radix Sort）是一種非比較型的整數排序算法，它的核心思想是按照數字的每一位（從最低位到最高位，例如個位、十位、百位等）依次進行排序。與基於比較的排序算法（如快速排序、歸併排序）不同，基數排序通過“分桶”和“收集”的方式實現排序，特別適合處理整數排序問題。
基數排序的基本思路¶
要使用基數排序，我們需要先確定待排序數組中最大數的位數，例如數組中的最大數是802，它有3位（個位、十位、百位），那麼我們就需要對這3位分別進行排序。具體步驟如下：
- 確定位數：找到數組中的最大數，計算其位數（例如802的位數是3）。
- 按位排序：從最低位（個位，第0位）開始，依次到最高位（百位，第2位）。對於每一位，我們將數組中的元素按照當前位的數字分到不同的“桶”中，然後按順序收集這些桶中的元素，完成該位的排序。
- 重複處理：對每一位重複上述分桶和收集操作，直到所有位都處理完畢，數組即完成排序。
Python實現步驟¶
下面我們通過代碼實現基數排序，關鍵步驟如下：
def radix_sort(arr):
# 處理空數組情況
if not arr:
return arr
# 找到數組中的最大數，確定需要排序的位數
max_num = max(arr)
digits = len(str(max_num)) # 最大數的位數，例如max_num=802時，digits=3
# 遍歷每一位（從最低位到最高位，digit從0開始）
for digit in range(digits):
# 初始化10個桶（0-9），每個桶用於存放當前位數字相同的元素
buckets = [[] for _ in range(10)]
# 按當前位的數字將元素分到對應的桶中
for num in arr:
# 獲取當前位的數字：(num // 10^digit) % 10
current_digit = (num // (10 ** digit)) % 10
buckets[current_digit].append(num)
# 將所有桶中的元素按順序收集，更新數組爲當前位排序後的結果
arr = []
for bucket in buckets:
arr.extend(bucket)
return arr
代碼解釋¶
- 處理空數組：如果輸入數組爲空，直接返回空數組，避免後續計算錯誤。
- 確定位數：通過
max(arr)找到最大數，再用len(str(max_num))計算其位數（例如802的位數是3）。 - 分桶與收集：
- 初始化桶：創建10個空列表（對應0-9的數字），用於存放每一位排序後的元素。
- 按位分桶：遍歷數組中的每個數，通過(num // (10 ** digit)) % 10獲取當前位數字（例如170的第0位（個位）是170//1 %10=0，第1位（十位）是170//10 %10=7），並將數放入對應桶中。
- 收集元素：將所有桶中的元素按順序連接，得到當前位排序後的數組，作爲下一位排序的輸入。
測試示例¶
以數組[170, 45, 75, 90, 802, 24, 2, 66]爲例驗證算法：
1. 處理個位（第0位）：所有數的個位數字爲0,5,5,0,2,2,4,6，分桶後收集結果爲[170, 90, 802, 2, 24, 45, 75, 66]。
2. 處理十位（第1位）：所有數的十位數字爲7,9,0,0,2,4,7,6，分桶後收集結果爲[802, 2, 24, 45, 66, 170, 75, 90]。
3. 處理百位（第2位）：所有數的百位數字爲8,0,0,0,0,1,0,0，分桶後收集結果爲[2, 24, 45, 66, 75, 90, 170, 802]，排序完成。
總結¶
基數排序通過按位分桶和收集實現排序，時間複雜度爲O(d×(n+k))（其中d是最大數的位數，n是數組長度，k是桶的數量，此處k=10），空間複雜度爲O(n+k)。它特別適合處理位數較少的整數數組，尤其當數組中存在重複數字時效率更高。如果需要處理負數，可先將負數轉爲正數，排序後再恢復符號。