排序算法 之 基数排序（Radix Sort）

排序算法 之 基数排序（Radix Sort）

1. 基础概念

1.1 定义

基数排序是一种基于“分配”和“收集”思想的排序算法，通过从最低位到最高位（或反之）对元素分布到“桶”中并依次收集，实现有序排列。

1.2 特点

• 时间复杂度较低，适用于数据位数较小的场景。
• 稳定排序：不会改变值相同元素的相对顺序。
• 需要额外空间：通常使用桶来辅助排序。

1.3 使用场景

常用于需要对整数、字符串或固定格式数据进行高效排序的场景，例如电子计分、邮政编码等。

2. 实现与操作

2.1 核心操作实现

以下提供基于C语言的基数排序实现：

#include <stdio.h> #include <stdlib.h> #include <string.h> // 获取数字的某一位 int getDigit(int num, int exp) { return (num / exp) % 10; } // 基数排序核心函数 void radixSort(int arr[], int n) { int max = arr[0]; // 找到数组中的最大值 for (int i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } // 动态分配10个桶，每个桶存储一个整数数组 int *buckets[10]; int bucketSizes[10] = {0}; // 每个桶的大小 for (int i = 0; i < 10; i++) { buckets[i] = (int *)malloc(n * sizeof(int)); } for (int exp = 1; max / exp > 0; exp *= 10) { memset(bucketSizes, 0, sizeof(bucketSizes)); // 重置桶大小 // 将数字放入桶中 for (int i = 0; i < n; i++) { int digit = getDigit(arr[i], exp); buckets[digit][bucketSizes[digit]++] = arr[i]; } // 从桶中取出元素，覆盖到原数组 int index = 0; for (int i = 0; i < 10; i++) { for (int j = 0; j < bucketSizes[i]; j++) { arr[index++] = buckets[i][j]; } } } // 释放桶内存 for (int i = 0; i < 10; i++) { free(buckets[i]); } } // 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 主函数 int main() { int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); printArray(arr, n); radixSort(arr, n); printf("排序后数组: "); printArray(arr, n); return 0; } </string.h></stdlib.h></stdio.h>

2.2 代码详解

• 函数`getDigit`用于提取数字在特定位的值（个位、十位等）。
• 在每次循环中，依据当前位数将数字分配到对应的桶（0-9）。
• 遍历桶中的数字，按顺序收集到原数组，实现部分排序。
• 代码设计保证稳定性，同时动态分配内存提高灵活性。

3. 时间与空间复杂度分析

3.1 时间复杂度

• 每一位排序需遍历所有n个数字，复杂度为O(n)。
• 假设数字最多有d位，总复杂度为O(d*n)。
• 基数b影响每次操作，平均复杂度为O(d*(n+b))。

3.2 空间复杂度

需要额外桶空间，总复杂度为O(n+b)，其中b为桶数量。

4. 优缺点与局限性

4.1 优点

• 适合大量整数排序，效率高。
• 对输入数据分布较为均匀时性能表现优异。

4.2 缺点与局限性

• 对输入数据依赖较强（如需要整数、固定格式）。
• 需要额外空间存储桶。
• 不适用于浮点数或负数排序。

5. 常见应用场景

5.1 实际应用

基数排序常用于财务、邮政编码等固定格式数据的排序场景。

6. 代码编译与运行

6.1 编译命令

使用以下命令编译和运行：

    gcc radix_sort.c -o radix_sort && ./radix_sort
        

6.2 测试用例

示例运行结果：

    原始数组: 170 45 75 90 802 24 2 66 
    排序后数组: 2 24 45 66 75 90 170 802