搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

CountingSort(计数排序)原理及C++代码实现

[复制链接]
查看: 84|回复: 0

1万

主题

1万

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
32637
发表于 2020-1-15 03:25 | 显示全部楼层 |阅读模式
计数排序是需要假定输入数据的排序之一,它假定输入元素是0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,计数排序的时候复杂度为θ(n)。
由于不是经过比力来排序,所以它的时候复杂度可以到达θ(nlgn)以下。
计数排序是安定的排序之一。
代码以下:(仅供参考)
  1. //计数排序盼望输入数据都是小区间内的整数void CountingSort(int * const begin, int * const end) {    vector temp(10000); //假定输入值小于10000    vector 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];}
复制代码
免责声明:假如加害了您的权益,请联系站长,我们会实时删除侵权内容,感谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 全椒百姓网-全椒知名**,发布及时新鲜的全椒新闻资讯 生活信息 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表