企业官网建设流程全解析

在数据结构与算法领域，基数排序是一种基于桶排序思想的非比较排序算法，它通过按位处理元素的每一位来实现排序，在处理整数、固定长度字符串等具有明确数位特征的数据时，能达到线性时间复杂度。本文将结合视频中的可视化流程，深入解析基数排序的原理，并提供可直接运行的 C 语言实现代码。

一、基数排序核心概念

1. 算法基本思想

基数排序的核心思想是 “按位排序、逐位收集”，通过对元素的每一位（从最低位到最高位）进行多轮桶排序，最终得到有序序列。它利用了桶排序的稳定性，确保每一轮排序后，低位的排序结果不会被高位的排序破坏。

2. 关键参数说明

• 基数（Radix）：通常取 10（十进制），表示每一位的取值范围是 0~9。
• 最大位数（d）：待排序元素中最大数的位数，决定了需要进行的排序轮数。
• 桶（Bucket）：用于暂存每一位排序过程中的元素，基数为 10 时需要 10 个桶。

二、可视化流程解析（以 12 个三位数为例）

视频中以[329, 457, 657, 839, 436, 720, 355, 273, 514, 162, 801, 945]为例，完整演示了基数排序的执行过程：

阶段 1：按个位（10⁰）排序

• 分配阶段：将所有元素按个位数字分配到 0~9 的桶中，例如720和801的个位是 0，放入 0 号桶；162和273的个位是 2 和 3，分别放入 2 号桶和 3 号桶。
• 收集阶段：按桶的顺序（0→9）将元素依次收集回主数组，得到[720, 801, 162, 273, 514, 355, 945, 436, 457, 657, 329, 839]。

阶段 2：按十位（10¹）排序

• 分配阶段：将上一轮得到的数组按十位数字分配到 0~9 的桶中，例如801和514的十位是 0 和 1，分别放入 0 号桶和 1 号桶；329和436的十位是 2 和 3，分别放入 2 号桶和 3 号桶。
• 收集阶段：按桶的顺序收集元素，得到[801, 514, 720, 329, 436, 839, 945, 355, 457, 657, 162, 273]。

阶段 3：按百位（10²）排序

• 分配阶段：将上一轮得到的数组按百位数字分配到 0~9 的桶中，例如162和273的百位是 1 和 2，分别放入 1 号桶和 2 号桶；329和355的百位是 3，放入 3 号桶。
• 收集阶段：按桶的顺序收集元素，最终得到完全有序的数组[162, 273, 329, 355, 436, 457, 514, 657, 720, 801, 839, 945]。

三、算法复杂度与特性

基数排序的核心优势在于其线性时间复杂度，其复杂度特性如下：

• 时间复杂度：O (d・(N+K))，其中 d 为最大位数，N 为元素个数，K 为基数（通常为 10）。在 d 较小的情况下，时间复杂度接近 O (N)，优于快速排序等比较排序算法。
• 空间复杂度：O (N+K)，需要额外的桶空间和临时数组空间。
• 算法稳定性：稳定排序，因为每一轮桶排序都是按先进先出的顺序收集元素，相同数位的元素相对顺序保持不变。
• 适用场景：适合排序整数、固定长度字符串等具有明确数位特征的数据，尤其是当数据位数较少时，性能优势显著。

四、C 语言完整实现代码

以下是基数排序的 C 语言实现，包含按位分配、收集的完整逻辑，可直接编译运行：

#include <stdio.h> #include <stdlib.h> #include <string.h> // 获取数组中的最大值 int getMax(int arr[], int n) { int max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } // 按指定位数进行桶排序 void countSort(int arr[], int n, int exp) { int *output = (int *)malloc(n * sizeof(int)); // 临时输出数组 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]--; } // 将输出数组复制回原数组 memcpy(arr, output, n * sizeof(int)); free(output); } // 基数排序主函数 void radixSort(int arr[], int n) { int max = getMax(arr, n); // 获取最大值，确定最大位数 // 从最低位到最高位依次进行桶排序 for (int exp = 1; max / exp > 0; exp *= 10) { countSort(arr, n, exp); } } // 打印数组 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {329, 457, 657, 839, 436, 720, 355, 273, 514, 162, 801, 945}; int size = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); printArray(arr, size); // 调用基数排序 radixSort(arr, size); printf("排序后数组: "); printArray(arr, size); return 0; }

代码说明

• getMax函数：获取数组中的最大值，用于确定需要排序的位数。
• countSort函数：按指定位数进行桶排序，通过计数数组统计每个桶中的元素个数，再将元素放入临时输出数组，最后复制回原数组。
• radixSort函数：从最低位到最高位依次调用countSort函数，完成基数排序。
• exp参数：表示当前处理的位数，初始为 1（个位），每次乘以 10（十位、百位……）。

五、应用场景与总结

基数排序在数据处理、计算机科学、信息学奥赛等领域具有广泛应用。其线性时间复杂度使其成为处理大规模整数数据的理想选择，尤其是在数据位数较少的情况下，性能优势显著。虽然基数排序的适用范围相对有限（仅适用于具有明确数位特征的数据），但在其适用场景下，它是一种非常高效的排序算法。

💖 点赞 + 收藏 + 关注，获取更多数据结构与算法的深度解析！