数据结构中的基数排序算法
陈莎拉
什么是基数排序算法？
基数排序是一种非比较排序算法。它的工作原理是分组排序。ping 首先确定待排序元素的各个数字。然后使用一种稳定的排序方法，根据元素的基数对其进行排序。这是一种线性排序算法。
排序过程涉及以下属性：
- 找到最大元素并获取该元素的位数。这便可得出排序过程所需的迭代次数。
- 的Grouping 每次迭代中相同有效位置的元素的各个数字。
- 该团体ping 处理过程从最低有效数字开始，到最高有效数字结束。
- 根据有效数字对元素进行排序。
- 保持具有相同键值的元素之间的相对顺序。基数排序的这一特性使其成为一种稳定排序算法。
最后一次迭代返回一个完全排序的列表。
基数排序算法的工作原理
要排序的整数列表
让我们使用基数排序法对上图中的整数列表进行升序排序。
以下是执行基数排序过程的步骤：
步骤1） 找出列表中的最大元素。这里是 835。
步骤2） 数一数它的位数。835 有 3 位数字，所以迭代次数为 3。
步骤3） 确定基数。由于这是十进制数，所以基数是10。
步骤4） 开始第一次迭代。
a）第一次迭代
按最后一位数字排序
在第一次迭代中，我们考虑每个元素的个位值。
步骤1） 将整数除以 10 取模，即可得到元素的个位数。例如，623 除以 10 的余数为 3，248 除以 10 的余数为 8。
步骤2） 使用计数排序或其他稳定排序算法，根据整数的最低有效数字对其进行排序。如图所示，248 落入第 8 个桶，623 落入第 3 个桶，依此类推。
第一次迭代之后，列表现在如下所示。
第一次迭代后的列表
列表尚未排序，需要更多迭代。
b）第二次迭代
根据十位数字排序
在本轮迭代中，我们考虑十位上的数字进行排序。
步骤1） 将整数除以 10。例如，248 除以 10 等于 24。
步骤2） 将步骤 1 的输出结果乘以 10 取模。24 mod 10 等于 4。
步骤3） 按照上一轮迭代中的步骤 2 进行操作。
经过第二次迭代，列表现在看起来像这样：
第二次迭代后的列表
该列表尚未完全排序，因为它还没有按升序排列。
c）第三次迭代
按百位数字排序
在最后一次迭代中，我们希望得到最高有效位。在本例中，它是列表中每个整数的百位。
步骤1） 将整数除以 100。例如，415 除以 100 等于 4。
步骤2） 将步骤 1 的结果除以 10 取模。4 mod 10 等于 4。
步骤3） 按照上一轮迭代中的步骤 3 进行操作。
第三次迭代后的列表
列表已按升序排序。最后一次迭代已完成，排序过程结束。
基数排序算法的伪代码
以下是基数排序算法的伪代码：
radixSortAlgo(arr as an array) Find the largest element in arr maximum = the element in arr that is the largest Find the number of digits in maximum k = the number of digits in maximum Create buckets of size 0-9 k times for j -> 0 to k Acquire the jth place of each element in arr. Here j = 0 represents the least significant digit. Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits in the jth place arr = sorted elements
C++ 实现基数排序的程序
#include <iostream> using namespace std; // Function to get the largest element in an array int getMaximum(int arr[], int n) { int maximum = arr[0]; for (int i = 1; i < n; i++) { if (maximum < arr[i]) maximum = arr[i]; } return maximum; } // We are using counting sort to sort the elements digit by digit void countingSortAlgo(int arr[], int size, int position) { const int limit = 10; int result[size]; int count[limit] = {0}; // Calculating the count of each integer for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++; // Calculating the cumulative count for (int j = 1; j < limit; j++) { count[j] += count[j - 1]; } // Sort the integers for (int j = size - 1; j >= 0; j--) { result[count[(arr[j] / position) % 10] - 1] = arr[j]; count[(arr[j] / position) % 10]--; } for (int i = 0; i < size; i++) arr[i] = result[i]; } // The radixSort algorithm void radixSortAlgo(int arr[], int size) { // Get the largest element in the array int maximum = getMaximum(arr, size); for (int position = 1; maximum / position > 0; position *= 10) countingSortAlgo(arr, size, position); } // Printing final result void printResult(int arr[], int size) { for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl; } int main() { int arr[] = {162, 623, 835, 415, 248}; int size = sizeof(arr) / sizeof(arr[0]); radixSortAlgo(arr, size); printResult(arr, size); }
输出：
162 248 415 623 835
Python 基数排序算法程序
# Radix Sort in Python def countingSortAlgo(arr, position): n = len(arr) result = [0] * n count = [0] * 10 # Calculating the count of elements in the array arr for j in range(0, n): element = arr[j] // position count[element % 10] += 1 # Calculating the cumulative count for j in range(1, 10): count[j] += count[j - 1] # Sorting the elements i = n - 1 while i >= 0: element = arr[i] // position result[count[element % 10] - 1] = arr[i] count[element % 10] -= 1 i -= 1 for j in range(0, n): arr[j] = result[j] def radixSortAlgo(arr): # Acquiring the largest element in the array maximum = max(arr) # Using counting sort to sort digit by digit position = 1 while maximum // position > 0: countingSortAlgo(arr, position) position *= 10 data = [162, 623, 835, 415, 248] radixSortAlgo(data) print(data)
输出：
[162, 248, 415, 623, 835]
基数排序的复杂度分析
需要考虑两种类型的复杂性：空间复杂性和时间复杂性。
- 空间复杂度： O(n + b)，其中 n 是数组的大小，b 是所考虑的基数。
- 时间复杂度： O(d * (n + b))，其中 d 是数组中最大元素的位数。
基数排序的空间复杂度
空间复杂性的两个重点特征：
- 数组中元素的数量， n.
- 用于表示元素的基础 b.
有时，这个基数可能大于数组的大小。因此，整体复杂度为 O(n + b)。
列表中元素的以下属性会导致基数排序的空间效率低下：
- 具有大量数字的元素。
- 元素的基数很大，如 64 位数字。
基数排序的时间复杂度
使用计数排序作为子程序，每次迭代需要 O(n + b) 时间。如果存在 d 次迭代，则总运行时间变为 O(d * (n + b))这里，“O”表示复杂度函数。
基数排序的线性
基数排序在以下情况下是线性的：
- d 是常数，其中 d 是最大元素的位数。
- b 并不比 n.
基数排序与其他排序方法的比较 Algorithms
基数排序的复杂度取决于数据量的大小。最佳情况和平均情况的复杂度均为 O(d * (n + b))。性能取决于内部排序算法——计数排序是标准算法，但任何稳定的排序算法都可以。
基数排序算法的应用
基数排序的重要应用包括：
- 基数排序可以用作定位算法，尤其适用于涉及大范围数值的情况。
- 它用于在 DC3 算法中构建后缀数组。
- 它用于顺序随机存取机器，其中记录由固定宽度的标识符作为键。
