线性排序
发布网友
发布时间：2023-03-12 12:03
共1个回答
热心网友
时间：2023-10-18 00:27
（1）就是将数据放入已经排好序的桶中，然后对桶中的数据分别进行排序，最后按照桶的顺序将数据拿出来，就是排完序的样子。
例如：需要对100万个用户按照年龄进行排序，可以将0-9岁的放到1号桶，10-19岁的放到2号桶，20-29岁的放到3号桶。。。。100-119岁。。。然后在将各个桶里面的数据利用其它排序方法（例如快排）排好序，最后按照桶的大小顺序将元素取出来。
（2）
（3）时间复杂度分析：
如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。
（4）桶排序的弊端：
要保证桶排序法的时间复杂度为线性的，需要让各个桶内的元素数量均匀，如果出现极端情况，比如所有的元素都几种到了同一个桶里面，那么桶排序的时间复杂度就会退化为O(nlogn)。由此看来，桶排序的应用场景非常有限。
（1）计数排序法是一种特殊的桶排序法，它是将数据范围缩到最小。
例如：同样是将100万个人按照年龄排序，可以将0岁放入1号桶，2岁放入2号桶。。。。。
（2）那么“计数”体现在什么地方？
同样是上面的例子，我们将数据规模缩小来说明这个事。
假如有8位小朋友，年龄分别是： 2，5，3，0，2，3，0，3
创建一个数据来存储各个年龄的人数：
事实上现在除了知道每个年龄的人数之外，还知道了在它前面有多少人。比如：3岁的有3人，前面有4人。
（3）应用中，为了把这个事办的更省心一些，会直接在每一个年龄的上面标一个数字，这个数字表示该年龄前面所有年龄人数之和加上该年龄的人数。例如：上面的例子
排序的时候，遍历到第一个3的时候，将它放到索引为6的位置，然后将它上面的数字减一，第二次遇到3时，将它放到第5的位置，上的数字再减一，所有的年龄都是同样的操作。
（4）
待续。。
