首先證明一波排序算法的運算性能，如下圖。對于50萬個數據的無序列表，時間復雜度為的桶排序和計數排序明顯比復雜度為的歸并排序和快速排序性能好至少一個數量級。

1. 計數排序

?1.1 基本原理：首先確定列表的最大值max和最小值min，然后創建一個 (max+1-min) 長度的二維空列表，第一維是數據的大小，第二維記錄該數據的個數。然后對待排序列表進行逐個元素掃描，將元素根據大小放入?(max+1-min) 長度的空列表，比如值為 min的元素就放在第0個，并且相應計數加1。直至列表掃描結束，那么(max+1-min) 長度的二維列表會記錄每個值的個數，然后數據再逐個從列表彈出至原列表即可，動畫效果。

1.2 python代碼

def countsort(lst):if len(lst)<2:return lstL = lst[:]min = L[0]max = L[0]for i in range(1,len(L)):if L[i]>max:max = L[i]elif L[i]<min:min = L[i]L_tmp = [[x, 0] for x in range(min, max+1)]for x in L:L_tmp[x-min][1] += 1L.clear()for i in range(min, max+1):while L_tmp[i-min][1]:L_tmp[i-min][1] -= 1L.append(i)return L

2. 桶排序

2.1 基本原理：首先求得列表的最大值max和最小值min，確定列表的范圍。然后設置桶的容量，那么根據列表總數和桶的容量，就可以得到桶的數量。現在可以根據數據大小，把數據放入相應桶中，示例如下。此時對每個桶進行排序，堆排序或者快速排序都可以，最后把排好序的數據放回原列表就可以了。

#桶排序原理 L = [3,7,1,0,5,7,7,9,3,1]----------------------------------------第一步---------------------------------------- 確定列表最大值max=9, 最小值min=0；這里調整桶的容量為3，則math.ceil(10/3)得到4個空桶 并且第一個空桶放0-2的數據，第二個空桶放3-5的數據，第三個空桶放6-8的數據，第二個空桶放9-11的數據----------------------------------------第一步---------------------------------------- 掃描列表L，根據數據大小放入不同的桶，[[1,0,1], [ 3,5,3], [7,7,7], [9]] 此時各個桶之間是有序的，我們再對各個桶內的數據使用快排進行排序，最后再把數據添加至原列表即可。

2.2 python代碼

def bucketsort(lst):if len(lst)<2:return lstL = lst[:]min = L[0]max = L[0]for i in range(1,len(L)):if L[i]>max:max = L[i]elif L[i]<min:min = L[i]m_len = 10cnt_m = math.ceil((max+1-min)/m_len)L_m = [[] for i in range(cnt_m)]for x in L:L_m[(x-min)//m_len].append(x)L.clear()for l_m in L_m:L.extend(quicksort1(l_m))return L

3. 基數排序?

3.1 基本原理：對數據的每一位（個位、十位、百位）進行排序，分為最低有效位LSD（從個位開始排序）和最高有效位MSD（從最高位開始排序）。網上都說對于位數多的數據，采用MSD更好，但沒找到原因，自己揣測是因為位數多數據少的話，更容易有序，如下簡單例子。

L = [8,16,123,15,3,9,678,287]#MSD ---------------------------------------第一步--------------------------------------- 最大值是123，則得到位數為3，從百位開始排序,根據百位是多少，放入第幾個列表(總共10個，0-9)，沒有則空著，如下。 得到L=[[8,16,15,3,9], [123], [287], [], [], [], [678], [], [], []]---------------------------------------第二步--------------------------------------- 其實此時數據已經大致有序，[123],[287],[678]三個列表不需要排序，只需對LL=[8,16,15,3,9]進行排序。 此時對LL=[8,16,15,3,9]的十位進行排序. 得到LL=[[8,3,9], [16,15], [], [], [], [], [], [], [], []]---------------------------------------第三步--------------------------------------- 此時再對個位進行排序，則可得到排好序的整個列表#LSD ---------------------------------------第一步--------------------------------------- 最大值是123，則得到位數為3，逐個掃描，從個位開始排序,根據個位是多少，放入第幾個列表，沒有則空著，如下。 得到L=[[], [], [], [123,3], [], [15], [16], [287], [8,678], [9]]---------------------------------------第二步--------------------------------------- LSD通過個位排序后的列表“看起來”更亂了。而且LSD與MSD不同，LSD此時需要把各個列表重新合并到一個列表, 得到LL=[123,3,15,16,287,8,678,9]。然后現在對數據逐個掃描并對十位進行排序，得到如下列表。 得到LL=[[3,8,9], [15,16], [123], [], [], [], [], [678], [287], []]---------------------------------------第三步--------------------------------------- 此時到最后一步，列表大致有序了。如果位數多的話，那么進行到第三步時，數據看著還是挺亂的，因此排序代價也更高。 最后再合并得到LLL=[3,8,9,15,16,123,678,287],然后對數據逐個掃描并對百位進行排序，得到如下列表。 LLL=[[3,8,9,15,16], [123], [287], [], [], [], [678], [], [], []] 此時列表已有序，最后合并即可

3.2 MSD代碼?

def resort(lst, cnt):if not cnt:return lstdiv = pow(10, cnt-1)L_tmp = [[] for i in range(10)]for x in lst:L_tmp[x//div%10].append(x)lst.clear()for i in range(10): lst.extend(resort(L_tmp[i], cnt-1))return lstdef basesort(lst):if len(lst)<2:return lstL = lst[:]max = L[0]for i in range(1,len(L)):if L[i]>max:max = L[i]cnt_bit = 0while max:cnt_bit += 1max //= 10return resort(L, cnt_bit)

4. 運算性能及總結?

4.1 性能分析

此時桶容量為10效果較好

此時桶容量為50效果較好，所以桶容量應隨著數據范圍的增大而相應增大。

通過數據的位數變化以及范圍變化，可以得到基數排序因為數據的位數增多而性能下降，計數排序則由于數據范圍增加而性能下降。

4.2 總結：

① 計數排序非常簡單易懂，而且運算性能也不差，但是運算性能隨著數據范圍的增大而減弱。

② 桶排序需要根據數據范圍調整桶的容量來確定桶的個數，桶數量越多，數據分布越均勻（這樣每個桶的數據量差不多），排序性能越好，因為N個數據，M個桶，每個桶有N/M的數據，則每個桶排序復雜度為，M個桶的排序復雜度為，N/M越小越好，即桶越多越好。最好情況是一個桶中只有一個數據，都不需要排序，但是內存消耗也相應增加；桶數量越少，排序性能越差。

③ 基數排序，運算性能受數據位數增多而下降

總結

以上是生活随笔為你收集整理的计数排序、桶排序和基数排序的运算性能对比及总结区别（附python代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。