chapter_sorting/counting_sort/

[giscus[bot]]

chapter_sorting/counting_sort/

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

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

[lethexixin]

在完整实现中，可排序对象，但代码里却传入的是 []int，一开始理解没转过来。

[lethexixin]

func TestCountingSort3(t *testing.T) {
	num := []Number{
		{"name1", 1}, {"name2", 0}, {"name3", 1},
		{"name4", 2}, {"name5", 0}, {"name6", 4},
		{"name7", 0}, {"name8", 2}, {"name9", 2},
		{"name10", 4}}
	CountingSort3(num)
	fmt.Println(num)
	//[{name2 0} {name5 0} {name7 0} {name1 1} {name3 1} {name4 2} {name8 2} {name9 2} {name6 4} {name10 4}]
}

type Number struct {
	Name string
	Num  int
}

// CountingSort3 计数排序
func CountingSort3(nums []Number) {
	// 1. 统计数组 nums 对象中的最大Num元素 m
	m := 0
	for _, num := range nums {
		if num.Num >= m {
			m = num.Num
		}
	}

	// 2. 统计各Num的出现次数
	// counter[num.Num] 代表 Num 的出现次数
	counter := make([]int, m+1)
	for _, num := range nums {
		counter[num.Num]++
	}

	// 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”
	// 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
	for i := 0; i < m; i++ {
		counter[i+1] += counter[i]
	}

	// 4. 倒序遍历 nums，将各元素填入结果数组 res
	// 初始化数组 res 用于记录结果
	n := len(nums)
	res := make([]Number, n)
	for i := n - 1; i >= 0; i-- {
		num := nums[i]
		// 将 num 放置到对应索引处
		res[counter[num.Num]-1] = num
		// 令前缀和自减 1 ，得到下次放置 num 的索引
		counter[num.Num]--
	}

	// 使用结果数组 res 覆盖原数组 nums
	copy(nums, res)
}

大佬，是否可以考虑下，传入对象的代码也一块展示出来，这样更好理解

[krahets]

赞！这个得考虑一下，是否应该再加一个排序对象某一属性的代码示例

[cylovecode]

之前看过yukiyama的这篇帖子https://leetcode.cn/circle/discuss/eBo9UB/，您这个再稍微改进一下既可以用于负整数又可以节约空间，当`nums`元素个数较多，并且有很多相等元素使得元素分布 集中在较小范围 时，$m+1$ 大小的 $counter$ 中大部分空间是多余的。改进方法很简单，即创建大小为 $max - min + 1$ 的 $counter$ ，$max$ 和 $min$ 分别是 $arr$ 中最大和最小元素，其他的和这里就一样了，
按照您的代码风格改了一下c++的，

> void countingSort(vector<int> &nums) {
>     // 1. 统计数组最大元素Max和最小元素Min
>     int n = nums.size(), Min = nums[0], Max = nums[0];
>     for(int num : nums) {  // 确定 Min 和 Max
>         Min = min(Min,num);
>         Max = max(Max,num);        
>     }
>     // 2. 统计各数字的出现次数
>     // counter[num - Min] 代表 num 的出现次数
>     vector<int> counter(Max - Min + 1,0);  //nums最多有Max-Min+1种数字,全部初始化为0；
>     for(int num: nums) {    
>         counter[num - Min] ++;   // nums[i] 的值出现一次，则 countArr[nums[i]-min] 加 1
>     }
>     // 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”
>     for(int i = 1; i < counter.size(); ++i) {  
>         counter[i] += counter[i-1];
>     }
>     // 4. 倒序遍历 nums ，将各元素填入结果数组 res
>     // 初始化数组 res 用于记录结果
>     vector<int> res(n);    
>     for(int i = n - 1; i >= 0; -- i) {   
>         int countIdx = nums[i] - Min;   // nums[i] 元素对应 counter 中的下标
>         int sortIdx = counter[countIdx] - 1;  // 在排序后数组中的下标
>         res[sortIdx] = nums[i];   // 在排序后数组中填入值
>         counter[countIdx]--;   // 令前缀和自减 1 ，方便得到下次放置 num 的索引
>     }
>     // 使用结果数组 res 覆盖原数组 nums
>     nums = res;
> }
> ```
上力扣跑了一下超过90%的提交，感觉蛮不错的，就是改了之后逆序填充元素的过程有点绕

[krahets]

@cylovecode 是的，文中也有提到：“对于包含负数的整数数组，可以先给所有数字加上一个常数，将全部数字转化为正数，排序完成后再转换回去即可”

[ltylty]

有点像bitmap

[yzd11]

在C语言的完整实现中进行第一次分配的代码是
int *counter = malloc(sizeof(int) * size);
难道不是根据最大值进行分配吗？我认为应该是这样的
int *counter = malloc(sizeof(int) * (m + 1));

[yzd11]

同时我发现在使用时如果有负数或者过大的数也会出现问题，以及counter数组没有赋初值为0；
使用malloc后也没有free;
这是我的代码，不知道可不可以

//计数排序
void countingSort(int num[], int size) {
    // 统计最大值和最小值
    int max = num[0];
    int min = num[0];
    for (int i = 1; i < size; i++) {
        if (num[i] > max) {
            max = num[i];
        }
        if (num[i] < min) {
            min = num[i];
        }
    }
    // 统计出现次数
    int range = max - min + 1;
    int *counter = malloc(sizeof(int) * range);
    memset(counter, 0, sizeof(int) * range);
    for (int i = 0; i < size; i++) {
        counter[num[i] - min]++;
    }
    // 计算前缀和
    for (int i = 1; i < range; i++) {
        counter[i] += counter[i - 1];
    }
    // 将结果付给res数组
    int *res = malloc(sizeof(int) * size);
    for (int i = size - 1; i >= 0; i--) {
        int nums = num[i] - min;
        res[counter[nums] - 1] = num[i];
        counter[nums]--;
    }
    memcpy(num, res, sizeof(int) * size);
    free(counter);
    free(res);
}

[krahets]

可以呀。本文代码仅适用于正整数数组，且数字大小不能超过元素类型的取值范围

[amlei]

是的，当前C语言的 countingSortNaive() 和 countingSort()函数中的 counter malloc后并未初始化，这就导致在后面统计个数实现 ++ 操作无法实现

// 2. 统计个数字出现的个数
int *counter = malloc(sizeof(int) * m);

Run out:

Process finished with exit code -1073741819 (0xC0000005)

我的策略是将其修改为：

// 将分配的内存初始化为零
int *counter = calloc(m, sizeof(int) * m);

// 4. 释放 counter 内存
free(counter);

[Gonglja]

是的，你的策略是对的，后面我会进行修改

[Arvin225]

这里的完整实现我没怎么明白具体 “好” 在哪，感觉就是最后可以保持同一个成员属性值的多个对象的相对位置不会发生变化（即原来它们的前后位置是怎样的，排序后它们的顺序依然是那样），其他就没看出什么 “优势” 了，简单实现也是能对对象排序的吧？只是无法对同一属性值的对象做区分？

[krahets]

完整实现具有“稳定性”，这是排序算法的一个重要的优良特性。简单实现只能排序整数数组，最终无法还原到对象上。

[Arvin225]

好的，谢谢回复😊

[WhiteRhinos]

为什么简单计数不稳定呢,获得了价格排序再和商品对照一下不就可以获得对应商品排序了,也不会改变相对位置,是我理解错了吗

        Commodity[] commodities = new Commodity[5];
        commodities[0] = new Commodity("商品1",2);
        commodities[1] = new Commodity("商品2",3);
        commodities[2] = new Commodity("商品3",1);
        commodities[3] = new Commodity("商品4",2);
        commodities[4] = new Commodity("商品5",2);
        //商品对应价格
        int[] price = {2,3,1,2,2};
        String[] names = new String[commodities.length];
        // 价格经过简单计数排序后为:1,2,2,2,3
        countingSort(price);
        for (Commodity commodity : commodities)
        {
            int commodityPrice = commodity.price;
            for (int j = 0; j < price.length; j++)
            {
                if (commodityPrice == price[j])
                {
                    names[j] = commodity.name;
                    price[j] = -100;
                    break;
                }
            }
        }
        // [商品3, 商品1, 商品4, 商品5, 商品2]
        System.out.println(Arrays.toString(names));

[krahets]

可以的，你展示的代码添加了一个 $O(mn)$ 的填值过程，其中 $m$ 为商品种类数；如果用哈希表记录前缀和来填值，应该可以在 $O(n)$ 内完成。

文中想表达的是，简单实现只关注数字的个数，相等数字之间相互的顺序，因此无法直接得到稳定的排序结果。

[WhiteRhinos]

ok,谢谢

[WhiteRhinos]

这里的稳定基数排序只展示了思想,像更清楚的体会稳定性看基数排序里面的使用

[krahets]

是的，简单实现已经体现了计数排序的核心思想；完整实现利用前缀和实现了稳定排序，稍微复杂些

[DXShelley]

细心的同学可能发现，如果输入数据是对象，上述步骤 3. 就失效了。假设输入数据是商品对象，我们想要按照商品价格（类的成员变量）对商品进行排序，而上述算法只能给出价格的排序结果.
请问这句话什么意思？
我能明白先分组计算和前缀和实现的两种方法原理和实现。但是不明白和提出的问题有什么关系？

[Donghuajie]

但是两个函数传入参数不都是一个价格列表吗？为什么第二种就实现了基于价格的对象排序呢？不是很理解

[krahets]

@Donghuajie 文中没用对象作为输入数据，你可以创建一个对象数组来试一下，例如拥有姓名和年龄这两个属性的 People 类，然后根据 age 排序它：

class People:
    def __init__(self, name: str, age: int):
        self.name: str = name # 姓名
        self.age: int = age # 年龄

[Donghuajie]

def counting_sort(people_list: list[People]):
# 1. 统计数组最大年龄
max_age = max(people.age for people in people_list)

# 2. 统计各年龄的出现次数
counter = [0] * (max_age + 1)
for person in people_list:
    counter[person.age] += 1

# 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”
for i in range(1, max_age + 1):
    counter[i] += counter[i - 1]

# 初始化数组 result 用于记录结果
n = len(people_list)
result = [None] * n

# 4. 倒序遍历 nums ，将各元素填入结果数组 result
for i in range(n - 1, -1, -1):
    person = people_list[i]
    result[counter[person.age] - 1] = person
    counter[person.age] -= 1

# 使用结果数组 result 覆盖原数组
for i in range(n):
    people_list[i] = result[i]

那是不是要这样修改一下源码？

[krahets]

对的

[Donghuajie]

好的，谢谢！

[FitzFitzFitz]

还是不太能理解“实际上，正序遍历 nums 也可以得到正确的排序结果，但结果是非稳定的。”
为什么是非稳定的呢

[zlikForward]

我是这样认为的，如果正序遍历的话几个相等的数位于原数组中最左边的，会被放在结果数组一连串相等的数的最右边，相等的数的相对位置发生了变化，所以是不稳定的。

[krahets]

因为初始状态下的前缀和记录的是元素在数组中的”最后一个索引“，填充 res 的过程是“从右向左”的，因此我们倒序遍历 nums 才能和填充顺序保持一致，从而保持稳定性。

换句话说，如果我们能将前缀和的初始状态指向"第一个索引"，那么就应该正序遍历 nums 。

[krahets]

如果想要达到正序遍历 + 稳定排序，那么可以这样写：

def counting_sort(nums: list[int]):
    """计数排序"""
    # 完整实现，可排序对象，并且是稳定排序
    # 1. 统计数组最大元素 m
    m = max(nums)
    # 2. 统计各数字的出现次数
    # counter[num] 代表 num 的出现次数
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”
    # 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
    for i in range(m):
        counter[i + 1] += counter[i]
    # ! 在 counter 首部添加 0 ，此时 counter[num] 的含义变为： num 在 res 中第一次出现的索引
    counter.insert(0, 0)
    # 4. 正序遍历 nums ，将各元素填入结果数组 res
    # 初始化数组 res 用于记录结果
    n = len(nums)
    res = [0] * n
    # ! 请注意，这时我们就可以在正序遍历下保持稳定性
    for i in range(n):
        num = nums[i]
        res[counter[num]] = num  # 将 num 放置到对应索引处
        counter[num] += 1  # 令前缀和自增 1 ，得到下次放置 num 的索引
    # 使用结果数组 res 覆盖原数组 nums
    for i in range(n):
        nums[i] = res[i]

[wangzichen-bixin]

一直在找这个疑问点，终于找到了作者的回复，和我想的一样！

[shixiansen1999]

（java）完整实现的这一步是为了计算相同值的下一次放置的索引吗：counter[num]--; // 令前缀和自减 1 ，得到下次放置 num 的索引

[buynonsense]

完整实现和简单实现的区别是什么？有人概括一下吗？

[yukuau780]

完整实现就是简单实现后根据在原始数据里出现的先后顺序确定实现后的顺序

[wangzichen-bixin]

对比两段代码你会发现，简单实现最后输出时遍历的是counter数组，索引对应的是nums数组的值。完整实现最后输出时遍历的是nums数组，到counter中去寻找排序后的位置。
简单实现用索引映射了nums数组的值，数组索引只能是int类型，所以不能对对象进行排序，硬排序的结果只能是针对对象中的int类型的成员变量。而且是不稳定的。不稳定体现在原nums是 1，1‘，1’‘，2，counter是0，3，1，排序后无法确定1、1’和1‘’的位置关系。
完整实现采用了前缀和数组记录每一个元素应该在的位置，倒序遍历nums之后元素会严格按照相对放置填入，保证了稳定性，也兼容了对象的排序，更具有普适性

[sakurakugu]

res[counter[num] - 1] = num; // 将 num 放置到对应索引处
 counter[num]--;                    // 令前缀和自减 1 ，得到下次放置 num 的索引

这里是不是可以改成 res[--counter[num]] = num; 这一句即可呀

[ShiinaMahiru-repo]

可以吧

[ShiinaMahiru-repo]

话说C语言那个counter数组 calloc(m, sizeof(int)) 是不是越界了 之后不是要更新counter[nums[i]] (包含m) 的值吗 这个是越界吗

[Gonglja]

是的，此处会存在越界行为，应为 calloc(m + 1, sizeof(int))

已更正：Gonglja@b8c66c9

[qw124341789]

第一段代码改了，第二段还是calloc（m,sizeof(int)）

[Verlog123]

计数排序有个关于“计数器数组长度”的问题，比如对100万个199~999的数字进行排序，计数器数组counter是一个长度为999的数组，前面198个长度并没有使用，是浪费掉的，因此为了节省内存，计数器数组应该改成counter=max(nums)-min(nums)+1,这样更节省内存

[Lijingwoquan]

有道理 赞了

[lieren1922]

但是这样的话每一个都要减去min

[qw124341789]

哈希函数跟计数排序有关联吗

[krahets]

可以把计数排序中的计数器看作是一个 key 为元素值、val 为元素数量的哈希表

[chaojiwudidashuaige492]

public static void countingSortPro(int[] nums){
        //假定输入一个商品数组 ItemArray
        //由此得到其成员变量价格 的数组 PriceArray
        //对PriceArray中的元素进行计数排序得到prefix-->元素插入位置
        //再遍历ItemArray得到 满足价格排序的 商品数组 且是稳定排序
        int max=nums[0];
        for(int i=1;i< nums.length;i++){
            max=nums[i]>max?nums[i] : max;
        }
        int[] counter = new int[max + 1];
        //得到counter数组
        for(int i=0;i< nums.length;i++){
            counter[nums[i]]++;
        }
        //得到prefix数组
        for(int i=0;i< counter.length;i++){
            counter[i+1]+=counter[i];
        }
        //创建存储结果的数组res
        //Item[] res;
        int[] res = new int[nums.length];
        //关键步骤
        for(int i= nums.length-1;i>=0;i--){
            int num=nums[i];
            //res[counter[num]-1]=ItemArray[i]
            res[counter[num]-1]=nums[i];//counter[num]得到该数据对应的prefix
            counter[num]-=1;
        }
        //使用结果数组res覆盖原数组nums
        for(int i=0;i< nums.length;i++){
            nums[i]=res[i];
        }
    }

希望帮助大家辅助理解一下完整实现的意义。priceArray中的价格元素和itemArray中的商品对象相对应，后面记录结果的时候直接从itemArray中提取元素就可以了。

[chaojiwudidashuaige492]

更正：得到prefix那里，循环终止条件应该是i<counter.length-1

[cgbSmith]

public class User{
    int cost;
    int age;
}
void countingSortNaive(User[] nums) {
    int m = 0;
    for(User user : nums){
        if(m>user.age) m = user.ages;
    }
    int[]ans = new int[m+1];
    for(User user:nums){
        int num = user.age;
        ans[num]++;//ans[3] = 4,表示年龄为3的对象有4个
    }
    //计算前缀合
    int[]pre = new int[m+1]
    for(int i=0;i<m;i++){
        pre[i+1] += pre[i]; //pre[3] = 10,表示年龄为3的最后一个对象的索引为10-1=9
    }

    User[]res = new User[n];
    for(i=nums.length-1;i>=0;i--){//从数组最后一位开始遍历可以保证元素的稳定性，即前后位置不变
        //如果从i=0开始的话，相同元素的相互位置可能会改变
        User user = nums[i];
        index = user.age;//这个对象的年龄就是这个对象在ans数组的索引，也是在pre数组的索引
        res[pre[index]-1] = user;
        pre[index]--;
    }
    //将res拷贝回去nums；
    for(int i=0;i<nums.length;i++){
        nums[i] = res[i];
    }
    
}
//之前发的版本User[]res = new User[m+1];不对，应该大小为n的对象数组

[cgbSmith]

排序内容为对象的实现

[jiangpeng999999]

感谢 K 神，当初看《算法 4th》计数排序虽然只占了很小几页，但一上来就是完整实现，反复看了很多遍都没能理解。。。现在看这篇弄清了，真可谓666也（原作者水平高内容立点也高，虽然也写得很清晰明了但看起来还是比这有难度多了）

[liweijian199011]

算法特性中，为什么没有自适应性了呢？

[krahets]

漏写了，计数排序是非自适应排序

[Tianyu-Huang-letsgo]

看这部教程有一种当初看完交大郑益慧老师《模拟电子技术》课程的感觉，真的惊叹作者水平之高，通篇竟无一句废话

[wangzichen-bixin]

我看大家提出疑问最多的是：为何简单实现不能排序对象？
我的理解是：对比两段代码你会发现，简单实现最后输出时遍历的是counter数组，索引对应的是nums数组的值。
// 3. 遍历 counter ，将各元素填入原数组 nums
int i = 0;
for (int num = 0; num < m + 1; num++) {
for (int j = 0; j < counter[num]; j++, i++) {
nums[i] = num;
}
}

简单实现用索引映射了nums数组的值，数组索引只能是int类型，所以不能对对象进行排序，硬排序的结果只能是针对对象中的int类型的成员变量。而且是不稳定的。不稳定体现在原nums如果是
{id:1,age:1}，{id:3,age:1}，{id:3,age:1}，{id:4,age:2}，根据age排序的话，counter是0，3，1（索引为1的位置为3，代表有3个对象的age都是1），那么遍历counter的时候没法将3个age=1对应回原来的对象。

完整实现采用了前缀和数组记录每一个元素应该在的位置，倒序遍历nums之后元素会严格按照相对放置填入，保证了稳定性，也兼容了对象的排序，更具有普适性

[One-one-Zero]

创建一个新的数组，新的数组的值即为当前索引在原数组中出现的次数，提取出新数组中的非零元素的索引序列，即为原数组的排序结果。