與基於比較的排序算法（歸併排序、堆排序、快速排序、冒泡排序、插入排序等等）相比，基於比較的排序算法的時間複雜度最好也就是
計數排序（Counting Sort）的時間複雜度為
那麼問題來了，當這個元素的的範圍在 1 到
此時就不能用計數排序了奧，因為這種情況下，計數排序的時間複雜度達到了
比如對數組 [170, 45, 75, 90, 802, 24, 2, 66] 這個而言，數組總共包含 8 個元素，而數組中的最大值和最小值之差為 802 - 2 = 800 ，這種情況下，計數排序就 」失靈了「 。
那麼有沒有那種排序算法可以在線性時間對這個數組進行排序呢？
答案就是今天要講的 基數排序（Radix Sorting） 。基數排序的總體思想就是從待排序數組當中，元素的最低有效位到最高有效位 逐位 進行比較排序；此外，基數排序使用計數排序作為一個排序的子過程。
下面我們就以數組 [170, 45, 75, 90, 802, 24, 2, 66] ，快樂學習基數排序！
數組當中的最大值 802 為三位數，所以我們在不足三位的數字前面補 0 ，即[170, 045, 075, 090, 802, 024, 002, 066]方便後續說明基數排序。
第一步：按數組當中元素的最低有效位，個位 [170 ,045 ,075 , 090 ,802 , 024 , 002 , 066 ]，進行計數排序：
第二步：按數組當中元素的次最低有效位，十位數 [170, 090, 802, 002, 024, 045, 075, 066] ，進行計數排序：
第三步：按數組當中元素的最高有效位，百位 [802, 002, 024, 045, 066, 170, 075, 090] ，進行計數排序：
這樣我們就完成了基數排序，得到了一個有序數組 [2, 24, 45, 66, 75, 90, 170, 802] .
高清視頻動畫實現代碼import java.io.*;
import java.util.*;
class Radix {
// 獲取數組中的最大值
static int getMax(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
max = arr[i];
return max;
}
// 計數排序
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; //輸出數組
int i;
int count[] = new int[10];
Arrays.fill(count,0);
// 統計數組中元素第 exp 位的數目
for (i = 0; i < n; i++){
count[(arr[i]/exp)%10]++;
}
// 對 count[] 數組進行轉
for (i = 1; i < 10; i++){
count[i] += count[i - 1];
}
// 進行計數排序
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// 輸出到數組arr[]中
for (i = 0; i < n; i++){
arr[i] = output[i];
}
}
// 基數排序
static void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// 對數組當中的數字按照每一個有效位進行一趟計數排序。
for (int exp = 1; m/exp > 0; exp *= 10){
countSort(arr, n, exp);
}
}
// 進行輸出
static void print(int arr[], int n)
{
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
/*Driver function to check for above function*/
public static void main (String[] args)
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = arr.length;
radixsort(arr, n);
print(arr, n);
}
}實現當中有一個細節需要解釋一下，那就是如何從最低位到最高位取每一個數字的該位的值。答案很簡單了，就是除 10 取餘。
比如 802 ，要取最低位，802 % 10 = 2 ，就取到了個位；緊接著除 10 取商數 802 / 10 = 80 ，然後對商數 80 進行除 10 取餘數，就可以得到十位了，80 % 10 = 0 ；最後再對 80 除 10 取商數 80 / 10 = 8 ， 然後對商數 8 進行除 10 取餘數，8 % 10 = 8 就可以得到百位數。
代碼中的 (arr[i] / exp) % 10 就可以輕鬆理解啦， exp 就相當於控制位數，而取餘操作就相當於取出第 exp 位的值。
當然徹底搞懂基數排序，前提是你要清楚計數排序（Counting Sort），又到打廣告的時間了，推薦看一下 漫畫：什麼是計數排序？。
複雜度分析 時間複雜度設
設
則基數排序整個時間複雜度為
對於一個較大的數
假設
那麼基數排序的時間複雜度就為
可是當我們將這個
當
也就說，當數字用
對於元素的跨度（範圍）比較大的數組而言，基數排序的運行時間可能比快速排序要好。但是對於基數排序而言，其漸近時間複雜度中隱含了更高的常量因子，並非完全的線性；而快速排序更有效地利用硬體緩存，提高其效率。此外，基數排序使用計數排序作為子過程，計數排序佔用額外的空間來對數組進行排序。
但是基數排序解決我們最開始所提出的問題，當數據範圍在 1 到
空間複雜度計數排序使用了額外的空間進行排序，空間複雜度為
推薦閱讀：
圖解「歸併排序」算法（修訂版）
圖解：什麼是快速排序？
漫畫：什麼是計數排序？
作者：景禹，一個追求極致的共享主義者，想帶你一起擁有更美好的生活，化作你的一把傘。