当前位置：首页 > news >正文

【初阶数据结构与算法】八大排序之非比较排序(计数排序)，一次性讲清！

news 2026/6/10 16:30:24

（一）计数排序 Countsort

(升序为例)开辟一个额外数组count用于存储待排数组中的元素个数，譬如待排数组为{2,2,3,3,5,5,5,6,3,1}，这样1的个数有1个，存在count数组的第一位中，2有2个，存在count数组的第二位中，3有3个，存在count数组的第三位中，4有0个，存在count数组的第四位中，5有3个，存在count数组的第五位中，6有1个，存在count数组的第六位中。

即arr中的数据是啥，就将它的个数存储到count对应下标的位置处。

然后再根据count数组中存储的数据个数，依次将值拷贝回原数组中，1有1个，放回原数组中，占一个位置，2有2个，放回原数组中，挨着1占两个位置，3有3个，放回原数组中，挨着2占三个位置，4放回原数组中，挨着3占零个位置，5有3个，放回原数组中，挨着4占三个位置，6有一个，放回原数组中，挨着5占一个位置。

排好序后，原数组变成了{1,2,2,3,3,3,5,5,5,6}，排升序完成。

（1）代码实现

void Countsort(int* arr,int n) { int* tmp = (int*)calloc(n,sizeof(int)); if(tmp == NULL) { return; } int* count = tmp; //找最大最小值 int max = arr[0]; int min = arr[0]; for(int i=1;i<n;i++) { if(arr[i]>max) max = arr[i]; if(arr[i]<min) min = arr[i]; } int range = max-min+1; //定义数组的长度 for(int i = 0;i<n;i++) { //让count数组相应下标处存储处理后的arr数组的数据的出现次数 count[arr[i]-min]++; } //让count数组中存储的个数显化为arr数组的排序 int j = 0; for(int i = 0;i<range;i++) { while(count[i]--) arr[j++] = i+min; } }

（2）细节理解

数组里存的数据不同，count数组的大小就不同，所以我们采用动态申请内存的方式创建数组。

要确定count数组的大小，就要知道arr中的数据范围是多少，因为count数组存储的是arr数组中各个数据的出现次数，找到arr数组数据的取值范围，就知道count数组需要记录多少个数据的出现次数，这个"多少个数据"就是count数组的大小。

所以我们找到arr数组中的max和min，通过max-min+1的方式来确定count数组的大小range。

接下来，遍历arr数组，前面我们说arr中的数据是啥，就将它的个数存储到count对应下标的位置处，但这句话是有问题的，假设数组arr为{103,102,109,105}，我们能确定count数组的大小为109-102+1=8，那count数组的下标范围就为0-7，何来103/102/109/105呢？

所以，arr中数据要先处理一下，再看这个处理后的数据，处理后的数据是啥，就将它的个数存储到count数组对应下标的位置。

处理的方式就是将arr数组中的数据先减去min。

arr为{103,102,109,105}，处理后就变成了{1,0,7,3}，这样count数组0-7的下标就能满足存储要求了，由于0-7范围内，arr只出现了1,0,7,3，还有一些数没有出现，但是count数组中已经为这些没有出现的数据创建了空间，所以这些空间里填的值应当为0，这也对应了为什么我们用calloc动态申请内存，calloc申请空间，并将空间全部初始化为0。

等到将count数组中存储的数据个数显化成arr中的数据时，遍历count数组，内嵌循环赋值，注意，由于count数组存储的数据个数，是处理后的数据的个数，那么再赋值回arr数组时，就需要将count的下标加上min。