基數排序

基數排序（radix sort）屬於分配排序（distribution sort），用於根據某個基數，對元素進行分配排序。如果是數字，基數會是個位數、十位數、百位數等；座標的話，基數就是 x、y、z，例如先根據 x 排序，接著 y、z；單字的話，每個字母可以是基數，例如依字典順序。

解法思路

基數排序可使用桶子（bucket），透過鍵值的部份資訊，將要排序的元素分配至某些桶，藉以達到排序的作用。以數字為例，可以採用 LSD（Least sgnificant digital）或 MSD（Most sgnificant digital），LSD 由鍵值的最右邊開始，而 MSD 相反，由鍵值的最左邊開始。

以 LSD 為例，若數列為 73、22、93、43、55、14、28、65、39、81，首先根據個位數，在走訪數值時將它們分配至編號 0 到 9 的桶子：

1	2	3	4	5	8	9
81				65		39
		43	14	55	28
		93
	22	73

接下來將桶子中的數值重新串接，成為數列 81、22、73、93、43、14、55、65、28、39，接著根據十位數來分配：

0	1	2	3	4	5	6	7	8	9
		28	39						39
	14	22		43	55	65	73	81	93

接下來將桶子中的數值重新串接起來，成為數列 14、22、28、39、43、55、65、73、81、93，這時候數列已經排序完成；若排序的對象有三位數以上，持續進行以上的動作直至最高位數為止。

LSD 的基數排序適用於基數個數少的數列，如果基數個數多的話，使用 MSD 的效率會比較好，MSD 的方式與 LSD 相反，由高位數為基底開始進行分配，其餘演算方式相同。

程式實作

#include <stdio.h> 
#include <stdlib.h> 

void radixSort(int[]);

int main(void) { 
    int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81}; 
      
    printf("\n排序前: "); 
    int i;
    for(i = 0; i < 10; i++) 
        printf("%d ", data[i]); 

    putchar('\n'); 

    radixSort(data);
    
    printf("\n排序後: "); 
    for(i = 0; i < 10; i++) 
        printf("%d ", data[i]); 

    return 0; 
} 

void radixSort(int data[]) {
    int temp[10][10] = {0}; 
    int order[10] = {0}; 
    
    int n = 1; 
    while(n <= 10) { 
        
        int i;
        for(i = 0; i < 10; i++) { 
            int lsd = ((data[i] / n) % 10); 
            temp[lsd][order[lsd]] = data[i]; 
            order[lsd]++; 
        } 
        
        // 重新排列
        int k = 0;
        for(i = 0; i < 10; i++) { 
            if(order[i] != 0)  {
                int j;
                for(j = 0; j < order[i]; j++, k++) { 
                    data[k] = temp[i][j]; 
                } 
            }
            order[i] = 0; 
        } 

        n *= 10; 
    }     
}

public class Sort {
    public static void radix(int[] number, int d) {
        int k = 0;
        int n = 1;
        
        int[][] temp = new int[number.length][number.length];
        int[] order = new int[number.length];
        
        while(n <= d) { 
            for(int num : number) { 
                int lsd = (num / n) % 10; 
                temp[lsd][order[lsd]] = num; 
                order[lsd]++; 
            } 

            for(int i = 0; i < number.length; i++) { 
                if(order[i] != 0) {
                    for(int j = 0; j < order[i]; j++) { 
                        number[k] = temp[i][j];  
                        k++; 
                    } 
                }
                order[i] = 0; 
            } 

            n *= 10; 
            k = 0; 
        } 
    }

    public static void main(String[] args) {
        int[] data = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100}; 
        Sort.radix(data, 100);
        for(int i : data) {
            System.out.print(i + " ");   
        }
    }
}

def sort(number, d):
    length = len(number)
    k = 0
    n = 1
    temp = []
    for i in range(length):
        temp.append([0] * length)
    order = [0] * length
    while n <= d:
        for i in range(length):
            lsd = (number[i] // n) % 10
            temp[lsd][order[lsd]] = number[i]
            order[lsd] += 1
        for i in range(length):
            if order[i] != 0:
                for j in range(order[i]):
                    number[k] = temp[i][j]
                    k += 1
            order[i] = 0
        n *= 10
        k = 0
        
number = [73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100]
sort(number, 100)
print(number)

object Sort {
    def radix(number: Array[Int], d: Int) {
        var k = 0
        var n = 1
        val temp = new Array[Array[Int]](number.length, number.length)
        val order = new Array[Int](number.length)
        while(n <= d) {
            number.foreach(num => {
                val lsd = (num / n) % 10
                temp(lsd)(order(lsd)) = num
                order(lsd) += 1
            })
            for(i <- 0 until number.length) {
                if(order(i) != 0) {
                    for(j <- 0 until order(i)) {
                        number(k) = temp(i)(j)
                        k += 1
                    }
                }
                order(i) = 0
            }
            n *= 10
            k = 0
        }
    }
}

val data = Array(73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100)
Sort.radix(data, 100)
data.foreach(x => print(x + " "))

def sort(number, d)
    length = number.length
    k = 0
    n = 1
    temp = Array.new(length) {
        Array.new(length, 0)
    }
    order = Array.new(length, 0)
    while n <= d
        length.times { |i|
            lsd = (number[i] / n) % 10
            temp[lsd][order[lsd]] = number[i]
            order[lsd] += 1
        }
        length.times { |i|
            if order[i] != 0
                order[i].times { |j|
                    number[k] = temp[i][j]
                    k += 1
                }
            end
            order[i] = 0
        }
        n *= 10
        k = 0
    end
end

number = [73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100]
sort(number, 100)
p number

function lsd(n, d) {
    return Math.floor(n / (10 ** (d - 1))) % 10;
}

function radixSort(lt, digits) {
    if(lt.length == 0) {
        return lt;
    }
    
    function _radixSort(lt, digits, counter) {
        if(counter > digits) {
            return lt;
        }
        
        let buckets = [[], [], [], [], [], [], [], [], [], []];
        for(let n of lt) {
            buckets[lsd(n, counter)].push(n);
        }
        return _radixSort(buckets.flat(), digits, counter + 1);
    }
    
    return _radixSort(lt, digits, 1);
}

let lt = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11];
console.log(radixSort(lt, 2));

radixSort [] _ = []
radixSort xs digits = _radixSort xs digits 1
    where 
    _radixSort xs digits counter =
        if counter > digits then xs
        else
            let buckets = [[]| i<- [0..9]]
                rvlt = map (\elem -> (lsd elem counter, elem)) xs
                nlt = concat $ foldl reducer buckets rvlt
            in _radixSort nlt digits (counter + 1)
    lsd n d = (n `div` (10 ^ (d - 1))) `mod` 10
    reducer buckets (radix, elem) =
        map (\i -> if radix == i then (buckets !! i) ++ [elem]
                   else buckets !! i) [0..9]

main = print $ radixSort [10, 9, 1, 2, 5, 3, 8, 7, 12, 11] 2