DSA 基数排序

基数排序

基数排序算法通过对数组中的每个数字逐位排序，从最低有效位（最右边的数字）开始。

基数（或底数）是指一个数制中唯一数字的数量。在通常使用的十进制系统中，有 10 个不同的数字，从 0 到 9。

基数排序使用基数，以便将十进制值放入 10 个不同的桶（或容器）中，这些桶对应于当前关注的数字，然后在移到下一个数字之前将它们放回数组中。

基数排序是一种非比较算法，只能用于非负整数。

基数排序算法可以这样描述

稳定排序

基数排序必须以稳定的方式对元素进行排序，才能确保结果排序正确。

稳定排序算法是一种在排序前后保持相同值元素顺序的算法。假设有两个元素“K”和“L”，其中“K”在“L”之前，它们的值都为“3”。如果排序后元素“K”仍然在“L”之前，则排序算法被认为是稳定的。

对于我们之前单独看过的算法，谈论稳定排序算法意义不大，因为它们是稳定的还是不稳定的，结果都一样。但是，对于基数排序来说，稳定排序很重要，因为元素是每次只按一位数字排序的。

因此，在对最低有效位上的元素进行排序并移到下一个数字之后，重要的是不要破坏已对前一位数字位置完成的排序工作，这就是为什么我们需要确保基数排序以稳定的方式对每个数字位置进行排序的原因。

在下面的模拟中，揭示了桶中底层排序是如何完成的。为了更好地理解稳定排序的工作原理，您还可以选择以不稳定的方式进行排序，这将导致结果不正确。排序变得不稳定，仅仅是将元素从数组的末尾放入桶中，而不是从数组的开头放入桶中。

手动运行

让我们尝试手动进行排序，以便在实际使用编程语言实现之前，更好地理解基数排序的工作原理。

步骤 1：我们从一个未排序的数组和一个空的数组开始，以容纳对应于 0 到 9 的基数的值。

步骤 2：我们从关注最低有效位开始排序。

步骤 3：现在，我们根据当前关注的数字，将元素移到 radixArray 中的正确位置。元素从 myArray 的开头取出，并推入 radixArray 的正确位置。

步骤 4：我们将元素移回初始数组，现在对最低有效位进行排序。元素从 radixArray 的末尾取出，并放入 myArray 的开头。

步骤 5：我们将关注点移到下一个数字。请注意，值 45 和 25 仍然保持着与开始时相同的相对顺序，因为我们以稳定的方式进行排序。

步骤 6：我们根据关注的数字将元素移到 radixArray 中。

步骤 7：我们从 radixArray 的末尾将元素移回到 myArray 的开头。

排序完成！

运行下面的模拟以查看上面步骤的动画。

手动运行：发生了什么？

我们看到值从要排序的数组中取出，并根据当前关注的基数放入 radixArray 中。然后，这些值被移回到我们想要排序的数组中。

这种从要排序的数组中取出值并移回的步骤必须执行的次数与值中最大数字的位数相同。例如，如果要排序的数组中最大的数字是 437，我们知道我们必须排序三次，每次对一个数字排序。

我们还看到 radixArray 需要是二维的，以便在特定基数或索引上存储多个值。

而且，正如之前提到的，我们必须以一种保持具有相同基数的值顺序的方式在两个数组之间移动值，以便排序是稳定的。

基数排序实现

要实现基数排序算法，我们需要

1. 一个需要排序的包含非负整数的数组。
2. 一个索引从 0 到 9 的二维数组，用来存放当前关注的基数的值。
3. 一个循环，从未排序的数组中取出值并将其放入二维 radixArray 中的正确位置。
4. 一个循环，将值从 radixArray 放回初始数组。
5. 一个外部循环，运行的次数与最大值中的数字位数相同。

生成的代码如下所示

myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixArray = [[], [], [], [], [], [], [], [], [], []]
maxVal = max(myArray)
exp = 1

while maxVal // exp > 0:

    while len(myArray) > 0:
        val = myArray.pop()
        radixIndex = (val // exp) % 10
        radixArray[radixIndex].append(val)

    for bucket in radixArray:
        while len(bucket) > 0:
            val = bucket.pop()
            myArray.append(val)

    exp *= 10

print("Sorted array:", myArray)

在第 7 行，我们使用地板除法（“//”）将最大值 802 除以 1，这是 while 循环第一次运行时，下次除以 10，最后一次除以 100。使用地板除法“//”时，小数点后的任何数字都会被忽略，并返回一个整数。

在第 11 行，根据值的基数（或当前关注的数字）决定将其放入 radixArray 中的位置。例如，外部 while 循环第二次运行时，exp 将为 10。值 170 除以 10 将得到 17。操作“%10”将除以 10 并返回余数。在本例中，17 除以 10 一次，余数为 7。因此，值 170 将被放置在 radixArray 的索引 7 中。

使用其他排序算法的基数排序

基数排序实际上可以与任何其他排序算法一起实现，只要它是稳定的。这意味着在对特定数字进行排序时，任何稳定的排序算法都可以工作，例如计数排序或冒泡排序。

这是一个使用冒泡排序对各个数字进行排序的基数排序实现

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                
def radixSortWithBubbleSort(arr):
    max_val = max(arr)
    exp = 1
    
    while max_val // exp > 0:
        radixArray = [[],[],[],[],[],[],[],[],[],[]]
        
        for num in arr:
            radixIndex = (num // exp) % 10
            radixArray[radixIndex].append(num)
        
        for bucket in radixArray:
            bubbleSort(bucket)
        
        i = 0
        for bucket in radixArray:
            for num in bucket:
                arr[i] = num
                i += 1
        
        exp *= 10

myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixSortWithBubbleSort(myArray)
print("Sorted array:", myArray)

基数排序时间复杂度

有关时间复杂度的概述，请访问 此页面。

有关基数排序时间复杂度的更详细解释，请访问 此页面。

基数排序的时间复杂度是

\[ \underline{\underline{O(n \cdot k)}} \]

这意味着基数排序既依赖于需要排序的值 \(n\)，也依赖于最大值中的数字位数 \(k\)。

基数排序的最佳情况是当待排序的值很多，但每个值的位数很少。例如，如果有超过一百万个值需要排序，而最大值是 999，只有三位数。在这种情况下，时间复杂度 \(O(n \cdot k)\) 可以简化为 \(O(n)\)。

基数排序的最坏情况是当最大值中的位数与待排序的值数量相同。这可能不是常见情况，但这种情况下时间复杂度将是 \(O(n^2)\)。

最常见的情况可能是当位数 \(k\) 与 \(k(n)= \log n\) 相似。如果是这样，基数排序的时间复杂度为 \(O(n \cdot \log n )\)。例如，如果有 1000000 个值要排序，而这些值有 6 位数。

下图显示了基数排序的不同时间复杂度。

运行基数排序的不同模拟，以查看操作次数如何介于最坏情况 \(O(n^2)\)（红线）和最佳情况 \(O(n)\)（绿线）之间。

代表不同值的条形图已按窗口大小缩放，以使它们看起来正常。这意味着具有 7 位数的值看起来只比具有 2 位数的值大 5 倍，但实际上，具有 7 位数的值实际上比具有 2 位数的值大 5000 倍！

如果我们固定 \(n\) 和 \(k\)，上述模拟中的“随机”、“降序”和“升序”选项会导致相同的操作次数。这是因为这三种情况下的操作方式相同。

Radix Sort must use a  
sorting algorithm.