首页 / 算法 / 排序算法 - 计数排序

排序算法 - 计数排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法 - 计数排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1160字，纯文字阅读大概需要2分钟。

内容图文

基本思想

计数排序是一种线性排序算法，它利用了一个数组，因为数组下标的增长是线性的，所以它就把自己的元素转换成新开辟数组的下标。可是下标都是非负数啊？数组当中的值有正有负啊。做一个简单的转化就行了：找到数组中最小元素，用元素值减去，这样一来，所有元素对应的下标就求出来了。（实际上感觉像是个映射函数？）下图中保存的是待排序数组：[-1,-5,-6,-2,1,2,8,2,1,8]

技术分享图片

 然后跟哈希排序的思路一样：这里。直接开辟一个对应的哈希数组，然后统计每个元素出现的次数。橙色标注出来的表示待排序数组中没有的元素（转换后的元素），自然就没有出现次数。这样可以看出来如果数组中元素差距很大，其实还是很浪费空间的，因为它新开辟数组的大小是待排序数组arr中max-min+1（8+6+1=15）。

 技术分享图片

最后再将count中的元素放回到arr中，就完成排序了。

算法代码

             1
            //
            计数排序
             2
            void CountSort(int *a, int size)
 3{
 4int max = a[0];
 5int min = a[0];
 6for (int i = 0; i < size; ++i)
 7    {
 8if (a[i] > max)
 9             max = a[i];
10if (a[i] < min)
11             min = a[i];
12    }
13int range = max - min + 1; //要开辟的数组范围14int *count = newint[range];
15     memset(count, 0, sizeof(int) * range); //初始化为0
16//统计每个数出现的次数17for (int i = 0; i < size; ++i)           //从原数组中取数，原数组个数为size18    {
19         count[a[i] - min]++;
20    }
21//写回到原数组22int index = 0;
23for (int i = 0; i < range; ++i) //从开辟的数组中读取，开辟的数组大小为range24    {
25while (count[i]--)
26        {
27             a[index++] = i + min;
28        }
29    }
30delete[] count;
31 }

 算法分析

计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为 O(n+k)，其中 k 是整数的范围。


[参考：https://blog.csdn.net/qq_34269988/article/details/90705977]

原文：https://www.cnblogs.com/WindSun/p/11361008.html

内容总结

以上是互联网集市为您收集整理的排序算法 - 计数排序全部内容，希望文章能够帮你解决排序算法 - 计数排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1268947.html

来源：【匿名】