基数排序（Radix Sort）是一种非比较性的排序算法，它将整数按位数逐个排序，每个位数的排序采用稳定的排序算法，最终得到有序序列。本文将详细介绍基数排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。
基数排序的基本思想
基数排序的核心思想是将整数按位数切割成不同的数字，然后按每个位上的数字分组。具体步骤如下：
1.确定位数： 确定待排序整数的最大位数，作为排序的轮数。
2.按位分组： 将整数按位数分成个位、十位、百位等不同组，从最低位开始。
3.每个位上的排序： 对每个位上的数字进行稳定排序，可以选择计数排序等。
4.合并： 合并每个位上的数字，得到最终有序序列。
基数排序的示例
让我们通过一个示例来理解基数排序的工作原理。假设我们有一个整数数组 [170, 45, 75, 90, 802, 24, 2, 66]，我们希望按升序排序它。
1.确定位数： 最大整数是802，有3位数字，因此需要3轮排序。
2.按位分组： 将整数按个位数字分组。
桶0: [170, 90] 桶1: [801] 桶2: [802, 2] 桶3: [] 桶4: [] 桶5: [75] 桶6: [66] 桶7: [] 桶8: [] 桶9: [45, 24]
1.每个位上的排序： 对每个位上的数字进行稳定排序，这里选择计数排序。
第一轮（个位）： 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.合并： 得到最终有序序列。
排序后的数组: [2, 24, 45, 66, 75, 90, 170, 801, 802]
基数排序的时间复杂度
基数排序的时间复杂度取决于稳定排序算法的时间复杂度以及位数。假设n是待排序元素的数量，k是元素的位数，t是稳定排序算法的时间复杂度。
1.每位的排序时间： O(n + t)
2.总的排序时间： 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; }
以上示例代码展示了不同编程语言中的基数排序算法实现。这些示例帮助你理解基数排序的工作原理，并提供了可供参考和使用的代码示例。基数排序是一种适用于整数排序的高效稳定的排序算法。
