基数排序（Radix Sort）是一种非比较性的排序算法，它将整数按照位数进行排序。基数排序的基本原理是从低位到高位依次对整数进行排序，通过多次分配和收集来实现排序。
基数排序的基本原理如下：
1. **按位排序**：从最低位开始，对整数进行按位排序。可以使用计数排序或桶排序等方法对每一位进行排序。
2. **多次分配和收集**：对每一位排序后，根据当前位的排序结果重新排列整数序列，重复这个过程直到所有位都被考虑过。
3. **稳定性**：基数排序要求用于排序的算法是稳定的，以保证低位排序的结果不会影响高位的排序结果。
4. **输出排序结果**：最终完成所有位的排序后，得到有序的整数序列。
基数排序的特点：
- 基数排序是稳定的排序算法。
- 时间复杂度为 O(d*(n+k))，其中 d 是数字位数，n 是元素个数，k 是基数（0-9 为 10）。
- 适用于整数位数较少的情况，对于位数很大的整数排序，可能会导致较高的时间复杂度。
基数排序通常用于整数排序，特别是位数相同的整数排序，例如对手机号码、学号等进行排序。基数排序在某些情况下可以比快速排序和归并排序更快，尤其是对于大量整数的排序。以下是用 C++ 实现基数排序的示例代码：
```cpp #include <iostream> #include <vector> // 获取数组中的最大值 int getMax(std::vector<int>& arr) { int max = arr[0]; for (int num : arr) { if (num > max) { max = num; } } return max; } // 对数组按照指定位数进行计数排序 void countingSort(std::vector<int>& arr, int exp) { int n = arr.size(); std::vector<int> output(n); std::vector<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(std::vector<int>& arr) { int max = getMax(arr); for (int exp = 1; max / exp > 0; exp *= 10) { countingSort(arr, exp); } } void printArray(const std::vector<int>& arr) { for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; } int main() { std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66}; int n = arr.size(); std::cout << "Original array: "; printArray(arr); radixSort(arr); std::cout << "Sorted array: "; printArray(arr); return 0; } ```
在这段代码中，`radixSort` 函数实现了基数排序算法，包括获取数组中的最大值、按位计数排序和基数排序。`countingSort` 函数用于对数组按照指定位数进行计数排序。`printArray` 函数用于打印数组的元素。在 `main` 函数中定义了一个整型数组并对其进行基数排序。
