计数排序和基数排序

这两种排序方法的时间复杂度O(n), 不同于比较排序

计数排序

1. 基本方法:
   新建辅助数组, 把原数组中的值对应的辅助数组索引处值计数, 利用索引的有序性对原数组进行排序
2. 标记变量

k  原数组中最大值+1

3. 代码

def counting_sort(arr, k):
  result = []
  # 辅助数组
  arr_temp = [0]*k
  # 遍历原数组, 元素值对应的辅助数组索引处值+1
  for i in arr:
    arr_temp[i] += 1
  # 累加求和
  # 为什么不直接遍历辅助数组, 通过值来还原排序的数组?
  # for i in range(k):
  #  while arr_temp[i] > 0:
  #    result.append(i)
  #    arr_temp[i] -= 1
  for i in range(k):
    if i > 0:
      arr_temp[i] = arr_temp[i] + arr_temp[i-1]
  # 还原排序的数组
  for i in range(len(arr)-1, -1, -1):
    # 原数组中值, 是辅助数组的索引, 假设辅助数组索引处的值n
    # 它是自身和比自身小的数字数量, 即结果数组中第n位
    result[arr_temp[arr[i]] - 1] = arr[i]
    arr_temp[arr[i]] -= 1

4. 适合有上限, 分布集中的整数数组

基数排序

1. 基本方法:
   根据数字的每一位进行排序. 利用该位上的值, 将其放入0-10数组中, 使其从局部有序到整体有序.
2. 标记变量:

radix 进制
k  最大位数

3. 代码:

import math

def  sort(a, radix=10):
  result = [[] for i in range(radix)] 
  # 最大位数
  k = math.ceil(math.log(max(a), radix))
  for i in range(k):
     for j in a:
      # 解析每个数该位上的数字
       num = j % 10**(i + 1) // 10**i
       result[num].append(j)
      # 清空原数组
     del a[:]
    for j in result:
      a.extend(j)

共同点:
利用映射关系, 将待排序中数组的值映射到辅助数组的索引上, 再通过索引的有序进行还原.