基數排序

December 10, 2021

基數排序(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 的桶子:

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 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