基数排序算法
基数排序是一种逐步排序算法，从输入元素的最低有效位开始排序。与计数排序和桶排序类似，基数排序也假设输入元素均为 k 位数字。
排序从每个元素的最低有效位开始。这些最低有效位都被视为独立元素，并首先排序；然后是第二低有效位。此过程持续进行，直到输入元素的所有数字都已排序。
注意 − 如果元素的位数不同，则找出输入元素中位数最多的数字，并为位数较少的元素添加前导零。此操作不会改变元素的值，但仍使其成为 k 位数字。
基数排序算法
基数排序算法在每个阶段的排序中都使用计数排序算法。详细步骤如下：−
步骤 1 − 检查所有输入元素的位数是否相同。如果不是，则检查列表中位数最多的数字，并为位数最少的数字添加前导零。
步骤 2 −取每个元素的最低有效位。
步骤 3− 使用计数排序逻辑对这些数字进行排序，并根据输出结果更改元素的顺序。例如，如果输入元素是十进制数，则每个数字可能取的值是 0-9，因此请根据这些值对数字进行索引。
步骤 4− 对下一个最低有效位重复步骤 2，直到元素中的所有数字都排序完毕。
步骤 5− 第 k 次循环后获得的最终元素列表即为排序后的输出。
伪代码
Algorithm: RadixSort(a[], n):
// 查找列表的最大元素
max = a[0]
for (i=1 to n-1):
if (a[i]>max):
max=a[i]
// 对输入列表中每个数字中的每个数字进行计数排序
For (pos=1 to max/pos>0):
countSort(a, n, pos)
pos=pos*10
调用的countSort算法将是 −
Algorithm: countSort(a, n, pos)
Initialize count[0…9] with zeroes
for i = 0 to n:
count[(a[i]/pos) % 10]++
for i = 1 to 10:
count[i] = count[i] + count[i-1]
for i = n-1 to 0:
output[count[(a[i]/pos) % 10]-1] = a[i]
i--
for i to n:
a[i] = output[i]
分析
假设输入元素有 k 位数字，基数排序算法的运行时间为 Θ(k(n + b)。其中，n 是输入列表中元素的数量，b 是数字每位数字可能取值的个数。
示例
对于给定的未排序元素列表 236, 143, 26, 42, 1, 99, 765, 482, 3, 56，我们需要执行基数排序并获得排序后的输出列表 −
步骤 1
检查最大位数为 3 的元素。因此，我们在非 3 位数字前添加前导零。我们得到的列表将是 −
236, 143, 026, 042, 001, 099, 765, 482, 003, 056
步骤 2
构建一个表，根据索引存储这些值。由于输入的是十进制数，因此索引是根据这些数字的可能值（即 0-9）进行的。
步骤 3
根据所有数字的最低有效位，将这些数字放在各自的索引上。
此步骤后排序的元素将为 001、042、482、143、003、765、236、026、056、099。
步骤 4
此步骤的输入顺序将是上一步输出的顺序。现在，我们使用第二低有效位进行排序。
最终输出的顺序为 001、003、026、236， 042, 143, 056, 765, 482, 099。
步骤 5
上一步后的输入列表重新排列为 −
001, 003, 026, 236, 042, 143, 056, 765, 482, 099
现在，我们需要对输入元素的最后几位数字进行排序。
由于输入元素中没有其他数字，因此此步骤获得的输出被视为最终输出。
最终排序后的输出为−
1, 3, 26, 42, 56, 99, 143, 236, 482, 765
实现
计数排序算法辅助基数排序，以"d"个循环迭代方式对多个 d 位数字进行排序。本教程使用四种编程语言实现基数排序：C、C++、Java 和 Python。
#include <stdio.h>
void countsort(int a[], int n, int pos){
int output[n + 1];
int max = (a[0] / pos) % 10;
for (int i = 1; i < n; i++) {
if (((a[i] / pos) % 10) > max)
max = a[i];
}
int count[max + 1];
for (int i = 0; i < max; ++i)
count[i] = 0;
for (int i = 0; i < n; i++)
count[(a[i] / pos) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(a[i] / pos) % 10] - 1] = a[i];
count[(a[i] / pos) % 10]--;
}
for (int i = 0; i < n; i++)
a[i] = output[i];
}
void radixsort(int a[], int n){
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
for (int pos = 1; max / pos > 0; pos *= 10)
countsort(a, n, pos);
}
int main(){
int a[] = {236, 15, 333, 27, 9, 108, 76, 498};
int n = sizeof(a) / sizeof(a[0]);
printf("排序前数组元素为：");
for (int i = 0; i <n; ++i) {
printf("%d ", a[i]);
}
radixsort(a, n);
printf("
排序后数组元素为：");
for (int i = 0; i < n; ++i) {
printf("%d ", a[i]);
}
printf("
");
}
输出
排序前数组元素为：236 15 333 27 9 108 76 498 排序后数组元素为：9 15 27 76 108 236 333 498
#include <iostream>
using namespace std;
void countsort(int a[], int n, int pos){
int output[n + 1];
int max = (a[0] / pos) % 10;
for (int i = 1; i < n; i++) {
if (((a[i] / pos) % 10) > max)
max = a[i];
}
int count[max + 1];
for (int i = 0; i < max; ++i)
count[i] = 0;
for (int i = 0; i < n; i++)
count[(a[i] / pos) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(a[i] / pos) % 10] - 1] = a[i];
count[(a[i] / pos) % 10]--;
}
for (int i = 0; i < n; i++)
a[i] = output[i];
}
void radixsort(int a[], int n){
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
for (int pos = 1; max / pos > 0; pos *= 10)
countsort(a, n, pos);
}
int main(){
int a[] = {236, 15, 333, 27, 9, 108, 76, 498};
int n = sizeof(a) / sizeof(a[0]);
cout <<"排序前数组元素为：";
for (int i = 0; i < n; ++i) {
cout <<a[i] << " ";
}
radixsort(a, n);
cout <<"
排序后数组元素为：";
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
cout << "
";
}
输出
排序前数组元素为：236 15 333 27 9 108 76 498 排序后数组元素为：9 15 27 76 108 236 333 498
import java.io.*;
public class Main {
static void countsort(int a[], int n, int pos) {
int output[] = new int[n + 1];
int max = (a[0] / pos) % 10;
for (int i = 1; i < n; i++) {
if (((a[i] / pos) % 10) > max)
max = a[i];
}
int count[] = new int[max + 1];
for (int i = 0; i < max; ++i)
count[i] = 0;
for (int i = 0; i < n; i++)
count[(a[i] / pos) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(a[i] / pos) % 10] - 1] = a[i];
count[(a[i] / pos) % 10]--;
}
for (int i = 0; i < n; i++)
a[i] = output[i];
}
static void radixsort(int a[], int n) {
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
for (int pos = 1; max / pos > 0; pos *= 10)
countsort(a, n, pos);
}
public static void main(String args[]) {
int a[] = {236, 15, 333, 27, 9, 108, 76, 498};
int n = a.length;
System.out.println("排序前数组元素为：");
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
radixsort(a, n);
System.out.println("
排序后数组元素为：");
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
}
}
输出
排序前数组元素为： 236 15 333 27 9 108 76 498 排序后数组元素为： 9 15 27 76 108 236 333 498
def countsort(a, pos):
n = len(a)
output = [0] * n
count = [0] * 10
for i in range(0, n):
idx = a[i] // pos
count[idx % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
idx = a[i] // pos
output[count[idx % 10] - 1] = a[i]
count[idx % 10] -= 1
i -= 1
for i in range(0, n):
a[i] = output[i]
def radixsort(a):
maximum = max(a)
pos = 1
while maximum // pos > 0:
countsort(a, pos)
pos *= 10
a = [236, 15, 333, 27, 9, 108, 76, 498]
print("排序前数组元素为：")
print (a)
radixsort(a)
print("排序后数组元素为：")
print (a)
输出
排序前数组元素为： [236, 15, 333, 27, 9, 108, 76, 498] 排序后数组元素为： [9, 15, 27, 76, 108, 236, 333, 498]
