python算法學(xué)習(xí)之桶排序算法實例(分塊排序)
# -*- 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個數(shù)分布到各個桶中
4 for i ← 0 to n-1
5 do sort list B[i] with insertion sort // 對各個桶中的數(shù)進(jìn)行排序
6 concatenate the lists B[0],B[1],...,B[n-1] together in order // 依次串聯(lián)各桶中的元素
桶排序假設(shè)輸入由一個隨機(jī)過程產(chǎn)生,該過程將元素均勻地分布在區(qū)間[0,1)上。
"""
n = len(A)
buckets = [[] for _ in xrange(n)] # n個空桶
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))
相關(guān)文章
對python 矩陣轉(zhuǎn)置transpose的實例講解
下面小編就為大家分享一篇對python 矩陣轉(zhuǎn)置transpose的實例講解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-04-04Python?dateutil庫簡化日期時間處理利器使用場景實踐
在Python中,處理日期和時間是常見的任務(wù)之一,dateutil庫是Python標(biāo)準(zhǔn)庫中datetime模塊的擴(kuò)展,提供了許多方便的工具和函數(shù),簡化了日期和時間的操作2023-12-12Python 如何手動編寫一個自己的LRU緩存裝飾器的方法實現(xiàn)
本文主要介紹了Python如何手動編寫一個自己的LRU緩存裝飾器,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-12-12提升Python Scrapy庫數(shù)據(jù)采集速度實現(xiàn)高效爬蟲
Scrapy是一個強(qiáng)大而靈活的Python爬蟲框架,被廣泛用于數(shù)據(jù)采集、網(wǎng)站抓取和網(wǎng)絡(luò)爬蟲開發(fā),本文將深入介紹Scrapy的功能和用法,并提供豐富的示例代碼,幫助更好地理解和應(yīng)用2023-11-11