基數排序(Radix Sort)演算法，可以依據多個鍵值來排序的演算法

基數排序(Radix Sort)演算法是可以利用多個鍵值來排序資料的演算法。排序還需要多個鍵值？有時候當然會需要啦！像是要排序檔案時，可以先依照檔案名稱排序後，再依照檔案大小來排，如此一來，整體上來看這些檔案，會是以檔案大小來排序，而相同檔案大小的檔案則是會依照檔案名稱來排序。基數排序法可以將整數的各個位數當作是鍵值，來進行線性時間的排序，比起會依照k(要排序的資料可能的值的數量)愈大而愈吃空間的計數排序法，基數排序法的空間複雜度是比較能夠控制的。

基數排序法(Radix Sort)

基數排序法的概念

基數排序法將整數的各個位數當作是鍵值，可以進行數值上遞增、遞減的排序，如：[1, 2, 3, 12, 23]；或是進行字典排序，如[1, 12, 2, 23, 3]。

若我們從整數最小的位數(LSD, least significant digit)開始，先把個位數當鍵值來排序、再把十位數當鍵值來排序、再把百位數當鍵值來排序……依此類推，直到完成最高位數的排序之後，就可以排出遞增或是遞減的序列了！若我們從整數最大的位數(MSD, most significant digit)開始，排到最小的個位數，就會是字典排序。這邊要特別注意的是，從MSD開始排序的時候，從左邊往右開始數的第一個有效位數就是MSD，例如8和20，8是8的MSD，2是20的MSD；從LSD開始排序的時候，從右邊往左開始數的第一個有效位數就是LSD，例如8和20，8是8的LSD，0是20的LSD。

以程式實作面來說，LSD的基數排序法比MSD的基數排序法還更容易實現。

基數排序法的過程

LSD──遞增或遞減排序

假設現在有個陣列資料，內容如下：

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢？

首先我們先拿個位數當鍵值，使用計數排序等適合少量已知數值範圍資料且穩定的演算法，先將序列進行第一次的遞增排序。這邊要注意的是，若有元素的位數小於整個序列的元素的最高位數時，要從最高位數開始補0。

索引    0   1   2   3   4   5   6   7   8   9
數值    6   8   3   3   0   0   4   6   3   7
        9   1   0   8   9   2   7   1   2   9   ●

排序後的結果如下：

索引    0   1   2   3   4   5   6   7   8   9
數值    3   8   6   0   3   4   3   6   0   7   ●
        0   1   1   2   2   7   8   9   9   9   ○

再來繼續排序十位數，排序後的結果如下：

索引    0   1   2   3   4   5   6   7   8   9
數值    0   0   3   3   3   4   6   6   7   8   ○
        2   9   0   2   8   7   1   9   9   1   ○

由於此序列最高位數就是十位數，至此就排序完成啦！

MSD──字典排序

假設現在有個陣列資料，內容如下：

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何以辭典排列原則將它排序完成呢？

這邊會需要用到額外的空間。利用十個桶子，編號為0~9，把目前正在查看的位數是0~9的元素個別丟進這十個桶子內。如果該位數的值是0，就丟進0號桶子；如果該位數的值是5，就丟進5號桶子，依此類推。

桶子號碼    0   1   2   3   4   5   6   7   8   9
桶子內容   []  []  []  []  []  []  []  []  []  []

一開始當然是先看MSD，把元素依據MSD丟入桶子中之後，桶子的內容此時如下：

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
        
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 38, 32]          [47]            []      [69, 61]          [79]          [81]            [9]

接著開始走訪所有桶子，尋找所有元素數量大於1的桶子，因為它們還需要再分類！

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ●
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 38, 32]          [47]            []      [69, 61]          [79]          [81]            [9]

我們可以先找到號碼3的桶子，它擁有三個元素。接著我們再拿十個新桶子出來，編號為0~9，把原先十個桶子中號碼3的桶子內的所有元素再分進去，此時要看的位數是目前位數(也就是MSD)的下一個位數。

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [30, 38, 32]
        
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容     [30]            []            [32]          []            []            []            []            []          [38]             []

同樣地，開始走訪所有桶子，尋找所有元素數量大於1的桶子，因為它們還需要再分類！

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [30, 38, 32]
               ○            ○            ○            ○            ○            ○            ○            ○            ○             ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容     [30]            []            [32]          []            []            []            []            []          [38]             []

因為已經沒有元素數量大於1的桶子了，就把這個桶子堆2的所有元素，再按照桶子順序塞回原本在桶子堆1的號碼3的桶子中。

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [69, 61]          [79]          [81]            [9]

接著繼續尋找元素數量大於1的桶子吧！

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○            ○            ○            ●
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [69, 61]          [79]          [81]            [9]

我們可以找到號碼6的桶子，它擁有兩個元素。接著我們再拿十個新桶子出來，編號為0~9，把原先十個桶子中號碼6的桶子內的所有元素再分進去，此時要看的位數是目前位數(也就是MSD)的下一個位數。

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [69, 61]
        
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []          [61]            []            []            []            []            []            []            []           [69]

同樣地，開始走訪所有桶子，尋找所有元素數量大於1的桶子，因為它們還需要再分類！

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [69, 61]
               ○            ○            ○            ○            ○            ○            ○            ○            ○             ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []          [61]            []            []            []            []            []            []            []           [69]

因為已經沒有元素數量大於1的桶子了，就把這個桶子堆3的所有元素，再按照桶子順序塞回原本在桶子堆1的號碼6的桶子中。

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○            ○            ○            ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [61, 69]          [79]          [81]            [9]

接著繼續尋找元素數量大於1的桶子吧！

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○            ○            ○            ○            ○            ○             ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [61, 69]          [79]          [81]            [9]

因為已經沒有元素數量大於1的桶子了，就把這個桶子堆1的所有元素，按照桶子順序串接起來吧！

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○            ○            ○            ○            ○            ○             ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [61, 69]          [79]          [81]            [9]
              └───────────────────────────────┬───────────────────────────────┘
                                                             [2, 30, 32, 38, 47, 61, 69, 79, 81, 9]

可以直接用原陣列來儲存串接結果，如此一來陣列就排序完成了！

基數排序法的實作

LSD──遞增和遞減排序

/// 計數排序法(遞增)，穩定版本。
#[inline]
fn radix_counting_sort_stable(array: &mut [i32], digit: i32) {
    let mut count = [0usize; 19];

    for n in array.iter().copied() {
        let k = (((n / digit) % 10) + 9) as usize;

        count[k] += 1;
    }

    for i in 1..19 {
        count[i] += count[i - 1];
    }

    let origin = array.to_vec();

    for n in origin.into_iter().rev() {
        let k = (((n / digit) % 10) + 9) as usize;

        let c = count.get_mut(k).unwrap();
        *c -= 1;
        array[*c] = n;
    }
}

/// 計數排序法(遞減)，穩定版本。
#[inline]
fn radix_counting_sort_stable_desc(array: &mut [i32], digit: i32) {
    let mut count = [0usize; 19];

    for n in array.iter().copied() {
        let k = (((n / digit) % 10) + 9) as usize;

        count[k] += 1;
    }

    for i in (0..18).rev() {
        count[i] += count[i + 1];
    }

    let origin = array.to_vec();

    for n in origin.into_iter().rev() {
        let k = (((n / digit) % 10) + 9) as usize;

        let c = count.get_mut(k).unwrap();
        *c -= 1;
        array[*c] = n;
    }
}

/// 基數排序法(遞增)，LSD。
pub fn radix_sort_lsd(array: &mut [i32]) {
    let mut digit = 1;

    let max = array.iter().map(|&n| n.abs()).max().unwrap();

    while digit <= max {
        radix_counting_sort_stable(array, digit);

        digit *= 10;
    }
}

/// 基數排序法(遞減)，LSD。
pub fn radix_sort_lsd_desc(array: &mut [i32]) {
    let mut digit = 1;

    let max = array.iter().map(|&n| n.abs()).max().unwrap();

    while digit <= max {
        radix_counting_sort_stable_desc(array, digit);

        digit *= 10;
    }
}

/**
 * 計數排序法(遞增)，穩定版本。
 */
static void radixCountingSortStable(final int[] array, final int digit) {
    final int[] count = new int[19];

    for (final int n : array) {
        final int k = ((n / digit) % 10) + 9;

        ++count[k];
    }

    for (int i = 1; i < 19; ++i) {
        count[i] += count[i - 1];
    }

    final int[] origin = array.clone();

    for (int i = array.length - 1; i >= 0; --i) {
        final int n = origin[i];
        final int k = ((n / digit) % 10) + 9;

        array[--count[k]] = n;
    }
}

/**
 * 計數排序法(遞減)，穩定版本。
 */
static void radixCountingSortStableDesc(final int[] array, final int digit) {
    final int[] count = new int[19];

    for (final int n : array) {
        final int k = ((n / digit) % 10) + 9;

        ++count[k];
    }

    for (int i = 17; i >= 0; --i) {
        count[i] += count[i + 1];
    }

    final int[] origin = array.clone();

    for (int i = array.length - 1; i >= 0; --i) {
        final int n = origin[i];
        final int k = ((n / digit) % 10) + 9;

        array[--count[k]] = n;
    }
}

/**
 * 基數排序法(遞增)，LSD。
 */
public static void radixSortLSD(final int[] array) {
    int digit = 1;

    final int max = IntStream.of(array).map(n -> Math.abs(n)).max().getAsInt();

    while (digit <= max) {
        radixCountingSortStable(array, digit);

        digit *= 10;
    }
}

/**
 * 基數排序法(遞減)，LSD。
 */
public static void radixSortLSDDesc(final int[] array) {
    int digit = 1;

    final int max = IntStream.of(array).map(n -> Math.abs(n)).max().getAsInt();

    while (digit <= max) {
        radixCountingSortStableDesc(array, digit);

        digit *= 10;
    }
}

/**
 * 計數排序法(遞增)，穩定版本。
 */
function radixCountingSortStable(array: number[], digit: number) {
    const count = new Array<number>(19).fill(0);

    for (const n of array) {
        const k = (Math.floor(n / digit) % 10) + 9;

        count[k] += 1;
    }

    for (let i = 1;i < 19;++i) {
        count[i] += count[i - 1];
    }

    const origin = array.slice();

    for (let i = array.length - 1;i >= 0;i--) {
        const n = origin[i];
        const k = (Math.floor(n / digit) % 10) + 9;

        count[k] -= 1;

        array[count[k]] = n;
    }
}

/**
 * 計數排序法(遞減)，穩定版本。
 */
function countingSortStableDesc(array: number[], digit: number) {
    const count = new Array<number>(19).fill(0);

    for (const n of array) {
        const k = (Math.floor(n / digit) % 10) + 9;

        count[k] += 1;
    }

    for (let i = 17;i >= 0;i--) {
        count[i] += count[i + 1];
    }

    const origin = array.slice();

    for (let i = array.length - 1;i >= 0;i--) {
        const n = origin[i];
        const k = (Math.floor(n / digit) % 10) + 9;

        count[k] -= 1;

        array[count[k]] = n;
    }
}

/**
 * 基數排序法(遞增)，LSD。
 */
function radixSortLSD(array: number[]) {
    let digit = 1;

    const max = Math.max(...array.map((n) => Math.abs(n)));

    while (digit <= max) {
        radixCountingSortStable(array, digit);

        digit *= 10;
    }
}

/**
 * 基數排序法(遞減)，LSD。
 */
function radixSortLSDDesc(array: number[]) {
    let digit = 1;

    const max = Math.max(...array.map((n) => Math.abs(n)));

    while (digit <= max) {
        countingSortStableDesc(array, digit);

        digit *= 10;
    }
}

// 計數排序法(遞增)，穩定版本。
func radixCountingSortStable(array []int, digit int) {
	var count [19]int

	for _, n := range array {
		k := ((n / digit) % 10) + 9

		count[k] += 1
	}

	for i := 1; i < 19; i += 1 {
		count[i] += count[i-1]
	}

	length := len(array)

	origin := make([]int, length)
	copy(origin, array)

	for i := length - 1; i >= 0; i -= 1 {
		n := origin[i]
		k := ((n / digit) % 10) + 9

		c := &count[k]
		*c -= 1
		array[*c] = n
	}
}

// 計數排序法(遞減)，穩定版本。
func radixCountingSortStableDesc(array []int, digit int) {
	var count [19]int

	for _, n := range array {
		k := ((n / digit) % 10) + 9

		count[k] += 1
	}

	for i := 17; i >= 0; i -= 1 {
		count[i] += count[i+1]
	}

	length := len(array)

	origin := make([]int, length)
	copy(origin, array)

	for i := length - 1; i >= 0; i -= 1 {
		n := origin[i]
		k := ((n / digit) % 10) + 9

		c := &count[k]
		*c -= 1
		array[*c] = n
	}
}

// 基數排序法(遞增)，LSD。
func RadixSortLSD(array []int) {
	digit := 1

	max := math.MinInt32

	for n := range array {
		if n < 0 {
			n = -n
		}
		
		if max < n {
			max = n
		}
	}

	for digit <= max {
		radixCountingSortStable(array, digit)

		digit *= 10
	}
}

// 基數排序法(遞減)，LSD。
func RadixSortLSDDesc(array []int) {
	digit := 1

	max := math.MinInt32

	for n := range array {
		if n < 0 {
			n = -n
		}

		if max < n {
			max = n
		}
	}

	for digit <= max {
		radixCountingSortStableDesc(array, digit)

		digit *= 10
	}
}

這邊的程式實作是以非常通用的方式來完成，一開始會先找出陣列元素中的最大值，為了拿來判斷目前是否已經看到最高位數。因為輸入的元素有可能會是負數的，所以在尋找最大值的時候要以元素的絕對值為準。另外，計數排序法的部份，會建立出長度為19的計數陣列，這是因為一個位數可能的值為-9 ~ +9，共19種可能。((n / digit) % 10) + 9這個算式是先計算出目前要看的位數的值之後，再進行-(-9)的索引值位移。

MSD──十進制字典排序(穩定排序)

/// 基數排序法(遞增)，MSD，穩定版本。此為用來遞迴呼叫的函數。
fn radix_sort_msd_stable_recursively(array: &mut [i32], d: i32, max_d: i32) {
    if d > max_d {
        return;
    }

    let mut buckets: Vec<Vec<i32>> = vec![Vec::new(); 11];

    for n in array.iter().copied() {
        let n_abs = n.abs();

        let nd = (n_abs as f64).log10() as i32 + 1;

        if d > nd {
            buckets[0].push(n);
        } else {
            let k = ((n_abs / i32::pow(10, (nd - d) as u32)) % 10) as usize + 1;

            buckets[k].push(n);
        }
    }

    for bucket in buckets.iter_mut() {
        if bucket.len() > 1 {
            radix_sort_msd_stable_recursively(bucket, d + 1, max_d);
        }
    }

    let mut p = 0;

    for bucket in buckets {
        for n in bucket {
            array[p] = n;

            p += 1;
        }
    }
}

/// 基數排序法(遞增)，MSD，穩定版本。
pub fn radix_sort_msd_stable(array: &mut [i32]) {
    let mut buckets: Vec<Vec<i32>> = vec![Vec::new(); 2];

    let mut max_0 = 0;
    let mut max_1 = 0;

    for n in array.iter().copied() {
        let k = if n >= 0 {
            if max_1 < n {
                max_1 = n;
            }

            1
        } else {
            if max_0 > n {
                max_0 = n;
            }

            0
        };

        buckets[k].push(n);
    }

    let d_0 = (max_0.abs() as f64).log10() as i32 + 1;
    let d_1 = (max_1 as f64).log10() as i32 + 1;

    radix_sort_msd_stable_recursively(&mut buckets[0], 1, d_0);
    radix_sort_msd_stable_recursively(&mut buckets[1], 1, d_1);

    let mut p = 0;

    for bucket in buckets {
        for n in bucket {
            array[p] = n;

            p += 1;
        }
    }
}

/// 基數排序法(遞減)，MSD，穩定版本。此為用來遞迴呼叫的函數。
fn radix_sort_msd_stable_desc_recursively(array: &mut [i32], d: i32, max_d: i32) {
    if d > max_d {
        return;
    }

    let mut buckets: Vec<Vec<i32>> = vec![Vec::new(); 11];

    for n in array.iter().copied() {
        let n_abs = n.abs();

        let nd = (n_abs as f64).log10() as i32 + 1;

        if d > nd {
            buckets[0].push(n);
        } else {
            let k = ((n_abs / i32::pow(10, (nd - d) as u32)) % 10) as usize + 1;

            buckets[k].push(n);
        }
    }

    for bucket in buckets.iter_mut() {
        if bucket.len() > 1 {
            radix_sort_msd_stable_desc_recursively(bucket, d + 1, max_d);
        }
    }

    let mut p = 0;

    for bucket in buckets.into_iter().rev() {
        for n in bucket {
            array[p] = n;

            p += 1;
        }
    }
}

/// 基數排序法(遞減)，MSD，穩定版本。
pub fn radix_sort_msd_stable_desc(array: &mut [i32]) {
    let mut buckets: Vec<Vec<i32>> = vec![Vec::new(); 2];

    let mut max_0 = 0;
    let mut max_1 = 0;

    for n in array.iter().copied() {
        let k = if n >= 0 {
            if max_1 < n {
                max_1 = n;
            }

            1
        } else {
            if max_0 > n {
                max_0 = n;
            }

            0
        };

        buckets[k].push(n);
    }

    let d_0 = (max_0.abs() as f64).log10() as i32 + 1;
    let d_1 = (max_1 as f64).log10() as i32 + 1;

    radix_sort_msd_stable_desc_recursively(&mut buckets[0], 1, d_0);
    radix_sort_msd_stable_desc_recursively(&mut buckets[1], 1, d_1);

    let mut p = 0;

    for bucket in buckets.into_iter().rev() {
        for n in bucket {
            array[p] = n;

            p += 1;
        }
    }
}

這邊的程式實作是以非常通用的方式來完成，為了要能夠排序正數和負數，因此在最一開始，會先將陣列元素分為負數和正數兩個桶子，再分別對這兩個桶子進行從MSD開始的排序。在桶子堆的桶子數量方面，這邊的程式是使用11個，而不是10個，多出來的那個(索引編號為0)是用來儲存位數比較少的元素，如此一來在遇到[40, 4]的時候，4才會在40的前面，當然，如果沒有要這麼嚴格要求這類的順序的話，一個桶子堆是可以只用10個桶子的！

基數排序法的複雜度