配置設定排序之"計數排序"

    假設，有20個随機整數，取值範圍是0到10，需要對其排序。可能第一反應是使用快速排序啊，快排的時間複雜度是O(nlog n)！但是，可不可以比O(nlog n)更快呢？這就是這篇文章要介紹的計數排序(從名字上來看，就是計算數字出現頻次的排序方法，非常的見名知意)。

計排的實作

　　因為取值範圍是0到10（整數的值在0,1,2,3,4,5,6,7,8,9,10裡），共有11個數值，是以需要11個坑，我們定義一個長度是12的數組array，每個元素的初始值是0，然後對20個随機整數進行循環，對應的元素值加1。最後，輸出array，就是排好序的。

　　比如有20個整數，分别是 9,2,8,5,1,8,6,9,5,8,1,5,8,3,4,7,0,6,2,10

　　初始化數組array

數組下标	1	2	3	4	5	6	7	8	9	10
頻率

　　要排序的随機整數，第一個值是9，那數組下标是9的分布值加1，是以array變成

數組下标	1	2	3	4	5	6	7	8	9	10
頻率	1

　　第二個值是2，數組下标是2的分布值加1

數組下标	1	2	3	4	5	6	7	8	9	10
頻率	1	1

　　後面的以此類推。最終輸出array，元素的值是幾，就輸出幾次。這個數組顯然是有序的了。 　　

數組下标	1	2	3	4	5	6	7	8	9	10
頻率	1	2	2	1	1	3	2	1	4	2	1

　　代碼如下

def sort(array):
    # 1.擷取數組内的最大值和最小值，來确定數組的size
    max = array[0]
    min = array[0]
    for i in array:
        if i > max:
            max = i
        if i < min:
            min = i

    # 2.定義定長數組，數組的元素初始值是0（這裡偷懶使用了清單生成式）
    sort_array = [0 for i in range(max - min + 1)]

    # 3.計數
    for i in array:
        sort_array[i - min] = sort_array[i - min] + 1

    # 4.獲得排序後的數組
	sortArray = [0 for i in array]
	index = 0
	for i, value in enumerate(countArray):
		for j in range(1, value + 1):
			sortArray[index] = i + min
			index = index + 1
	return sortArray

if __name__ == "__main__":
    array = [9, 2, 8, 5, 1, 8, 6, 9, 5, 8, 1, 5, 8, 3, 4, 7, 0, 6, 2, 10]
    sort_array = sort(array)
    print(sort_array)
           

　　下面是輸出結果

[0, 1, 1, 2, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 8, 8, 9, 9, 10]

Process finished with exit code 0
           

　　從代碼實作來看，也不複雜，甚至很簡單。

優化版的計排

　　上面的算法，因為有一個雙重fou循環，還可以在優化下。

　　假設考試是十分制的，共有20個同學，同學的考試成績是上面的那20個數（9, 2, 8, 5, 1, 8, 6, 9, 5, 8, 1, 5, 8, 3, 4, 7, 0, 6, 2, 10），考試獲得9分的有兩個同學，那到底誰是第二、誰是第三呢？

上面的表格，需要更新一下，頻率一欄，需要變成“分布值”了，它的值是上一格的值和自身的值之和

數組下标	1	2	3	4	5	6	7	8	9	10
分布值	1	3(1+2)	5(3+2)	6(5+1)	7(6+1)	10(7+3)	12(10+2)	13(12+1)	17(13+4)	19(17+2)	20(19+1)

然後對分布值數組輸出，第一個是下标10的，周遊之後分布值表格的下标10的分布值就減1，它是第一名（總人數-分布值+1）

數組下标	1	2	3	4	5	6	7	8	9	10
分布值	1	3	5	6	7	10	12	13	17	19	19(20-1)

假如獲得9分的是張三和李四，周遊張三之後，表格下标9的值減1，它是第二名（2 = 20-19 +1）

數組下标	1	2	3	4	5	6	7	8	9	10
分布值	1	3	5	6	7	10	12	13	17	18(19-1)	19

李四是第三名(3 = 20 -18 + 1)

數組下标	1	2	3	4	5	6	7	8	9	10
分布值	1	3	5	6	7	10	12	13	17	17(18-1)	19

這樣的話，相同分數的同學，就分出分數排名了。

def sort2(array):
    # 1.擷取數組内的最大值和最小值，來确定數組的size
    max = array[0]
    min = array[0]
    for i in array:
        if i > max:
            max = i
        if i < min:
            min = i

    # 2.定義定長數組，數組的元素初始值是0（這裡偷懶使用了清單生成式）
    countArray = [0 for i in range(max - min + 1)]

    # 3.計數
    for i in array:
        countArray[i - min] = countArray[i - min] + 1

    # 4.計數的數組變形
    sum = 0
    for i,value in enumerate(countArray):
        sum = sum + value
        countArray[i] = sum

    # 5.獲得排序後的數組
    sortArray = [0 for i in array]
    for i in array:
        sortArray[countArray[i - min] - 1] = i
        countArray[i - min] = countArray[i - min] - 1

    return sortArray


if __name__ == "__main__":
    array = [9, 2, 8, 5, 1, 8, 6, 9, 5, 8, 1, 5, 8, 3, 4, 7, 0, 6, 2, 10]
    sort_array = sort2(array)
    print(sort_array)
           

複雜度

　　假設array元素有N個，取值範圍是M。

時間複雜度：3N(步驟1、步驟3、步驟5) + M(步驟4)，去掉系數，時間複雜度是O(N+M)

空間複雜度：隻考慮統計數組，那就是M

計排的缺陷

1. 數組的元素有小數。比如有一個元素是1.001,這種建立統計數組的話，那代價就太大太大了。
2. 數組内的元素跨度大。假如有十個數，最大是1000，最小是1，使用計排的話，得建立1000個長度的數組，這顯然也不合适的。