您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)如何使用python實(shí)現(xiàn)計數(shù)排序與桶排序,小編覺得挺實(shí)用的,因此分享給大家做個參考,希望大家閱讀完這篇文章后可以有所收獲。
計數(shù)排序
找到給定序列的最小值與最大值
創(chuàng)建一個長度為最大值-最小值+1的數(shù)組,初始化都為0
然后遍歷原序列,并為數(shù)組中索引為當(dāng)前值-最小值的值+1
此時數(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ù)排序的缺點(diǎn)
當(dāng)數(shù)值中有非整數(shù)時,計數(shù)數(shù)組的索引無法分配
桶排序
桶排序原理:
桶排序與計數(shù)排序類似,但可以解決非整數(shù)的排序
桶排序相當(dāng)于把計數(shù)數(shù)組劃分為按順序的幾個部分
每一部分叫做一個桶,它來存放處于該范圍內(nèi)的數(shù)
然后再對每個桶內(nèi)部進(jìn)行排序,可以使用其他排序方法如快速排序
最后整個桶數(shù)組就是排列好的數(shù)據(jù),再將其返回給原序列
舉例:
桶排序?qū)崿F(xiàn)
這里選擇桶的數(shù)量為序列元素個數(shù)+1,范圍分別是5等分與最大值,和上面那個圖一樣。
具體問題應(yīng)該按照具體情況進(jìn)行桶劃分
這里桶內(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]
關(guān)于“如何使用python實(shí)現(xiàn)計數(shù)排序與桶排序”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學(xué)到更多知識,如果覺得文章不錯,請把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。