计数排序

算法思路

对一组数据排序,如果我们能事先知道数组的范围比如我们的”待排序数组A[]”所有的数字都在0到10之间,那我们可以初始化一个数组B[]大小就是10,默认值都是0(这里为了方便叙述,所有数组下标从1开始),A数组从头到尾遍历,比如第一个数字是5,那B[5]=1,第二个数是3那B[3]=1,第三个数字是5那B[5] = B[5]+1=2,以此类推获得数组B,此时B数组里面index即原数组A里面的数字,value为A数组里面值为index的数字出现了几次,遍历所以遍历B数组打印每打印一次A[index]-1直到A[index]=0,这样我们就将所有的数字排序打出

举例

问题

① 数组大小可以为max-min+1减小空间复杂度比如[99,100]其实size为2就够了

② 如何让排序稳定,比如{6,5,5}我们给5编一个号码方便简述5a,5b,如果是上边的方式5a和5b其实是不稳定的,但是如果我们可以对原数组进行累加,原有多少个index数组,就变成有多少个数字比index小了,例如上边的数组,辅助数组为{2,1}->{2,3}然后将{6,5a,5b}从后到前遍历,5b放到index为2的地方{2,3}->{1,3},然后遍历到5a,5a放到index为1的地方,最后6放到index为3的地方得到{6,5a,5b}稳定排序

发表评论

邮箱地址不会被公开。 必填项已用*标注