一、問題

對列表進(jìn)行排序，已知列表中的數(shù)范圍都在0到100之間。設(shè)計(jì)時(shí)間復(fù)雜度為O(n)的算法。

二、解決思路

我們已知數(shù)字的范圍，那么我們可以將數(shù)字的個(gè)數(shù)得到：

例如：有一個(gè)0~5的列表

[1,3,2,4,1,2,3,1,3,5]? ?則共有0個(gè)0，3個(gè)1，2個(gè)2，3個(gè)3，1個(gè)4，1個(gè)5。

再直接進(jìn)行排序即可，可以將原來的列表覆蓋。

示例代碼如下：

def count_sort(li, max_count = 100):count = [0 for _ in range(101)]  #創(chuàng)建101個(gè)數(shù)字為0的列表for val in li:   #遍歷列表中的元素count[val] += 1   # 找到后+1 ；count[val]相當(dāng)于元素的數(shù)量li.clear()# 再一次遍歷count，其中ind = val代表數(shù)的值，v = count[val]代表數(shù)字有幾個(gè)for ind, v in enumerate(count):  # v代表有幾個(gè)數(shù)值, i代表數(shù)值for i in range(v):li.append(ind)import random
li = [random.randint(0,100) for i in range(100)]
print(li)
count_sort(li)
print(li)

輸出結(jié)果如下：

注意點(diǎn)：

1. 此時(shí)n為li的長度，代碼中雖然是一共有兩層循環(huán)，但是長度都不是n，兩層循環(huán)的復(fù)雜度一共為O(n) 。
2. 計(jì)數(shù)排序使用需要一個(gè)已知條件：已知數(shù)值的范圍。