如何使用python實現計數排序與桶排序

這篇文章將為大家詳細講解有關如何使用python實現計數排序與桶排序，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

計數排序

1. 找到給定序列的最小值與最大值

2. 創建一個長度為最大值-最小值+1的數組，初始化都為0

3. 然后遍歷原序列，并為數組中索引為當前值－最小值的值＋１

4. 此時數組中已經記錄好每個值的數量，自然也就是有序的了

例如：

計數排序實現

下面為列表的計數排序

def count_sort(s):
  """計數排序"""
  # 找到最大最小值
  min_num = min(s)
  max_num = max(s)
  # 計數列表
  count_list = [0]*(max_num-min_num+1)
  # 計數
  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)

計數排序的缺點

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

桶排序

桶排序原理：

1. 桶排序與計數排序類似，但可以解決非整數的排序

2. 桶排序相當于把計數數組劃分為按順序的幾個部分

3. 每一部分叫做一個桶，它來存放處于該范圍內的數

4. 然后再對每個桶內部進行排序，可以使用其他排序方法如快速排序

5. 最后整個桶數組就是排列好的數據，再將其返回給原序列

舉例：

桶排序實現

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

具體問題應該按照具體情況進行桶劃分

這里桶內部排序直接調用了sorted

def bucket_sort(s):
  """桶排序"""
  min_num = min(s)
  max_num = max(s)
  # 桶的大小
  bucket_range = (max_num-min_num) / len(s)
  # 桶數組
  count_list = [ [] for i in range(len(s) + 1)]
  # 向桶數組填數
  for i in s:
    count_list[int((i-min_num)//bucket_range)].append(i)
  s.clear()
  # 回填，這里桶內部排序直接調用了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]

關于“如何使用python實現計數排序與桶排序”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。