# 基數排序

December 10, 2021

## 解法思路

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

0 1 2 3 4 5 6 7 8 9
28 39 39
14 22 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};

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

putchar('\n');

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

return 0;
}

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

if(lt.length == 0) {
return lt;
}

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

}

let lt = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11];
``````
``````radixSort [] _ = []
where