非比较排序

Count Sort(计数排序)

  • 基本思想：按照数据的键的大小创建相应大小的数组，当键是整数且键是唯一递增的，则可以将键映射到新数组的索引，在对应的索引中存放键对应的值。
  • 遍历原数组，新建一个数组记录原数组中每一个键以及对应出现的元素次数，存储到新数组中，记录完个数就可以算出每一个键值对应的在排序数组的起始值。再创建一个与数组个数一样的数组，将原数组的每一个元素通过新数组中记录的位置，将元素放入排序数组的相应记录位置。(每放入一个元素，其对应的位置数组的位置要加一)。

复杂度

  • 设数据的键的个数为NN，而键的种数为RR，则计数排序复杂度为Θ(N+R)\Theta(N+R)
  • 复杂度渐进函数族是多元函数，当一个变量占主要地位时，可以将另一个变量当作常数。
  • 空间复杂度Θ(N+R)\Theta(N+R)

稳定性

  • 稳定：不改变各相同元素的相对位置

适用性

  • 适用于数据数量较大的情况，数据大小在一定范围限制内，对于相同数据的相对位置有不变性需求。

Radix Sort(基数排序)

  • 基本思想：将整数按位数切割成不同的数字，然后按每个位数分别比较，即为逐位比较+计数比较的想法。

LSD Radix Sort(最小有效位基数排序)

  • 从数据的键的最低位开始逐步向高位进行按位计数排序。
  • 如果键的长度不相等，可以在短的整数前面补上0，直到长度保持一致。
  • 复杂度：Θ(WN+WR)\Theta(WN+WR)，其中WW为键的长度，NN为键的数目，RR为键的种数。
  • 空间复杂度：Θ(N+R)\Theta(N+R)

MSD Radix Sort(最大有效位基数排序)

  • 从数据的键的最高位开始逐步向低位进行按位计数排序。
  • 注意：每次排序完一位时，应该在每一个相同的键分区内各自进行下一位的排序，否则会打乱顺序。
  • 复杂度：
    • 最佳情况（仅比较最高位即排完序）：Θ(N+R)\Theta(N+R)
    • 最差情况（比较全部为才排完序）：Θ(WN+WR)\Theta(WN+WR)
    • 空间复杂度：Θ(N+WR)\Theta(N+WR)

SUMMARY

  • 数据结构
  • 图问题及算法
  • 集合与映射&排序算法

完结撒花！ ヾ(๑╹ヮ╹๑)ﾉ”