桶排序 Bucket Sort

• 思想说明
  1. 桶排序只包含一种操作，元素的移动，不涉及元素之间的比较操作
  2. 将要排序的数据分到几个有序的桶里，每个桶里的数据单独进行排序
  3. 桶内排序完成后（归并排序），把每个桶里的数据按照顺序依次取出
• 分析
  1. 空间复杂度 O（n），不是原地排序算法
  2. 最好时间复杂度 O（n），最坏时间复杂度 O（nlog(n)）
  3. 是稳定的排序算法
• 应用场景分析
  1. 排序的数据需要很容易的划分成 m 个桶
  2. 桶和桶之间有天然的大小关系
  3. 数据在各个桶之间的分布比较均匀
  4. 比较适合用在外部排序中，因数据量较大，内存有限而无法全部加载在内存中

计数排序 Counting Sort

• 思想说明
  1. 计数排序只包含一种操作，元素的移动，不涉及元素之间的比较操作
  2. 排序的数据划分成 m 个桶，每个数据对应的值为一个桶，每个桶中存放的是这个值对应的数据个数
  3. 将桶中存放的数据个数依次相加，得到位置数组
  4. 创建和原数据大小一致的数组，从后到前遍历原数据，将数据对应的值的桶中存放的数据个数取出（x），放在创建数组 x-1 的位置上，并将桶中的值 - 1
• 分析
  1. 空间复杂度 O（n），不是原地排序算法
  2. 时间复杂度 O（n）
  3. 是稳定的排序算法（从后到前遍历原数据）
• 应用场景分析
  1. 排序的数据范围比较小
  2. 只能给非负整数排序，如果要排序的数据是其他类型，要在不改变相对大小的情况下，转化为非负整数

基数排序 Radix Sort

• 思想说明
  1. 将要排序的数据按“位”分割
  2. 从后往前的按照“位”来排序数据，排序数据的算法必须是稳定的
• 分析
  1. 空间复杂度 O（1），是原地排序算法
  2. 最好时间复杂度 O（n）（“位”次桶排序或计数排序）
  3. 是稳定的排序算法
• 应用场景分析
  1. 要排序的数据可以分割出独立的“位”来比较，
  2. “位”之间有递进的关系，若 a 数据的高位比 b 数据的大，则剩下的低位不用比较
  3. 每一“位”的数据范围不能过大，要可以用线性排序算法来排序