打卡Day11
学习内容 : 线性排序：如何根据年龄给100万用户数据排序？
3种排序原理和适用场景
1.桶排序的原理和适用场景
桶排序（Bucket sort）
桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序
桶排序的时间复杂度：O(n)
适用场景：桶排序比较适合用在外部排序中。
2.计数排序的原理和适用场景
计数排序（Counting sort）
计数排序其实是桶排序的一种特殊情况。
计数排序的时间复杂度：O(n)
适用场景：计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
3.基数排序的原理和适用场景
基数排序（Radix sort）
这种排序目前还比较模糊，还需要细看。
如何给100万用户排序？
根据年龄给 100 万用户排序，遍历这 100 万用户，根据年龄将其划分到这 120 个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。
本文参考【极客时间】专栏《数据结构与算法之美》。
网友评论