数据结构中的基数排序算法

由： 陈莎拉 陈莎拉
Hours 更新

什么是基数排序算法？

基数排序是一种非比较排序算法。它的工作原理是将要排序的元素的各个数字分组。然后使用稳定的排序技术根据元素的基数来组织元素。它是一种线性排序算法。

排序过程涉及以下属性：

  • 找到最大元素并获取该元素的位数。它为我们提供了排序过程将遵循的迭代次数。
  • 在每次迭代中将元素的各个数字分组到相同的有效位置。
  • 分组过程将从最低有效数字开始，到最高有效数字结束。
  • 根据有效位置的数字对元素进行排序。
  • 保持具有相同键值的元素的相对顺序。基数排序的这一特性使其成为一种稳定排序。

最后的迭代将给我们一个完全排序的列表。

基数排序算法的工作原理

基数排序算法的工作原理
要排序的整数列表

让我们尝试使用基数排序算法按升序对上图中的整数列表进行排序。

以下是执行基数排序过程的步骤：

步骤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算法中的后缀数组。
  • 它用于典型计算机中按顺序随机存取的机器中，对记录进行键入。

你可能会喜欢：