基數排序法

說明

在之前所介紹過的排序方法，都是屬於「比較性」的排序法，也就是每次排序時，都是比較整個鍵值的大小以進行排序。

這邊所要介紹的「基數排序法」（radix sort）則是屬於「分配式排序」（distribution sort），基數排序法會使用到「桶子」（bucket），顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的比較性排序法。

解法

基數排序的方式可以採用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

以LSD為例，假設原來有一串數值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：

0	1	2	3	4	5	6	7	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
	14	22		43	55	65	73	81	93

接下來將這些桶子中的數值重新串接起來，成為以下的數列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。

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

實作：C Java Python Scala Ruby

#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; 
    }     
}

Java

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 + " ");   
        }
    }
}

Python

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)

Scala

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 + " "))

Ruby

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