python實現(xiàn)計數(shù)排序與桶排序?qū)嵗a

更新時間：2019年03月28日 15:55:39 作者：sfencs

這篇文章主要介紹了python計數(shù)排序與桶排序，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

計數(shù)排序

找到給定序列的最小值與最大值
創(chuàng)建一個長度為最大值-最小值+1的數(shù)組，初始化都為0
然后遍歷原序列，并為數(shù)組中索引為當前值－最小值的值＋１
此時數(shù)組中已經(jīng)記錄好每個值的數(shù)量，自然也就是有序的了

例如：

計數(shù)排序?qū)崿F(xiàn)

下面為列表的計數(shù)排序

def count_sort(s):
  """計數(shù)排序"""
  # 找到最大最小值
  min_num = min(s)
  max_num = max(s)
  # 計數(shù)列表
  count_list = [0]*(max_num-min_num+1)
  # 計數(shù)
  for i in s:
    count_list[i-min_num] += 1
  s.clear()
  # 填回
  for ind,i in enumerate(count_list):
    while i != 0:
      s.append(ind+min_num)
      i -= 1

if __name__ == '__main__':
  a = [3,6,8,4,2,6,7,3]
  count_sort(a)
  print(a)

計數(shù)排序的缺點

當數(shù)值中有非整數(shù)時，計數(shù)數(shù)組的索引無法分配

桶排序

桶排序原理：

桶排序與計數(shù)排序類似，但可以解決非整數(shù)的排序
桶排序相當于把計數(shù)數(shù)組劃分為按順序的幾個部分
每一部分叫做一個桶，它來存放處于該范圍內(nèi)的數(shù)
然后再對每個桶內(nèi)部進行排序，可以使用其他排序方法如快速排序
最后整個桶數(shù)組就是排列好的數(shù)據(jù)，再將其返回給原序列

舉例：

桶排序?qū)崿F(xiàn)

這里選擇桶的數(shù)量為序列元素個數(shù)+1，范圍分別是5等分與最大值，和上面那個圖一樣。

具體問題應(yīng)該按照具體情況進行桶劃分

這里桶內(nèi)部排序直接調(diào)用了sorted

def bucket_sort(s):
  """桶排序"""
  min_num = min(s)
  max_num = max(s)
  # 桶的大小
  bucket_range = (max_num-min_num) / len(s)
  # 桶數(shù)組
  count_list = [ [] for i in range(len(s) + 1)]
  # 向桶數(shù)組填數(shù)
  for i in s:
    count_list[int((i-min_num)//bucket_range)].append(i)
  s.clear()
  # 回填，這里桶內(nèi)部排序直接調(diào)用了sorted
  for i in count_list:
    for j in sorted(i):
      s.append(j)

if __name__ == '__main__':
  a = [3.2,6,8,4,2,6,7,3]
  bucket_sort(a) 
  print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]

總結(jié)

計數(shù)排序與桶排序都是以犧牲空間換時間，雖然很快，但由于可能產(chǎn)生大量的空位置導(dǎo)致內(nèi)存增大，尤其是計數(shù)排序。

桶排序中盡量使每個桶中的元素個數(shù)均勻分布最好

以上所述是小編給大家介紹的python計數(shù)排序與桶排序詳解整合，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！

您可能感興趣的文章: