基数排序算法
- 基数排序算法
- 实现
基数排序是一种逐步排序算法，它从输入元素的 least significant digit（最低有效位）开始排序。类似于 Counting Sort 和 Bucket Sort，基数排序也对输入元素做出假设，即它们都是 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[09] 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。
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("Before sorting array elements are: ");
for (int i = 0; i <n; ++i) {
printf("%d ", a[i]);
}
radixsort(a, n);
printf("\nAfter sorting array elements are: ");
for (int i = 0; i < n; ++i) {
printf("%d ", a[i]);
}
printf("\n");
}
输出
Before sorting array elements are: 236 15 333 27 9 108 76 498 After sorting array elements are: 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 <<"Before sorting array elements are: ";
for (int i = 0; i < n; ++i) {
cout <<a[i] << " ";
}
radixsort(a, n);
cout <<"\nAfter sorting array elements are: ";
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
cout << "\n";
}
输出
Before sorting array elements are: 236 15 333 27 9 108 76 498 After sorting array elements are: 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("Before sorting array elements are: ");
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
radixsort(a, n);
System.out.println("\nAfter sorting array elements are: ");
for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
}
}
输出
Before sorting array elements are: 236 15 333 27 9 108 76 498 After sorting array elements are: 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("Before sorting array elements are: ")
print (a)
radixsort(a)
print("After sorting array elements are: ")
print (a)
输出
Before sorting array elements are: [236, 15, 333, 27, 9, 108, 76, 498] After sorting array elements are: [9, 15, 27, 76, 108, 236, 333, 498]