复制代码 代码如下:
# -*- coding: utf-8 -*-
def insertion_sort(A):
"""插入排序,作为桶排序的子排序"""
n = len(A)
if n <= 1:
return A
B = [] # 结果列表
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] // 桶数
2 for i ← 1 to n
3 do insert A[i] into list B[floor(nA[i])] // 将n个数分布到各个桶中
4 for i ← 0 to n-1
5 do sort list B[i] with insertion sort // 对各个桶中的数进行排序
6 concatenate the lists B[0],B[1],...,B[n-1] together in order // 依次串联各桶中的元素
桶排序假设输入由一个随机过程产生,该过程将元素均匀地分布在区间[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))
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- 《腾格尔 容中尔甲 亚东 高原三星 男人篇 3CD》[WAV/分轨][1GB]
- 命运圣契公测实测可用兑换码大全 命运圣契最新兑换码分享
- 黑神话悟空上品疾蝠精魄获取方法一览|上品疾蝠精魄收集攻略
- 《七龙珠电光炸裂!ZERO》GT角色预告片曝光,15位新角色登场
- [ABC]安娜-胆麦发烧女声[6N纯银镀膜][2016[低速原抓WAV+CUE]
- NewViennaOctetViennaWindSoloists-TheDeccaRecordings(2024)18CD[24-48][FLAC]-7
- 雨果唱片-三角琴《俄罗斯民间音乐系列-梁祝(中国名曲)》wav
- 《塞尔达传说:智慧的再现》新实机!无之世界介绍
- 任天堂公布《塞尔达传说》系列时间线:野炊与王泪独立在外
- 任天堂更新网络投稿规范:打击影响他人游戏体验行为
- 冼佩瑾.2024-女儿Daughter(EP)【杰威尔】【FLAC分轨】
- 黑豹乐队.1993-光芒之神【摇音晨【WAV+CUE】
- 曾轶可.2011-一只猫的旅行【天娱传媒】【WAV+CUE】
- 黑神话悟空上品狼刺客精魄获取方法一览|上品狼刺客精魄收集攻略
- 视觉小说《神椿市建设中REGENERATE》将于2025年2月20日发售