桶排序
桶排序其实就是把数据分到各个桶中,比如把100个数据到10个桶中,然后每个桶再进行排序比如快排,桶和桶之间也是有顺序的
桶排序是线性排序
,也就是时间复杂度为O(n)
假设数据有 n 个,把它们均匀地划分到 m 个桶内
每个桶里就有 k=n/m 个元素
在快排那里我们分析过,快排的时间复杂度为O(nlogn)
那么每个桶内的时间复杂度为 O(k * logk)
m 个桶排序的时间复杂度就是 O(m * k * logk),因为 k=n/m,所以整个桶排序的时间复杂度就是 O(n*log(n/m))。
当桶的个数 m 接近数据个数 n 时,log(n/m) 就是一个非常小的常量,这个时候桶排序的时间复杂度接近 O(n)。
大家可以想到,均匀分布是桶排序的前提调节,假设一个极端的情况,所有的数据都被分进了一个桶里,那其实就是快排了,就不是线性排序
那么桶排序适合什么场景的使用呢?
桶排序比较适合用做外部排序
,数据量很大的适合,内存空间不足,就可以一个桶一个桶的排序,排完之后在按桶的顺序输出就行
计数排序
先说场景,假如要排序全校2w学生的体育成绩,成绩满分为5分
那么这就是一个经典的计数排序会应用的场景
把学生分为6个桶,0-5,把学生按成绩分到这6个桶内
为了讲解方便,现在假设学生人数为8个
这 8 个考生的成绩我们放在一个数组 A[8]中,它们分别是:2,5,3,0,2,3,0,3
我们对这个数组顺序求和,就能得到排名,如图
我们从后面开始扫描A数组,如下图,比如第一个数是3,读出C[3]的值为7,说明3排位为7,那么我们就把3填入到R[6]中,这是C[3]的值需要减1,表示3已经排走了,以此类推,就能得到R的结果
// 计算排序的关键步骤,有点难理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i]; c[a[i]]--;
}
基数排序
基数排序就是,当数据量很大,数值也很高,但是数据量之间存在前后关系
比如假设我们有 10 万个手机号码,希望将这 10 万个手机号码从小到大排序
可以先按照最后一位来排序手机号码,然后,再按照倒数第二位重新排序,以此类推,最后按照第一位重新排序。经过 11 次排序之后,手机号码就都有序了。
在每一位的排序中,可以用桶排序或者计数排序
所以如果要排序的数据有 k 位,那我们就需要 k 次桶排序或者计数排序,总的时间复杂度是 O(k*n)。
当 k 不大的时候,比如手机号码排序的例子,k 最大就是 11,所以基数排序的时间复杂度就近似于 O(n)。
指的注意的是,基数排序的底层排序必须是稳定的排序
,所以不能用快排
-部分图片和内容参考geek