数据结构与算法Python版：基数排序

简介：基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog?m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。通常有两种方法：LSD（Least Significant Digit，最小有效位排序）和MSD（Most Significant Digit，最大有效位排序）。基数排序的效率依赖于内部操作的速度。

历史攻略：

Python基础入门 1 - 230题

Golang基础练习 1 - 40题

实现原理：基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

Python语言描述：

import math


def bucket_sort(a, radix=10):
    """a为整数列表， radix为基数"""
    if not a:  # 检查列表是否为空
        return a
    max_val = max(a)
    if max_val <= 0:  # 检查最大值是否大于0
        return a
    K = int(math.ceil(math.log(max_val, radix)))  # 用K位数可表示任意整数
    bucket = [[] for _ in range(radix)]  # 不能用 [[]]*radix
    for i in range(1, K + 1):  # K次循环
        for val in a:
            # 使用整数除法
            bucket_index = (val // (radix ** (i - 1))) % radix
            bucket[bucket_index].append(val)  # 析取整数第K位数字 （从低到高）
        del a[:]
        for each in bucket:
            a.extend(each)  # 桶合并
        bucket = [[] for _ in range(radix)]
    return a

案例源码：3题

# -*- coding: utf-8 -*-
# time: 2023/12/17 17:18
# file: bucket_sort_demo.py
# 公众号: 玩转测试开发

from typing import List


# 164. 最大间距
# 给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
# 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
# 示例 1:
# 输入: nums = [3,6,9,1]
# 输出: 3
# 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
# 示例 2:
# 输入: nums = [10]
# 输出: 0
# 解释: 数组元素个数小于 2，因此返回 0。


class Solution164:
    def maximumGap(self, nums: List[int]) -> int:
        # 思路
        # 1、排序
        # 2、设置无限小。
        # 3、如果数组长度小于2.返回0
        # 4、如果长度大于2. 从第二个开始遍历。每次如果间距大于前一个结果，则替换结果。不大于则继续。
        # 5、结束返回

        if len(nums) < 2:
            return 0
        else:
            nums.sort()
            res = float("-inf")
            for index, value in enumerate(nums[1:]):
                tmp = value - nums[index]
                if tmp > res:
                    res = tmp
                else:
                    continue
        return res


s164 = Solution164()
r164 = s164.maximumGap([3, 6, 9, 1, 22])
print(f"r164:{r164}")  # r164:13

# 912. 排序数组
# 给你一个整数数组 nums，请你将该数组升序排列。
# 示例 1：
# 输入：nums = [5,2,3,1]
# 输出：[1,2,3,5]
# 示例 2：
# 输入：nums = [5,1,1,2,0,0]
# 输出：[0,0,1,1,2,5]

import math


class Solution912:
    def sortArray(self, nums: List[int]) -> List[int]:
        # return sorted(nums)

        def bucket_sort(a, radix=10):
            """a为整数列表， radix为基数"""
            if not a:  # 检查列表是否为空
                return a
            max_val = max(a)
            if max_val <= 0:  # 检查最大值是否大于0
                return a
            K = int(math.ceil(math.log(max_val, radix)))  # 用K位数可表示任意整数
            bucket = [[] for _ in range(radix)]  # 不能用 [[]]*radix
            for i in range(1, K + 1):  # K次循环
                for val in a:
                    # 使用整数除法
                    bucket_index = (val // (radix ** (i - 1))) % radix
                    bucket[bucket_index].append(val)  # 析取整数第K位数字 （从低到高）
                del a[:]
                for each in bucket:
                    a.extend(each)  # 桶合并
                bucket = [[] for _ in range(radix)]
            return a

        bucket_sort(nums)
        return nums


s912 = Solution912()
input_912 = [50, 21, 32, 11]
r912 = s912.sortArray(input_912)
print(f"r912:{r912}")  # r912:[11, 21, 32, 50]


# 2343. 裁剪数字后查询第 K 小的数字
# 给你一个下标从 0 开始的字符串数组 nums ，其中每个字符串 长度相等 且只包含数字。
# 再给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ki, trimi] 。对于每个 queries[i] ，你需要：
# 将 nums 中每个数字 裁剪 到剩下 最右边 trimi 个数位。在裁剪过后的数字中，找到 nums 中第 ki 小数字对应的 下标 。
# 如果两个裁剪后数字一样大，那么下标 更小 的数字视为更小的数字。
# 将 nums 中每个数字恢复到原本字符串。请你返回一个长度与 queries 相等的数组 answer，其中 answer[i]是第 i 次查询的结果。
# 提示：
# 裁剪到剩下最右边 x 个数位的意思是不断删除最左边的数位，直到剩下 x 个数位。
# nums 中的字符串可能会有前导 0 。
# 示例 1：
# 输入：nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]
# 输出：[2,2,1,0]
# 解释：
# 1. 裁剪到只剩 1 个数位后，nums = ["2","3","1","4"] 。最小的数字是 1 ，下标为 2 。
# 2. 裁剪到剩 3 个数位后，nums 没有变化。第 2 小的数字是 251 ，下标为 2 。
# 3. 裁剪到剩 2 个数位后，nums = ["02","73","51","14"] 。第 4 小的数字是 73 ，下标为 1 。
# 4. 裁剪到剩 2 个数位后，最小数字是 2 ，下标为 0 。
#    注意，裁剪后数字 "02" 值为 2 。
#
# 示例 2：
# 输入：nums = ["24","37","96","04"], queries = [[2,1],[2,2]]
# 输出：[3,0]
# 解释：
# 1. 裁剪到剩 1 个数位，nums = ["4","7","6","4"] 。第 2 小的数字是 4 ，下标为 3 。
#    有两个 4 ，下标为 0 的 4 视为小于下标为 3 的 4 。
# 2. 裁剪到剩 2 个数位，nums 不变。第二小的数字是 24 ，下标为 0 。

class Solution2343:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        result = []

        for i in queries:
            tmp = []
            for j in nums:
                tmp.append(j[-i[-1]:])
            tmp = [(int(i), index) for index, i in enumerate(tmp)]
            tmp.sort()
            result.append(tmp[i[0] - 1][-1])
        return result


s2343 = Solution2343()
r2343 = s2343.smallestTrimmedNumbers(nums=["24", "37", "96", "04"], queries=[[2, 1], [2, 2]])
print(f"r2343:{r2343}")  # r2343:[3, 0]

运行结果：

r164:13
r912:[11, 21, 32, 50]
r2343:[3, 0]