数据结构定义和算法--排序--桶排序
算法原理
- 将排序的元素放到几个连续的桶里，每个桶里的元素进行排序；
- 桶里的元素排好之后再把所有桶里的元素按照顺序取出来，就是排好顺序的了；
使用条件
- 要排序的元素容易划分到m个桶里，并且桶与桶之间有天然的大小顺序；
- 每个桶里分到的元素比较平均；
适用场景
- 桶排序适合外部排序，即存储在外部磁盘的数据；
应用案例
- 需求描述：有10GB的订单数据，需要按照订单金额进行排序，但内存有限（只有几百兆）
- 解决思路：
- 扫描一遍文件，看订单金额范围，比如1~10万元，那么就分100个桶；
- 第一个桶存储金额1~1000元之间的订单，第二个桶存储1001~2000之间的订单，依此类推；
- 每个桶对应一个文件夹，并按照金额大小进行排序编号（00， 01， 02， ...，99）；
- 将100个小文件夹依次放入内存进行快排；
- 所有文件排序好后，只需按照文件名称从小到大依次读取每个小文件的订单即可；
- 注意点：若单个文件无法全部载入内存，则对该文件继续按照前面的思路进行处理；