数据结构中的基数排序算法
陈莎拉
什么是基数排序算法？
基数排序是一种非比较排序算法。它的工作原理是将要排序的元素的各个数字分组。然后使用稳定的排序技术根据元素的基数来组织元素。它是一种线性排序算法。
排序过程涉及以下属性：
- 找到最大元素并获取该元素的位数。它为我们提供了排序过程将遵循的迭代次数。
- 在每次迭代中将元素的各个数字分组到相同的有效位置。
- 分组过程将从最低有效数字开始，到最高有效数字结束。
- 根据有效位置的数字对元素进行排序。
- 保持具有相同键值的元素的相对顺序。基数排序的这一特性使其成为一种稳定排序。
最后的迭代将给我们一个完全排序的列表。
基数排序算法的工作原理
让我们尝试使用基数排序算法按升序对上图中的整数列表进行排序。
以下是执行基数排序过程的步骤：
步骤1） 确定列表中具有最大值的元素。在本例中，该元素为 835。
步骤2） 计算最大元素的位数。835 正好有 3 位数字。
步骤3） 根据步骤2确定迭代次数。835有3位数字，这意味着迭代次数将为3。
步骤4） 确定元素的基数。由于这是十进制，因此基数为 10。
步骤5） 开始第一次迭代。
a）第一次迭代
在第一次迭代中，我们考虑每个元素的个位值。
步骤1） 对整数取 10 的模数，得到元素的个位。例如，623 取模 10 得到值 3，248 取模 10 得到值 8。
步骤2） 使用计数排序或任何其他稳定排序，根据整数的最低有效数字对其进行组织。如图所示，248 将落在第 8 个存储桶中。623 将落在第 3 个存储桶中，依此类推。
第一次迭代之后，列表现在如下所示。
从上图可以看出，列表尚未排序，需要更多迭代才能完全排序。
b）第二次迭代
在这次迭代中，我们将考虑 10 处的数字th 进行分类过程的地方。
步骤1） 将整数除以 10。248 除以 10 得到 24。
步骤2） 将步骤 1 的输出除以 10。24 除以 10 得到 4。
步骤3） 按照上一次迭代中的步骤 2 进行。
第二次迭代后，列表现在如下所示
从上图可以看出，列表仍未完全排序，因为它尚未按升序排列。
c）第三次迭代
对于最后一次迭代，我们希望获得最高有效位。在本例中，最高有效位是 100th 列表中每个整数的位置。
步骤1） 将整数除以 100...415 除以 100 得到 4。
步骤2） 将步骤 1 的结果除以 10。4 除以 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 of the elements in the jthplace 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 integers
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 using 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
input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)
输出：
[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.
基数排序与其他比较算法的比较
正如我们所见，Radix 排序的复杂度取决于字或数字的大小。在平均和最佳情况下，它的复杂度相同。即 O(d*(n+b))。此外，根据您在中间使用的排序技术，它也会有所不同。例如，您可以在 Radix 排序中使用计数排序或快速排序作为中间排序算法。
基数排序算法的应用
基数排序的重要应用是：
- 基数排序可用作使用大范围值的位置查找算法。
- 它用于构建DC3算法中的后缀数组。
- 它用于典型计算机中按顺序随机存取的机器中，对记录进行键入。
