基数排序（Radix Sort）是一种非比较性的排序算法，它将整数按位数逐个排序，每个位数的排序采用稳定的排序算法，最终得到有序序列。本文将详细介绍基数排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。
基数排序的基本思想
基数排序的核心思想是将整数按位数切割成不同的数字，然后按每个位上的数字分组。具体步骤如下：
- 确定位数： 确定待排序整数的最大位数，作为排序的轮数。
- 按位分组： 将整数按位数分成个位、十位、百位等不同组，从最低位开始。
- 每个位上的排序： 对每个位上的数字进行稳定排序，可以选择计数排序等。
- 合并： 合并每个位上的数字，得到最终有序序列。
基数排序的示例
让我们通过一个示例来理解基数排序的工作原理。假设我们有一个整数数组 [170, 45, 75, 90, 802, 24, 2, 66]，我们希望按升序排序它。
- 确定位数： 最大整数是802，有3位数字，因此需要3轮排序。
- 按位分组： 将整数按个位数字分组。
桶0: [170, 90]
桶1: [801]
桶2: [802, 2]
桶3: []
桶4: []
桶5: [75]
桶6: [66]
桶7: []
桶8: []
桶9: [45, 24]- 每个位上的排序： 对每个位上的数字进行稳定排序，这里选择计数排序。
- 第一轮（个位）：
170, 90, 801, 802, 2, 75, 66, 45, 24 - 第二轮（十位）：
801, 802, 2, 24, 45, 66, 75, 170, 90 - 第三轮（百位）：
2, 24, 45, 66, 75, 90, 170, 801, 802
- 合并： 得到最终有序序列。
排序后的数组: [2, 24, 45, 66, 75, 90, 170, 801, 802]基数排序的时间复杂度
基数排序的时间复杂度取决于稳定排序算法的时间复杂度以及位数。假设n是待排序元素的数量，k是元素的位数，t是稳定排序算法的时间复杂度。
- 每位的排序时间： O(n + t)
- 总的排序时间： O(k * (n + t))
综合起来，基数排序的时间复杂度为O(k * (n + t))。
基数排序是一种稳定的排序算法，适用于整数排序。它在元素位数较小且范围确定的情况下表现出色。
示例代码
以下是基数排序的示例代码，分别使用Python、Go、Java和C语言编写。
Python 基数排序
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
# 统计每个位上的数字出现次数
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
# 计算累积频次
for i in range(1, 10):
count[i] += count[i - 1]
# 根据位数排序
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# 将排序结果复制回原数组
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("排序后的数组:", arr)Go 基数排序
package main
import (
"fmt"
)
func countingSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
// 统计每个位上的数字出现次数
for i := 0; i < n; i++ {
index := arr[i] / exp % 10
count[index]++
}
// 计算累积频次
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
// 根据位数排序
for i := n - 1; i >= 0; i-- {
index := arr[i] / exp % 10
output[count[index]-1] = arr[i]
count[index]--
}
// 将排序结果复制回原数组
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func radixSort(arr []int) {
maxNum := arr[0]
n := len(arr)
// 找到最大值
for i := 1; i < n; i++ {
if arr[i] > maxNum {
maxNum = arr[i]
}
}
exp := 1
// 逐位排序
for maxNum/exp > 0 {
countingSort(arr, exp)
exp *= 10
}
}
func main() {
arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
radixSort(arr)
fmt.Println("排序后的数组:", arr)
}Java 基数排序
import java.util.Arrays;
public class RadixSort {
public static void countingSort(int arr[], int exp) {
int n = arr.length;
int output[] = new int[n];
int count[] = new int[10];
// 统计每个位上的数字出现次数
for (int i = 0; i < n; i++) {
int index = arr[i] / exp % 10;
count[index]++;
}
// 计算累积频次
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 根据位数排序
for (int i = n - 1; i >= 0; i--) {
int index = arr[i] / exp % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
// 将排序结果复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
public static void radixSort(int arr[]) {
int maxNum = Arrays.stream(arr).max().getAsInt();
int exp = 1;
while (maxNum / exp > 0) {
countingSort(arr, exp);
exp *= 10;
}
}
public static void main(String[] args) {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
System.out.print("排序后的数组: ");
System.out.println(Arrays.toString(arr));
}
}C 语言 基数排序
#include <stdio.h>
void countingSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
// 统计每个位上的数字出现次数
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// 计算累积频次
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 根据位数排序
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// 将排序结果复制回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
void radixSort(int arr[], int n) {
int maxNum = arr[0];
// 找到最大值
for (int i = 1; i < n; i++) {
if (arr[i] > maxNum) {
maxNum = arr[i];
}
}
int exp = 1;
// 逐位排序
while (maxNum / exp > 0) {
countingSort(arr, n, exp);
exp *= 10;
}
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radixSort(arr, n);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}以上示例代码展示了不同编程语言中的基数排序算法实现。这些示例帮助你理解基数排序的工作原理，并提供了可供参考和使用的代码示例。基数排序是一种适用于整数排序的高效稳定的排序算法。
