基数排序算法图文详解
- 作者: 嗳祢莪等祢
- 来源: 51数据库
- 2022-09-23
本节您将系统学习基数排序算法，还会看到实现基数排序算法的 C、Java 以及 Python 程序。
阅读本文前，请您先学习计数排序算法，因为基数排序算法的实现会用到计数排序算法。
基数排序算法适用于对包含多个数值或者字符串的序列做升序或降序排序，例如：
{121, 432, 564, 23, 1, 45, 788}
{"zhangsan","lisi","wangwu"}
基数排序算法的核心思想是：从低位到高位，依次提取出待排序列各个元素中相同位置上的数字（或字符），通过比较它们的大小调整各个元素的位置，最终实现升序或者降序排序。
以对 {121, 432, 564, 23, 1, 45, 788} 做升序排序为例，下图演示了基数排序算法的实现过程：
图 1 基数排序算法的实现过程
首先提取出各个元素个位上的数字，根据它们的大小调整各个元素的位置。然后提取出各个元素十位上的数字，再根据它们的大小调整各个元素的位置。最后提取出各个元素百位上的数字，根据它们的大小调整各个元素的位置。最终得到的序列即为排好序的序列。
基数排序算法的工作原理
这里，我们给您具体讲解对 {121, 432, 564, 23, 1, 45, 788} 进行基数排序的具体实现过程。
1) 首先，找到序列中的最大值，并记录该元素具有的位数。显然整个序列中的最大值为 788，它由 3 个数字组成。这意味着，在根据位数对各个元素进行比较时，我们需要依次根据个位数、十位数和百位数对序列中的各个元素进行排序。
2) 根据个位数进行排序，这里需要使用计数排序算法对各个元素进行排序，具体的排序过程如下图所示：
图 2 采用计数排序算法根据个位数进行排序
图中，array 数组中存储的是序列中各个元素的个位数，count 数组中记录的是 array 数组中各个元素出现次数的累加和，output 数组中记录的是排序后各个元素所处的位置。
3) 以同样的方法，根据各个元素十位上的数字进行排序，此时 array 数组中的数据为 {2, 0, 3, 2, 6, 4, 8}，排序结果为：
4) 以同样的方法，根据各个元素百位上的数字进行排序，此时 array 数组中的数据为 {0, 1, 0, 4, 0, 5, 7}，排序结果为：
如下为实现基数排序算法的伪代码：
//基数排序算法，array 为待排序序列
radixSort(array):
max = getMax(array) // 查找 array 序列中的最大值
place <- 1 // 默认从个位开始排序
while max/place > 0 : // 结合最大值的数位，直至按照各个数位全部进行了排序，整个排序过程才算完成
countingSort(array,place) // 调用计数排序算法，根据所选数位对各个元素进行排序
place = place * 10
//计数排序算法，array 为待排序序列，place 指排序所依照的数位
countingSort(array, place)
size <- len(array) // 获取 array 序列中的元素个数
max <- (array[0] / place) % 10 // 根据 place，找到相应数位值最大的元素
for i <- 1 to size:
if (array[i] / place) % 10 > max：
max <- array[i]
for j <- 0 to size // 创建 count[max+1] 并统计各个元素的出现次数
count[(array[i] / place) % 10] <- count[(array[i] / place) % 10] + 1
for i <- 1 to max // 对 count[max+1] 存储的元素做累加操作
count[i] <- count[i] + count[i - 1];
for j <- size down to 0 // 根据 count[max+1] 中的累加值，找到各个元素排序后的具体位置
output[count[(array[i] / place) % 10] - 1] <- array[i];
count[(array[i] / place) % 10] <- count[(array[i] / place) % 10] - 1 // 确定一个元素的位置后，count[max+1] 中相应位置的数值要减 1
return output[size]
基数排序算法的具体实现
如下为实现基数排序算法的 C 语言程序：
#include <stdio.h>
#define N 7
#define MAX 100 //限制各个元素各数位上的值不能超过 100
//计数排序算法，place 表示以指定数位为准，对序列中的元素进行排序
void countingSort(int array[], int place) {
int output[N];
//假设第一个元素指定数位上的值最大
int max = (array[0] / place) % 10;
//找到真正数位上值最大的元素
for (int i = 1; i < N; i++) {
if (((array[i] / place) % 10) > max)
max = array[i];
}
//初始化一个 count 数组
int count[MAX] = {0};
//统计各个元素出现的次数
for (int i = 0; i < N; i++)
count[(array[i] / place) % 10]++;
//累加 count 数组中的出现次数
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
//根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
for (int i = N - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
//将 output 数组中的数据原封不动地拷贝到 array 数组中
for (int i = 0; i < N; i++)
array[i] = output[i];
}
//找到整个序列中的最大值
int getMax(int array[]) {
int max = array[0];
for (int i = 1; i < N; i++)
if (array[i] > max)
max = array[i];
return max;
}
//基数排序算法
void radixSort(int array[]) {
//找到序列中的最大值
int max = getMax(array);
//根据最大值具有的位数，从低位依次调用计数排序算法
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, place);
}
//输出 array 数组中的数据
void printArray(int array[]) {
for (int i = 0; i < N; ++i) {
printf("%d ", array[i]);
}
}
int main() {
int array[N] = { 121, 432, 564, 23, 1, 45, 788 };
radixSort(array);
printArray(array);
}
如下为实现基数排序算法的 Java 程序：
import java.util.Arrays;
public class Demo {
// 计数排序算法，place 表示以指定数位为准，对序列中的元素进行排序
public static void countingSort(int array[], int place) {
int size = array.length;
int[] output = new int[size];
// 假设第一个元素指定数位上的值最大
int max = (array[0] / place) % 10;
// 找到真正数位上值最大的元素
for (int i = 1; i < size; i++) {
if (((array[i] / place) % 10) > max)
max = array[i];
}
// 创建并初始化 count 数组
int[] count = new int[max + 1];
for (int i = 0; i < max; ++i)
count[i] = 0;
// 统计各个元素出现的次数
for (int i = 0; i < size; i++)
count[(array[i] / place) % 10]++;
// 累加 count 数组中的出现次数
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// 根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
// 将 output 数组中的数据原封不动地拷贝到 array 数组中
for (int i = 0; i < size; i++)
array[i] = output[i];
}
// 找到整个序列中的最大值
public static int getMax(int array[]) {
int size = array.length;
int max = array[0];
for (int i = 1; i < size; i++)
if (array[i] > max)
max = array[i];
return max;
}
// 基数排序算法
public static void radixSort(int array[]) {
// 找到序列中的最大值
int max = getMax(array);
// 根据最大值具有的位数，从低位依次调用计数排序算法
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, place);
}
public static void main(String args[]) {
int[] data = { 121, 432, 564, 23, 1, 45, 788 };
radixSort(data);
System.out.println(Arrays.toString(data));
}
}
如下为实现基数排序算法的 Python 程序：
格式化复制
array = [121, 432, 564, 23, 1, 45, 788] #计数排序算法，place 表示以指定数位为准，对序列中的元素进行排序 def countingSort(array, place): size = len(array) output = [0] * size max_element = int(array[0] // place) % 10 for i in range(1,size): if (array[i] // place) % 10 > max_element: max_element = array[i] count = [0] * (max_element+1) #统计 count 数组中各元素的出现次数 for i in range(0, size): count[(array[i]//place) % 10] += 1 #累加 count 数组中的出现次数 for i in range(1, max_element): count[i] += count[i - 1] #根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中 i = size - 1 while i >= 0: output[count[(array[i]//place) % 10] - 1] = array[i] count[(array[i]//place) % 10] -= 1 i -= 1 #将 output 数组中的数据原封不动地拷贝到 array 数组中 for i in range(0, size): array[i] = output[i] # 基数排序算法 def radixSort(array): # 找到序列中的最大值 max_element = max(array) # 根据最大值具有的位数，从低位依次调用计数排序算法 place = 1 while max_element//place : countingSort(array, place) place *= 10 radixSort(array) print(array)
以上程序的执行结果为：
1 23 45 121 432 564 788
