說明
在之前所介紹過的排序方法，都是屬於「比較性」的排序法，也就是每次排序時 ，都是比較整個鍵值的大小以進行排序。
這邊所要介紹的「基數排序法」（radix sort）則是屬於「分配式排序」（distribution
sort），基數排序法又稱「桶子法」（bucket sort）或bin
sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間複雜度為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相反，是由高位數為基底開始進行分配，其他的演
算方式則都相同。
實作
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
int temp[10][10] = {0};
int order[10] = {0};
int i, j, k, n, lsd;
k = 0;
n = 1;
printf("\n排序前: ");
for(i = 0; i < 10; i++)
printf("%d ", data[i]);
putchar('\n');
while(n <= 10) {
for(i = 0; i < 10; i++) {
lsd = ((data[i] / n) % 10);
temp[lsd][order[lsd]] = data[i];
order[lsd]++;
}
printf("\n重新排列: ");
for(i = 0; i < 10; i++) {
if(order[i] != 0)
for(j = 0; j < order[i]; j++) {
data[k] = temp[i][j];
printf("%d ", data[k]);
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
}
putchar('\n');
printf("\n排序後: ");
for(i = 0; i < 10; i++)
printf("%d ", data[i]);
return 0;
}
public class RadixSort {
public static void sort(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 i = 0; i < number.length; i++) {
int lsd = ((number[i] / n) % 10);
temp[lsd][order[lsd]] = number[i];
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};
RadixSort.sort(data, 100);
for(int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
}
|
|