桶排序——不基于比较的排序

原创
03/31 21:25
阅读数 46

场景

  1. 员工按照age排序;

可以进行词频统计表,建一个数组,然后age的范围是150之内,就150个元素,每一个员工在对应的数组元素的age进行加1;然后按照数组顺序倒出来即可以得到排序; 这是计数排序,是捅排序思想的一个类型; 严重的弱点,该方法与样本本身有强相关;所有的桶排序思想都与样本状态强相关;只要样本稍大,就可能不行; 时间复杂度 o(n);

桶排序:桶就是容器,计数排序桶就是数组的一个词频统计;基数排序桶是队列,先进先出; 桶排序是一种思想,就是i使用容器即桶来进行操作;

  1. 基数排序的前提假设,每一个数都要求是非负的十进制;

基数排序:是0-9个捅,然后每个桶是一个队列,先进先出;先按照个位先入桶再出桶,再十位,再百位,后面入的会把前面入的顺序颠覆掉;

如果破坏了基数排序原本的数据状况,也是能改出来,只是代价就比较高了; 不基于比较的排序,只要样本改动一点点,代码大量重写;比如用负数来做基数排序,需要深度改写,补符号等;

基于比较的排序,复杂度极限就是o(nlogn);但是不基于比较的排序可以达到o(n),只是样本状态比较窄; 所以在做题中,如果非特殊要求,复杂度都是按照基于比较排序考虑;

桶排序的时间复杂度一般说是o(n),但是基数排序的时间复杂度是o(nlog10^max),只是一般max不是太大,所以说是o(n); 空间复杂度o(m),就是不确定,他与样本量关系不大

计数排序和基数排序
1)一般来讲,计数排序要求,样本是整数,且范围比较窄
2)一般来讲,基数排序要求,样本是10进制的正整数
一旦要求稍有升级,改写代价增加是显而易见的

基于比较的排序

之前所有的排序都是基于比较的排序;
就是告诉怎么去比较大小;
然后后面的所有排序都是可以服用的;
java里面就是comparetor,c++里面就是重载比较运算符; 比较器可以很好的应用在根据特殊标准排序的结构上

展开阅读全文
打赏
0
0 收藏
分享
加载中
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部