快捷導(dǎo)航

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

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

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

計(jì)數(shù)排序

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

例如：

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

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

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

計(jì)數(shù)排序的缺點(diǎn)

當(dāng)數(shù)值中有非整數(shù)時(shí)，計(jì)數(shù)數(shù)組的索引無法分配

桶排序

桶排序原理：

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

舉例：

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

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

具體問題應(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]

總結(jié)

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

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

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

您可能感興趣的文章:

相關(guān)文章

Python基于ImageAI實(shí)現(xiàn)圖像識(shí)別詳解
ImageAI是一個(gè)面向計(jì)算機(jī)視覺編程的Python庫，支持最先進(jìn)的機(jī)器學(xué)習(xí)算法。本文將利用ImageAI實(shí)現(xiàn)圖像識(shí)別功能，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
2023-02-02
Django ImageFiled上傳照片并顯示的方法
今天小編就為大家分享一篇Django ImageFiled上傳照片并顯示的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2019-07-07
PyQt6/PySide6中QLabel類的使用
QLabel?是 PyQt6 或 PySide6 庫中用于顯示文本或圖像的控件,本文主要介紹了PyQt6/PySide6中QLabel類的使用,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2025-05-05
python的re模塊應(yīng)用實(shí)例
這篇文章主要介紹了python的re模塊應(yīng)用實(shí)例,包括了常見的正則匹配技巧,需要的朋友可以參考下
2014-09-09
基于Python做形狀相似性判斷的實(shí)現(xiàn)方法
在計(jì)算機(jī)視覺領(lǐng)域,形狀相似性判斷是圖像識(shí)別、目標(biāo)檢測(cè)、醫(yī)學(xué)影像分析等應(yīng)用的核心技術(shù),本文將系統(tǒng)解析基于Python的形狀相似性判斷方法,結(jié)合OpenCV等工具實(shí)現(xiàn)多種算法,并通過代碼示例展示具體實(shí)現(xiàn),需要的朋友可以參考下
2025-10-10
十行Python代碼實(shí)現(xiàn)文字識(shí)別功能
這篇文章主要和大家分享如何調(diào)用百度的接口實(shí)現(xiàn)圖片的文字識(shí)別。整體是用Python實(shí)現(xiàn)，所需要使用的第三方庫包括aip、PIL、keyboard、pyinstaller，需要的可以參考一下
2022-05-05
Python 連連看連接算法
這段時(shí)間老是“不務(wù)正業(yè)”的搞一些東西玩。之前的貪吃蛇，俄羅斯方塊激發(fā)了我研究游戲算法的興趣。經(jīng)過1個(gè)星期的構(gòu)思，連連看的連接算法終于出爐了。再過一段時(shí)間就基于這個(gè)算法使用JavaScript推出網(wǎng)頁版的連連看。下面是說明及代碼。
2008-11-11
利用python代碼管理Word文檔屬性信息
在Word文檔管理中,文檔屬性包含與文檔有關(guān)的關(guān)鍵信息,如標(biāo)題、作者、創(chuàng)建日期等,是進(jìn)行文檔管理的重要工具,本文將展示如何利用Python代碼來靈活操控Word文檔的屬性信息,從而滿足個(gè)性化與批量化文檔處理的需求,需要的朋友可以參考下
2024-05-05
Pygame游戲開發(fā)之太空射擊實(shí)戰(zhàn)添加圖形篇
相信大多數(shù)8090后都玩過太空射擊游戲，在過去游戲不多的年代太空射擊自然屬于經(jīng)典好玩的一款了，今天我們來自己動(dòng)手實(shí)現(xiàn)它，在編寫學(xué)習(xí)中回顧過往展望未來，在本課中，我們將討論如何在游戲中使用預(yù)先繪制的圖形
2022-08-08
Python3.9.0 a1安裝pygame出錯(cuò)解決全過程(小結(jié))
這篇文章主要介紹了Python3.9.0 a1安裝pygame出錯(cuò)解決全過程(小結(jié))，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-02-02