跳到主要内容

基数排序算法

提示
  1. 基本概念：基数排序是一种非比较排序算法，它通过对数组中的元素按位数分组并根据每个位的值进行排序。
  2. 排序过程：首先找出数组中的最大元素，然后按照从最低有效位到最高有效位的顺序，使用稳定的排序算法（如计数排序）对元素进行排序。
  3. 应用和效率：基数排序适用于处理大范围数字，其时间复杂度为线性，但由于使用额外的空间来存储中间排序结果，空间效率较低。

基数排序是一种排序算法，它首先将元素按照各个位数分组，然后根据它们的递增/递减顺序对元素进行排序。

假设我们有一个包含8个元素的数组。首先，我们将根据个位的值对元素进行排序。然后，我们将根据十位的值对元素进行排序。这个过程一直持续到最后一个有效位。

让我们假设初始数组为[121, 432, 564, 23, 1, 45, 788]。按照基数排序的方式排序如下图所示。

基数排序工作原理

在阅读本文之前，请先学习计数排序，因为计数排序在基数排序中用作中间排序。

基数排序的工作原理​

  1. 找到数组中的最大元素，记为max。令X为max中的数字位数。我们计算X，因为我们必须遍历所有元素的有效位。

    在数组[121, 432, 564, 23, 1, 45, 788]中，最大数字为788，它有3位数字。因此，循环应该执行到百位数（3次）。

  2. 依次遍历每个有效位。

    使用任何稳定的排序技术，按照每个有效位上的数字对元素进行排序。我们在这里使用计数排序。

    根据个位数字（X=0）对元素进行排序。 基数排序使用计数排序作为中间步骤的工作方式

  3. 接下来，根据十位上的数字对元素进行排序。 基数排序步骤

  4. 最后，根据百位上的数字对元素进行排序。 基数排序步骤

基数排序算法​

radixSort(array)
  d <- 最大元素中的位数
  创建大小为0-9的d个桶
  for i 从 0 到 d
    使用计数排序，根据第i位数字对元素进行排序

countingSort(array, d)
  max <- 在d位元素中找到最大的元素
  初始化一个包含全0的计数数组
  for j 从 0 到 数组大小
    找到元素的第d位上每个唯一数字的总计数，并将计数存储在计数数组的j索引处
  for i 从 1 到 max
    找到累计总和并存储在计数数组中
  for j 从 数组大小 到 1
    恢复元素到数组中
    减少每个恢复的元素的计数值1

Python、Java 和 C/C++ 中的基数排序代码​

Python Java C C++

# Python中的基数排序


# 使用计数排序按照位数的重要性来排序元素
def countingSort(array, place):
    size = len(array)
    output = [0] * size
    count = [0] * 10

    # 计算元素的个数
    for i in range(0, size):
        index = array[i] // place
        count[index % 10] += 1

    # 计算累计个数
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 按排序后的顺序放置元素
    i = size - 1
    while i >= 0:
        index = array[i] // place
        output[count[index % 10] - 1] = array[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(0, size):
        array[i] = output[i]


# 实现基数排序的主要函数
def radixSort(array):
    # 获取最大元素
    max_element = max(array)

    # 应用计数排序以根据位数值排序元素。
    place = 1
    while max_element // place > 0:
        countingSort(array, place)
        place *= 10


data = [121, 432, 564, 23, 1, 45, 788]
radixSort(data)
print(data)
// Java编程中的基数排序

import java.util.Arrays;

class RadixSort {

  // 使用计数排序按照有效位排序元素
  void countingSort(int array[], int size, int place) {
    int[] output = new int[size + 1];
    int max = array[0];
    for (int i = 1; i < size; i++) {
      if (array[i] > max)
        max = array[i];
    }
    int[] count = new int[max + 1];

    for (int i = 0; i < max; ++i)
      count[i] = 0;

    // 计算元素的个数
    for (int i = 0; i < size; i++)
      count[(array[i] / place) % 10]++;

    // 计算累计个数
    for (int i = 1; i < 10; i++)
      count[i] += count[i - 1];

    // 按排序后的顺序放置元素
    for (int i = size - 1; i >= 0; i--) {
      output[count[(array[i] / place) % 10] - 1] = array[i];
      count[(array[i] / place) % 10]--;
    }

    for (int i = 0; i < size; i++)
      array[i] = output[i];
  }

  // 获取数组中的最大元素
  int getMax(int array[], int n) {
    int max = array[0];
    for (int i = 1; i < n; i++)
      if (array[i] > max)
        max = array[i];
    return max;
  }

  // 实现基数排序的主要函数
  void radixSort(int array[], int size) {
    // 获取最大元素
    int max = getMax(array, size);

    // 应用计数排序以根据位数值排序元素。
    for (int place = 1; max / place > 0; place *= 10)
      countingSort(array, size, place);
  }

  // 主程序
  public static void main(String args[]) {
    int[] data = { 121, 432, 564, 23, 1, 45, 788 };
    int size = data.length;
    RadixSort rs = new RadixSort();
    rs.radixSort(data, size);
    System.out.println("按升序排序的数组：");
    System.out.println(Arrays.toString(data));
  }
}
// C编程中的基数排序

#include <stdio.h>

// 从数组中获取最大元素
int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}

// 使用计数排序按有效位排序元素
void countingSort(int array[], int size, int place) {
  int output[size + 1];
  int max = (array[0] / place) % 10;

  for (int i = 1; i < size; i++) {
    if (((array[i] / place) % 10) > max)
      max = array[i];
  }
  int count[max + 1];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  // 计算元素的个数
  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;

  // 计算累计个数
  for (int i = 1; i < 10; i++)
    count[i] += count[i - 1];

  // 按排序后的顺序放置元素
  for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}

// 实现基数排序的主要函数
void radixsort(int array[], int size) {
  // 获取最大元素
  int max = getMax(array, size);

  // 应用计数排序以根据位数值排序元素。
  for (int place = 1; max / place > 0; place *= 10)
    countingSort(array, size, place);
}

// 打印数组
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {


 printf("%d  ", array[i]);
  }
  printf("\n");
}

// 主程序
int main() {
  int array[] = {121, 432, 564, 23, 1, 45, 788};
  int n = sizeof(array) / sizeof(array[0]);
  radixsort(array, n);
  printArray(array, n);
}

希望这些代码和解释对你有帮助。如果你有任何问题，请随时提问。

基数排序算法（C++编程）​

基数排序是一种高效的排序方法，它根据元素的每一位来分配和收集元素。

基数排序代码示例（C++）​

#include <iostream>
using namespace std;

// 获取数组中的最大元素
int getMax(int array[], int n) {
  int max = array[0];
  for (int i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}

// 使用计数排序来基于重要位对元素进行排序
void countingSort(int array[], int size, int place) {
  const int max = 10;
  int output[size];
  int count[max];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  // 计算每个元素的数量
  for (int i = 0; i < size; i++)
    count[(array[i] / place) % 10]++;

  // 计算累积数量
  for (int i = 1; i < max; i++)
    count[i] += count[i - 1];

  // 根据排好的顺序放置元素
  for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i] / place) % 10] - 1] = array[i];
    count[(array[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}

// 实现基数排序的主要功能
void radixsort(int array[], int size) {
  // 获取最大元素
  int max = getMax(array, size);

  // 基于每个位的值应用计数排序
  for (int place = 1; max / place > 0; place *= 10)
    countingSort(array, size, place);
}

// 打印数组
void printArray(int array[], int size) {
  for (int i = 0; i < size; i++)
    cout << array[i] << " ";
  cout << endl;
}

// 驱动代码
int main() {
  int array[] = {121, 432, 564, 23, 1, 45, 788};
  int n = sizeof(array) / sizeof(array[0]);
  radixsort(array, n);
  printArray(array, n);
}

基数排序的复杂度​

时间复杂度 
最佳O(n+k)
最差O(n+k)
平均O(n+k)
空间复杂度O(max)
------
稳定性是
------

由于基数排序是一种非比较排序算法，它相较于比较排序算法具有一定的优势。

基数排序使用计数排序作为稳定的中间排序时，时间复杂度为O(d(n+k))。

这里，d是循环的次数，O(n+k)是计数排序的时间复杂度。

因此，基数排序的时间复杂度是线性的，比比较排序算法的O(nlog n)更好。 如果我们处理非常大的数字或其他进制的数字，例如32位和64位的数字，基数排序可以在线性时间内执行，但中间排序会占用大量空间。

这使得基数排序在空间上效率较低。这也是为什么这种排序不常用于软件库中的原因。

基数排序的应用领域​

基数排序在以下情况下被使用：

  • 在制作后缀数组时使用了DC3算法（Kärkkäinen-Sanders-Burkhardt）。
  • 处理数字范围很大的情况下。

类似的排序算法​

  1. 快速排序
  2. 归并排序
  3. 桶排序
  4. 计数排序
最后于 更新