雅乐网

计算机技术、学习成长

计算机 » 算法 » 计数排序和基数排序

计数排序和基数排序

基于比较的排序的时间复杂度下界是O(nlogn),但是当要排序的元素具有一些特殊性质的时候,可以使用非比较的方法突破这种限制。

计数排序

当待排序的元素a[]都是位于区间[0,k]中的整数时,可以使用计数排序。计数排序顾名思义就是统计元素的个数,这需要额外O(k)的空间,我们使用数组c来记录。

首先通过遍历待排序的数组,统计每个元素个数。这时c[i]记录了数组a中i元素的个数。

然后遍历一次统计结果数组,通过c[i] += c[i-1]的操作使c[i]记录a中小于等于i的元素的个数。这样可以直接得到元素在排序好的数组中的下标,例如:数组a中小于等于7的元素有23个,那么排序号的数组中7的下标就是23。

当a中有重复元素的时候,区间  (  c[i] ,c[i+1]  ]就确定了元素i+1的位置。为了保持排序的稳定性,在最终遍历a确定位置的时候要从n开始递减,然后c[i]递减,这样可以保证后面的元素排序好后还是位于后面。

计数排序的时间复杂度为O(n),但排序不是原址的,空间复杂度为O(max(k, n))。

基数排序

基数排序通过分别按某一位进行排序,先从最低位开始排序,再从次低位,最后到高位。排序时,元素的权值是元素的某一位,而且要使用稳定的排序算法来进行排序。

231957299298

10进制数字的某一位范围是0-9 ,这非常适合使用计数排序。

基数排序的时间复杂度也为O(n)。

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/counting_sort_and_radix_sort.html

上一篇:

下一篇:

我要评论

验证码*: 6 + 7 =