计数排序

1, 速度很快, 唯一缺陷是计数长度列表和排序的最大数字相等, 如果排序中的数字实在太大了, 创建的列表太长了比如2的32次方

import random

def count_sort(li, max_count =21):
    count = [0 for _ in range(max_count+1)]
    for val in li:
        count[val] += 1
    li.clear()
    for ind, val in enumerate(count):
        for i in range(val):
            li.append(ind)
li = [random.randint(0,20) for _ in range(8)]
random.shuffle(li)
print('排序前',li)
count_sort(li)
print('排序后',li)

2, 稍稍的改进,减少计数列表的的长度, 如果最小数实在太小, 无法减少

import random

def count_sort(li):
    min ,max_count = li[0],li[0]
    for i in li:
        if i > max_count:
            max_count = i
        if i < min:
            min = i
    count = [0 for _ in range(max_count+1-min)]
    for val in li:
        count[val-min] += 1
    li.clear()
    for ind, val in enumerate(count):
        for i in range(val):
            li.append(ind+min)
li = [random.randint(10,20) for _ in range(8)]
random.shuffle(li)
print('排序前',li)
count_sort(li)
print('排序后',li)