桶排序之计数排序总结

桶排序之计数排序总结

• 非比较排序
• 桶思想的一种

算法思想

• 量大但是范围小
  • 某大型企业数万名员工年龄排序
  • 如何快速得知高考名次

创建一个数组用来计数,数组长度是可以取值范围的长度
遍历原数组,用这个计数数组记录每一个值的出现次数

分配新数组和原数组一样长
遍历基数数组,将计数数组每个元素写入新分配的数组

时空复杂度对比

空间

n为原数组,k为计数数组

• n + k

  时间复杂度

  遍历了原数组n次,写入结果数组n次,遍历计数数组k次
• n/n (n + k) = O(n+k) or O(n)