chapter_sorting/radix_sort/

[giscus[bot]]

chapter_sorting/radix_sort/

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

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

[GyBernstein]

个数转索引 巧妙的方法啊

[krahets]

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

[muquew]

使用链表的图的实现可能更容易理解

[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的相对位置保持不变才行，因为第二轮的排序完全不会去考虑个位
所以如果是不稳定的正序相当于只是在排十位，整个就乱套了

[sean990802]

实际上这与你存储的桶内各数的位置有关，文中存储的是对应数字最后一次出现的位置，所以自然要使用倒叙遍历才能保证稳定性。但是如果存储的是正序的（上一个数的倒叙位置+1）那就可以使用正序来保证稳定性了。

[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]

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

[syutengu]

同感，不就是把int理解为obj（或arr）后，对其按照 k 个属性（或arr[k]）计数排序 k 遍嘛。
e.g., int 31415926 -> arr [3,1,4,1,5,9,2,6] -> obj {0:3,1:1,2:4,3:1,4:5,5:9,6:2,7:6}

[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
已放弃 (核心已转储)

[backtraxe]

1. temp1[i + 1] += temp1[i]; 越界。
2. temp2[temp1[n] - 1] = v[i]; 索引可能为负。

[Than-Sing]

NOTE：1.对数位做倒序排序保证算法有效性；2.构造res[]数组是从上一轮排好的数组倒序进行的，保证排序算法的稳定性

[Ne0911]

/* 计数排序（根据 nums 第 k 位排序） */
void countingSortDigit(int nums[], int size, int exp) {
// 十进制的位范围为 09 ，因此需要长度为 10 的桶数组
int *counter = (int *)malloc((sizeof(int) * 10));
// 统计 09 各数字的出现次数
for (int i = 0; i < size; i++) {
// 获取 nums[i] 第 k 位，记为 d
int d = digit(nums[i], exp);
// 统计数字 d 的出现次数
counter[d]++;
}
// 求前缀和，将“出现个数”转换为“数组索引”
for (int i = 1; i < 10; i++) {
counter[i] += counter[i - 1];
}
// 倒序遍历，根据桶内统计结果，将各元素填入 res
int *res = (int *)malloc(sizeof(int) * size);
for (int i = size - 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
}
// 使用结果覆盖原数组 nums
for (int i = 0; i < size; i++) {
nums[i] = res[i];
}
}

这步不需要free(res)吗 记得malloc的不用都要free的吧

[sean990802]

可不可以优先排序高位，然后将高位一样的元素分到同一个桶里继续排序里面的低位，这样的话在某个高位排序完成且不相等的情况下那个桶就完成排序了，而不需要继续排序低位了。从低位排序则必须要排完所有位才能保证结果。

[sean990802]

写出来一个类，是从高位向低位排序的，但是写的比从低到高麻烦了一些，多了一些步骤。使用的话直接用redixSort(nums)传入数组，或者redixSort(nums， exp, left, right)传入参数。

package com.itheima;

public class redix_sort {
    // 传入以获取确定的某一位
    private int digit(int num, int exp){
        return (num / exp) % 10;
    }

    // 将某区间内的元素排序,返回区间桶的位置
    private int[] countingSortDigit(int[] nums, int exp, int left, int right){
        int[] counter = new int[10];
        int n = nums.length;
        // 计数
        for (int i = left; i <= right; i++) {
            int tmp = digit(nums[i], exp);
            counter[tmp]++;
        }
        // 判断counter的所有位是否只有1或0，是则代表无需在进行下一步划分
        boolean flag = true;
        for(int count : counter){
            if(count > 1){
                flag = false;
                break;
            }
        }

        // 计算位置
        for(int i = 0; i < counter.length-1; i++){
            counter[i+1] += counter[i];
        }
        // 对counter做一次复制,并重新定位
        int[] counter_copy = new int[10];
        for(int i = 0; i < 10; i++){
            counter_copy[i] = counter[i] + left;
        }
        // 倒叙插入
        int[] nums_copy = new int[right-left+1];
        for(int i = right; i >= left; i--){
            int tmp = digit(nums[i], exp);
            int index = counter[tmp]-1;
            nums_copy[index] = nums[i];
            counter[tmp]--;
        }
        // 替换
        for(int i = left, j=0; i <= right && j <= right-left; i++, j++){
            nums[i] = nums_copy[j];
        }
        // 如果该桶内排序确定，则返回null以标志无需再次划分
        if(flag){
            return null;
        }
        return counter_copy;
    }

    // 从高位到低位排序
    public void redixSort(int[] nums, int exp, int left, int right){

        // 循环排序各区间
        if(left < 0 || left+1 >= right || exp <= 1){
            return;
        }
        int[] counter = countingSortDigit(nums, exp, left, right);
        if(counter == null){
            return;
        }
        for(int count : counter){
            right = count - 1;
            redixSort(nums, exp/10, left, right);
            left = right+1;
        }
    }
    // 再次封装
    public void redixSort(int[] nums){
        // 获取最大数
        int m = nums[0];
        for(int num : nums){
            if(num > m){
                m = num;
            }
        }
        // 获取最大数的位数
        int length = String.valueOf(m).length();

        int exp = (int) Math.pow(10, length-1);
        redixSort(nums, exp, 0, nums.length-1);
    }
}

[sean990802]

感觉有很多可以优化的地方，欢迎大家指出来

[sean990802]

退出循环条件应该是exp<=0

[tstanon]

完整的计数排序C代码

void get_kth_digit(int x, int k, int *digit){ *digit = (x / (int)pow(10, k)) % 10; } // 获取数字x的第k位数字
void counting_sort_digit(int *arr, int size, int k){
    int *counter = (int *) calloc(10, sizeof(int)), *res = (int *)malloc(sizeof(int) * size); // 计数数组（最终存储前缀和）；结果数组
    for (int i = 0; i < size; ++i) { int digit; get_kth_digit(arr[i], k, &digit); counter[digit]++; } // 累计计数
    for (int i = 1; i < 10; ++i) { counter[i] += counter[i - 1]; } // 计算前缀和
    for (int i = size - 1; i >= 0 ; --i) { int digit; get_kth_digit(arr[i], k, &digit); res[counter[digit] - 1] = arr[i]; counter[digit]--; } // 从后往前遍历，根据前缀和确定元素在结果数组中的位置
    memcpy(arr, res, sizeof(int) * size); free(counter); free(res);
}
void radix_sort(int *arr, int size){
    if (size <= 0)  return; int max_val = arr[0], max_digit = 0;
    for (int i = 1; i < size; i++) { if (arr[i] > max_val) max_val = arr[i]; } // 找到最大值，用于确定计数数组大小[0, max_val]
    while (max_val > 0) { max_val /= 10; max_digit++; } // 计算最大值的位数
    for (int i = 0; i < max_digit; i++) { counting_sort_digit(arr, size, i); } // 从低位到高位，依次对每一位进行计数排序
}

[tstanon]

无需传入exp

[checkma-xh]

import random


def sort(nums):
    max_bit = max(nums)
    base = 1

    while max_bit:
        buckets = [[] for _ in range(10)]
        new_nums = []
        
        for num in nums:
            buckets[num // base % 10].append(num)
        for bucket in buckets:
            new_nums.extend(bucket)

        nums = new_nums
        base *= 10
        max_bit -= 1
    
    return nums


nums = [random.randrange(0, 10000) for _ in range(10)]
print(nums)
print(sort(nums))

[123, 5968, 9815, 3676, 8577, 9975, 269, 6414, 3962, 9470]
[123, 269, 3676, 3962, 5968, 6414, 8577, 9470, 9815, 9975]

[cncws]

max_bit = max(nums).bit_length()   # 这才是变量本意，不然循环从 max(sums)降为0会浪费很多时间
while max_bit:
    ...
    max_bit -= 1

[LQF376]

K神，基数排序的核心思想是从低位对高位每一个位进行排序，从而得到一个有序的数列，我想知道如果每一位排序的算法不用计数排序，而用其他非稳定的排序方法，这样基数排序还有效吗？

[Xuuyuan]

用其它排序方法复杂度不会更低吧

[eyerthin]

无效，基数排序的前提就需要稳定的排序方法，最好的就是计数排序，如果使用其他稳定排序方法虽然也可以，但是复杂度就更高了，比如结合插入排序变成 O(d*n^2) 了，其中 d 是位数。所以最好还是配合计数排序，基数排序的每一位正好符合数据多，但是范围小这一情况。

[Ares-bit]

C版本的countingSortDigit第一句应该用calloc