python算法学习之桶排序算法实例(分块排序)
发布时间:2022-09-08 13:11:33
# -*- 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))
猜你喜欢
- 数据及配置文件之争数据及文件通常有三种类型:配置文件型:如ini,conf,properties文件,适合存储简单变量和配置项,最多支持两层
- 如何利用Image Data Type从数据库中读取图片,并在主页中显示图形?然后,写如下代码:< % @&nbs
- 一、什么要备份数据库 ?在现实IT世界里,我们使用的服务器硬件可能因为使用时间过长,而发生故障;Windows系列服务器有可能蓝屏或者感染病
- 转:coolcode.cn通常情况下,我们的网页要指定一个编码字符集,如 GB2312、UTF-8、ISO-8859-1 
- 这个符合设计标准的三 级向上弹出菜单,纯css代码控制,没有使用javascript脚本,绿色环保,呵呵。兼容性应该更好。截图:<!D
- 从MySQL 5.0.2开始,通过mysql_stmt_attr_set() C API函数实现了服务器端光标。服务器端光标允许在服务器端生
- 一、变量和表达式>>> 1 + 1 &n
- 是的,我们知道:我们可以为border设置它的width,这个border的宽度可以是5px,可是10px,可以是20px,可以是随意数值。
- 在本人看来,HTML 5是一个妥协方案,虽不激进,但更能推动技术的继续进步。没有命名空间,元素也不要求闭合(当然这并不是优点),浏览器也可以
- 在安装wordpress的时候,按照里面的readme.html的步骤进行安装,但是在访问wp-admin/install.php的时候就出
- MySQL Group By用法我们现在回到函数上。记得我们用 SUM 这个指令来算出所有的 Sales (营业额)吧!如果我们的需求变成是
- 本文实例讲述了Python 操作mysql数据库查询之fetchone(), fetchmany(), fetchall()用法。分享给大家
- 编写思路:把本地文件在客户端通过base64编码以后发送目的地.测试过程中,上传文件过大,导致超时不成功,后来经过改善.把编码分
- Python 中提供了对时间日期的多种多样的处理方式,主要是在 time 和 datetime 这两个模块里。一、time 模块time 模
- Guide to the Section 508 Standards for Electronic and Information Tech
- 最近在学习python,做一些python练习题github上几年前的练习题有一题是这样的:使用 Python 实现:对着电脑吼一声,自动打
- 在用wordpress这个博客的时候,我很奇怪的发现,最近写的内容排在第一页,而最早写的成了最后页。这显然有悖逻辑,正常的情况应该是最早写的
- 1.什么是内存逃逸在一段程序中,每一个函数都会有自己的内存区域分配自己的局部变量,返回值,这些内存会由编译器在栈中进行分配,每一个函数会分配
- 压缩数据库文件可以提高数据库的性能,但是有些时候在压缩数据库时,系统会提醒用户该数据库不能压缩。如果在Access数据库中删除数据库对象,或
- 很多人可能认为门户网站首页设计只是把一些导航、资讯内容和广告堆积起来摆放得好看就可以了,虽然这个观点也并不是完全错误的,确实门户网站首页是由