chapter_sorting/radix_sort/

[giscus[bot]]

chapter_sorting/radix_sort/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_sorting/radix_sort/

[GyBernstein]

个数转索引 巧妙的方法啊

[krahets]

确实，这也是计数排序的难点

[newcakes]

c++语言
// 倒序遍历，根据桶内统计结果，将各元素填入 res
vector res(n, 0);
for (int i = n - 1; i >= 0; i--) {
int d = digit(nums[i], exp);
int j = counter[d] - 1; // 获取 d 在数组中的索引 j
res[j] = nums[i]; // 将当前元素填入索引 j
counter[d]--; // 将 d 的数量减 1
}
这里为什么要倒序遍历呀！我试了一下正序遍历，结果是错的，但不知道是什么原因？就解答！
@krahets

[hhhxxxddd]

逆序是稳定的，因为counter[]中保存的本来就是元素的最大索引，所以相等的元素在排序后的相对位置不会变化
正序不稳定，如果有几个相同元素，那么第一个碰到的反而会放到最后面了

在计数排序里面只有一次排序可能无所谓，正序逆序都行，但是这个基数排序排了几轮，比如：
第一轮 ：01 12 13 14 15 16 07

那么第二轮就必须要让01和07的相对位置保持不变才行，因为第二轮的排序完全不会去考虑个位
所以如果是不稳定的正序相当于只是在排十位，整个就乱套了

[HustRobb]

//计数排序正序尝试
void countingSortDigit(vector<int> &nums, int exp) {
    // 十进制的位范围为 0~9 ，因此需要长度为 10 的桶
    vector<int> counter(10, 0);
    int n = nums.size();
    // 统计 0~9 各数字的出现次数
    for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp); // 获取 nums[i] 第 k 位，记为 d
        counter[d]++;                // 统计数字 d 的出现次数
    }
    // 求前缀和，将“出现个数“转换为第一次出现的位置
    vector<int>profile(10,0);
    for (int i = 1; i < 10; i++) {
        profile[i] += counter[i-1]+profile[i-1];
    }
    // 正序遍历，根据桶内统计结果，将各元素填入 res
    vector<int> res(n, 0);
    for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp);
        int j = profile[d]; // 获取 d 在数组中的索引 j
        res[j] = nums[i];       // 将当前元素填入索引 j
        profile[d]++;           // 将 d 的数量减 1
    }
    // 使用结果覆盖原数组 nums
    for (int i = 0; i < n; i++)
        nums[i] = res[i];
}

我这样正序排列好像也可以，有点不明白为什么不能用正序遍历

[krahets]

Hi，只是在文中的前缀和数组下，需要正序遍历。可以看看这里

[ChinaYong]

该书的作者，你们好！
文中在描述算法特性的时候提到了，基数排序稳定性与计数排序相同，但我认为，如果计数排序是不稳定的，基数排序应该无法求得正解才对。比如，对于323，321这两个数字排序：第一轮由于1<3，所以是321、323（升序），第二轮2=2，如果是非稳定排序，就可能让排序由此被打乱成323、321。还是说是我的对算法的理解哪里有问题吗？

[krahets]

Hi～是的，这和文中“基数排序稳定性与计数排序相同”想表达的含义是一致的。即基数排序“继承”了计数排序的稳定性。如果实现的计数排序是不稳定的，基数排序既不稳定，也可能无法得到正确的结果。

[lxy697]

但是我觉得如果使用的计数排序是不稳定的，那么基数排序应该是错的而不是不稳定的。所以说基数排序的过程中必须使用稳定的计数排序，从而也一定是稳定的，不知道我理解的对不对

[Claw-some]

我也觉得，基数排序应该是稳定的才对😝

[wangzijian121]

    // 统计 0~9 各数字的出现次数
    for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp); // 获取 nums[i] 第 k 位，记为 d
        counter[d]++;                // 统计数字 d 的出现次数
    }
    // 求前缀和，将“出现个数”转换为“数组索引”
    for (int i = 1; i < 10; i++) {
        counter[i] += counter[i - 1];
    }

核心在【个数】转【数组索引】这样理解可能更好：
当 i 等于 0 时，将 count[0] 个值为 0 的元素放入 nums 的索引范围 [index[0], index[1])。
当 i 等于 1 时，将 count[1] 个值为 1 的元素放入 nums 的索引范围 [index[1], index[2])。
当 i 等于 2 时，将 count[2] 个值为 2 的元素放入 nums 的索引范围 [index[2], index[3])。

[hello-ikun]

def radix_sort(nums):
    n=len(str(max(nums)))
    for i in range(n):
        bucket_list=[[] for _ in range(10)]
        for j in nums:
            idx=j//pow(10,i)%10
            bucket_list[idx].append(j)
        nums=[j for i in bucket_list for j in i]
    return nums

可以这样来实现 更舒服一点

[hello-ikun]

汇总一一下下

# 借助桶排序
def radix_sort(nums):
    # 计算数字的最大位数
    n = len(str(max(nums)))
    # 对每一位进行排序
    for i in range(n):
        # 创建桶列表
        bucket_list = [[] for _ in range(10)]
        # 将数字放入对应的桶中
        for j in nums:
            idx = j // pow(10, i) % 10
            bucket_list[idx].append(j)
        # 合并桶中的数字
        nums = [j for bucket in bucket_list for j in bucket]
    return nums

# 借用计数排序即可
def radix_sort1(nums):
    # 计算数字的最大位数
    n = len(str(max(nums)))
    # 对每一位进行计数排序
    for i in range(n):
        count_sort(nums, i)
    return nums

# 计数排序
def count_sort(nums, exp):
    cnt = [0] * 10
    # 统计数字出现的次数
    for num in nums:
        idx = num // pow(10, exp) % 10
        cnt[idx] += 1

    # 计算前缀和
    for i in range(1, 10):
        cnt[i] += cnt[i - 1]

    n = len(nums)
    ans = [0] * n
    # 逆序遍历排序数组，保证稳定性
    for i in range(n - 1, -1, -1):
        idx = nums[i] // pow(10, exp) % 10
        ans[cnt[idx] - 1] = nums[i]
        cnt[idx] -= 1

    # 将排序后的数组复制回原始数组
    for i in range(n):
        nums[i] = ans[i]

[Verlog123]

”假设我们需要对 n=10^6个学号进行排序，而学号是一个 8位数字”，对这么多的学号进行排序，博主没考虑到“res = [0] * n”这行代码的数组res会变得异常的大么？

[krahets]

在普通基数排序下，输入数组 nums 和 res 的空间复杂度都是 $O(n)$ ，因此不能说 res “异常” 的大，这在大数据量是下难以避免的

[WalkerInAI]

起码要给数据一个储存的东西吧

[YannisLing]

不懂就问，C代码中/* 基数排序 */里的第一个for循环为啥要使用size_t类型捏？它和Int型有啥区别吗？

[echo1937]

"相较于计数排序，基数排序适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。"

似乎非固定位数不影响基数排序的正确性啊，比如数组 {546151, 35663510, 42865989, 34862445, 81883077, 88906420, 72429244, 30524779, 82060337, 2996} 位数不相同，但是依然可以正确排序。

[krahets]

那是因为我们将这个数据“表示为固定位数的格式”，例如 2996 被表示为 00002996

[Tianyu-Huang-letsgo]

我的理解：基数排序事实上就是计数排序实际应用的一种情况，将多位数作为一个对象，从低位往高遍历的数字依次作为排序值，牵动多位数（对象）进行排序

[YMMdrq]

void Radixsorting(std::vector<int> &v, int K)
{
    // 十进制,最大元素为9
    int m = 9;

    // temp1创建并建立数量映射
    std::vector<int> temp1(m + 1, 0);
    for (const auto &it : v)
    {
        // 按要排的第几位映射为索引
        temp1[(it / K) % 10]++;
    }

    // 变成前缀和
    for (int i = 0; i <= m; ++i)
    {
        temp1[i + 1] += temp1[i];
    }

    int l = v.size();
    std::vector<int> temp2(l);
    for (int i = l - 1; i >= 0; i--) // 由于前缀和为保证稳定排序需倒序填充
    {
        int n = (v[i] / K) % 10;    // 只看要排那一位
        temp2[temp1[n] - 1] = v[i]; // 根据前缀和索引到对应位置
        --temp1[n];                 // 前缀和更新为向前一个位置的索引
    }
    // temp2覆盖v
    v = temp2;
}

请问一下，这段哪有问题啊？
我只调用一次，
vector v{1,2,31,4,56};
Radixsorting(v,1);
运行结果没问题
vector v{1,2,31,4,56};
Radixsorting(v,10);
运行结果也没问题
但这样
vector v{1,2,31,4,56};
Radixsorting(v,1);
Radixsorting(v,10);
就会
ldl@ldl-virtual-machine:~/AlgoPrimer/bin$ ./main
munmap_chunk(): invalid pointer
已放弃 (核心已转储)