计数排序

计数排序参考： Hello 算法计数排序

说明

可以理解为将相同的数放在一起统计，分成一堆，那么根据数的大小依次就可以返回一个排序好的数组。

比如经过统计后，有 3 个 1， 2 个 2， 1 个 3，那么就可以返回 [1,1,1,2,2,3]

算法

设有 n 个待排序的数，待排序的数的范围为 [minNum, maxNum]，则 size = maxNum - minNum + 1 这些数的区间
创建一个 counts 数组，长度为 size，用于记录每个数出现的次数, 这里有个映射关系 index = num - minNum，即 num 对应的索引是 num - minNum
根据统计的次数，依次返回排序好的数组

复杂度分析

时间复杂度： $O (n + k)$
空间复杂度： $O (k)$

下面算法步骤中有个倒序操作，是为了保持原数序列的稳定性的一种操作。因此这个算法是稳定的。

这个算法在 k < log(n) 時，有一定的优势，但是在 k > log(n) 时，就不如快排了。

代码

class Solution(object):
  def countingSort(self, nums):
    minNum = min(nums)
    maxNum = max(nums)

    size = maxNum - minNum + 1

    counts = [0 for _ in range(size)]

    for num in nums:
      index = num - minNum
      counts[index] += 1


    # 对于数字排序可以用下面的方法
    # res = []
    # for i in range(size):
    #   count = counts[i]
    #   num = minNum + i

    #   while count > 0:
    #     res.append(num)
    #     count -= 1

    # 上面方法对于元数据查看有困难,更改下面方案
    for i in range(1, size):
      # 这里定位最后一个 num 的位置在 counts[num-minNum] 位置
      counts[i] += counts[i-1]

    res = [0] * len(nums)

    for num in reversed(nums):
      index = counts[num - minNum] -1
      res[index] = num
      counts[num-minNum] -= 1

    return res

if __name__ == "__main__":
  nums = [5,6,2,3,1,7,9,8,10,1,2]

  s = Solution()
  print(s.countingSort(nums))

计数排序 ​

说明 ​

代码 ​

计数排序

说明

代码