python算法學(xué)習(xí)之桶排序算法實(shí)例(分塊排序)
# -*- coding: utf-8 -*-
def insertion_sort(A):
"""插入排序,作為桶排序的子排序"""
n = len(A)
if n <= 1:
return A
B = [] # 結(jié)果列表
for a in A:
i = len(B)
while i > 0 and B[i-1] > a:
i = i - 1
B.insert(i, a);
return B
def bucket_sort(A):
"""桶排序,偽碼如下:
BUCKET-SORT(A)
1 n ← length[A] // 桶數(shù)
2 for i ← 1 to n
3 do insert A[i] into list B[floor(nA[i])] // 將n個(gè)數(shù)分布到各個(gè)桶中
4 for i ← 0 to n-1
5 do sort list B[i] with insertion sort // 對(duì)各個(gè)桶中的數(shù)進(jìn)行排序
6 concatenate the lists B[0],B[1],...,B[n-1] together in order // 依次串聯(lián)各桶中的元素
桶排序假設(shè)輸入由一個(gè)隨機(jī)過(guò)程產(chǎn)生,該過(guò)程將元素均勻地分布在區(qū)間[0,1)上。
"""
n = len(A)
buckets = [[] for _ in xrange(n)] # n個(gè)空桶
for a in A:
buckets[int(n * a)].append(a)
B = []
for b in buckets:
B.extend(insertion_sort(b))
return B
if __name__ == '__main__':
from random import random
from timeit import Timer
items = [random() for _ in xrange(10000)]
def test_sorted():
print(items)
sorted_items = sorted(items)
print(sorted_items)
def test_bucket_sort():
print(items)
sorted_items = bucket_sort(items)
print(sorted_items)
test_methods = [test_sorted, test_bucket_sort]
for test in test_methods:
name = test.__name__ # test.func_name
t = Timer(name + '()', 'from __main__ import ' + name)
print(name + ' takes time : %f' % t.timeit(1))
- python實(shí)現(xiàn)冒泡排序算法的兩種方法
- python 實(shí)現(xiàn)插入排序算法
- python選擇排序算法的實(shí)現(xiàn)代碼
- python 實(shí)現(xiàn)歸并排序算法
- Python實(shí)現(xiàn)各種排序算法的代碼示例總結(jié)
- Python實(shí)現(xiàn)的直接插入排序算法示例
- 八大排序算法的Python實(shí)現(xiàn)
- python 實(shí)現(xiàn)堆排序算法代碼
- Python實(shí)現(xiàn)的幾個(gè)常用排序算法實(shí)例
- python實(shí)現(xiàn)歸并排序算法
- python常用的各種排序算法原理與實(shí)現(xiàn)方法小結(jié)
相關(guān)文章
對(duì)python 矩陣轉(zhuǎn)置transpose的實(shí)例講解
下面小編就為大家分享一篇對(duì)python 矩陣轉(zhuǎn)置transpose的實(shí)例講解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-04-04Python?dateutil庫(kù)簡(jiǎn)化日期時(shí)間處理利器使用場(chǎng)景實(shí)踐
在Python中,處理日期和時(shí)間是常見(jiàn)的任務(wù)之一,dateutil庫(kù)是Python標(biāo)準(zhǔn)庫(kù)中datetime模塊的擴(kuò)展,提供了許多方便的工具和函數(shù),簡(jiǎn)化了日期和時(shí)間的操作2023-12-1230秒輕松實(shí)現(xiàn)TensorFlow物體檢測(cè)
這篇文章主要為大家詳細(xì)介紹了30秒輕松實(shí)現(xiàn)TensorFlow物體檢測(cè),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-03-03利用Python解決Excel問(wèn)題的最佳方案總結(jié)
python處理excel文件有很多方法,最開(kāi)始接觸的是xlrd、xlsxwriter模塊,分別用于excel文件的讀、寫(xiě),后來(lái)又學(xué)習(xí)了openpyxl模塊,可以同時(shí)完成excel文件的讀、寫(xiě),下面這篇文章主要給大家介紹了關(guān)于利用Python解決Excel問(wèn)題的最佳方案,需要的朋友可以參考下2023-04-04Python 如何手動(dòng)編寫(xiě)一個(gè)自己的LRU緩存裝飾器的方法實(shí)現(xiàn)
本文主要介紹了Python如何手動(dòng)編寫(xiě)一個(gè)自己的LRU緩存裝飾器,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12提升Python Scrapy庫(kù)數(shù)據(jù)采集速度實(shí)現(xiàn)高效爬蟲(chóng)
Scrapy是一個(gè)強(qiáng)大而靈活的Python爬蟲(chóng)框架,被廣泛用于數(shù)據(jù)采集、網(wǎng)站抓取和網(wǎng)絡(luò)爬蟲(chóng)開(kāi)發(fā),本文將深入介紹Scrapy的功能和用法,并提供豐富的示例代碼,幫助更好地理解和應(yīng)用2023-11-11基于Python編寫(xiě)一個(gè)B站全自動(dòng)抽獎(jiǎng)的小程序
本文將利用Python編寫(xiě)一個(gè)B站全自動(dòng)抽獎(jiǎng)的小程序,可以實(shí)時(shí)監(jiān)控自己關(guān)注的UP主,如果關(guān)注的UP主中有人發(fā)布了抽獎(jiǎng)的動(dòng)態(tài),就自動(dòng)參與這個(gè)抽獎(jiǎng)。這樣就能不錯(cuò)過(guò)任何一個(gè)可以暴富的機(jī)會(huì)了。需要的可以參考一下2022-03-03