桶排序(Bucket sort)
特点
将数据拆分到几个有序的桶里,每个桶里的数据再单独进行排序
桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列即为有序
复杂度分析
最好情况时间复杂度: O(n)
最坏情况时间复杂度:O(nlogn)
平均情况时间复杂度:O(n)
待排序数据有n个,把它们均匀地划分到m个桶内,每个桶里就有k=n/m个元素
每桶内部使用快排,时间复杂度为O(k*logk),整个桶排序时间复杂度为O(m* k*logk)
因k=n/m,所以整个桶排序时间复杂度为O(n*log(n/m))。
当桶的个数m接近数据个数n时,log(n/m)为非常小常量,桶排序时间复杂度接近O(n)
前提条件
首先,要排序的数据要很容易能划分成m个桶,并且桶与桶之间有着天然的大小顺序
其次,数据在各个桶之间的分布是比较均匀,否则极端情况下时间复杂度降为O(nlogn)
应用场景
桶排序比较适合用在外部排序中
数据量大且内存有限,将数据存储在外部磁盘,加载部分数据到内存进行排序再合并
计数排序(Counting sort)
特点
计数排序其实是桶排序的⼀种特殊情况。跟桶排序⾮常类似,只是桶的⼤⼩粒度不⼀样
排序过程
待排序的N(数值不大)个数据,最大值是K,我们就数据划分成K个桶
每个桶内的数据值都是相同的,省掉了桶内排序的时间。
找出待排序的数组中最大和最小的元素;
统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
不是原地排序算法
需借助额外存储空间
稳定的排序算法
时间复杂度
最好/最坏/平均情况时间复杂度: O(n)
总结
计数排序只能⽤在数据范围不⼤的场景中,如果数据范围k⽐要排序的数据n⼤很多,就不适合⽤计数排序了。
⽽且,计数排序只能给⾮负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对⼤⼩的情况下,转化为⾮负整数。
基数排序(Radix sort)
特点
原地排序算法
稳定排序算法
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。
有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。
最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。
基数排序基于固有顺序,所以属于稳定排序算法
排序过程
取数组中的最大数,并取得位数;
arr为原始数组,从最低位开始取每个位组成radix数组;
对radix进行计数排序(利用计数排序适用于小范围数的特点);
时间复杂度
时间复杂度为: O(k*n),其中k为数组中的数的最大的位数,基数排序的时间复杂度就近似于O(n)
总结
基数排序要求数据可以划分成高低位,位之间有递进关系
例如:有如下5组单词: hke、iba、hzg、ikf、hac,按照字母从a-z排序,具体如下: