CountingSort(计数排序)原理及C++代码实现
2020-01-14 16:01:16来源:博客园 阅读 ()
CountingSort(计数排序)原理及C++代码实现
计数排序是需要假设输入数据的排序之一,它假设输入元素是0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,计数排序的时间复杂度为θ(n)。
因为不是通过比较来排序,所以它的时间复杂度可以达到θ(nlgn)以下。
计数排序是稳定的排序之一。
代码如下:(仅供参考)
//计数排序期望输入数据都是小区间内的整数 void CountingSort(int * const begin, int * const end) { vector<int> temp(10000); //假设输入值小于10000 vector<int> out(end - begin); for (int i = 0; i < end - begin; ++i) ++temp[*(begin + i)]; for (int i = 1; i < 10000; ++i) temp[i] += temp[i-1]; for (int i = end - begin - 1; i >= 0; --i) { out[temp[*(begin + i)] - 1] = *(begin + i); --temp[*(begin + i)]; } for (int i = 0; i < end - begin; ++i) *(begin + i) = out[i]; }
原文链接:https://www.cnblogs.com/yxsrt/p/12193682.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:Big Event
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 排序汇总 2020-05-05
- 二叉排序树 2020-05-02
- 排序算法之快速排序代码c++ 2020-04-01
- tmp 2020-04-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash