基数排序

#sort #algorithm

import time
def radix_sort(nums):
    """
    基数排序

    Args:
        nums (list[int]): 待排序的数字列表

    Returns:
        list[int]: 排序后的数字列表
    """
    max_digit = max(nums)
    for digit in range(1, max_digit + 1):
        buckets = [[] for _ in range(10)]
        for num in nums:
            buckets[(num // digit) % 10].append(num)
        i = 0
        for bucket in buckets:
            for num in bucket:
                nums[i] = num
                i += 1
    print(buckets)
    return nums
t = time.time()
res=radix_sort([10,9,78,3,4,90,9000123])
dur = time.time() - t
print(dur)
print(res)

#include<vector>
#include<chrono>
class Solution {
public:
    int maximumGapvector<int>& nums {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        int exp = 1;
        std::vector<int> buf(n);
        int maxVal = *std::max_element(nums.begin(), nums.end());

        while (maxVal >= exp) {
            // 数字长度固定是0-9,且cnt每次只记录一个数位的排序
            std::vector<int> cnt(10);
            // 针对nums中所有的数字中各个数位进行排序，从个位开始，百位，千位等等
            for (int i = 0; i < n; i++) {
                int digit = (nums[i] / exp) % 10;
                // cnt中的index对应当前位的数字，value对应当前位都是index的个数
                cnt[digit]++;
            }
            // 如果cnt[7] = 4, 表示当前位数字是7的num有4个，
            // 这四个后面实际升序位置是cnt[1] + cnt[2] + .. + cnt[6] ~ cnt[1] + cnt[2] + .. cnt[6] + cnt[7]
            for (int i = 1; i < 10; i++) {
                cnt[i] += cnt[i - 1];
            }
            // 根据排序结果进行更新
            for (int i = n - 1; i >= 0; i--) {
                int digit = (nums[i] / exp) % 10;
                buf[cnt[digit] - 1] = nums[i];
                // 上一步给的位置是当前数字最大index，后续相同数字的需要往前排
                cnt[digit]--;
            }
            // 每次数位排完序后更新到nums
            copy(buf.begin(), buf.end(), nums.begin());
            exp *= 10;
        }

        int ret = 0;
        for (int i = 1; i < n; i++) {
            ret = std::max(ret, nums[i] - nums[i - 1]);
        }
        return ret;
    }
};
Solution s
std::vector<int> input = {100,10,19,2389,89,12,9000999}
auto start = std::chrono::high_resolution_clock::now();
std::cout<<"max gap:"<< s.maximumGap(input)
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "time in seconds: " << duration.count()
// std::cout<<duration
input

//作者：力扣官方题解
//链接：https://leetcode.cn/problems/maximum-gap/solutions/498428/zui-da-jian-ju-by-leetcode-solution/