python算法学习之桶排序算法实例(分块排序)

yipeiwu_com7年前Python基础

复制代码 代码如下:

# -*- 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))

相关文章

基于python历史天气采集的分析

基于python历史天气采集的分析

分析历史天气的趋势。 先采集 代码: #-*- coding:utf-8 -*- import requests import random import MySQLdb im...

使用Python进行中文繁简转换的实现代码

中文繁体、简体的差异,在NPL中类似英文中的大小写,但又比大小写更为复杂,比如同样为繁体字,大陆、香港和台湾又不一样。先前写过一篇中文繁简转换的文章,感觉写的不太详细,今天就针对Pyth...

Python 自动登录淘宝并保存登录信息的方法

Python 自动登录淘宝并保存登录信息的方法

前段时间时间为大家讲解了如何使用requests库模拟登录淘宝,而今天我们将对该功能进行丰富。所以我们把之前的那个版本定为1.0,而今天修改的版本定为2.0。版本的迭代意味着功能的升级,...

Python使用Matplotlib实现雨点图动画效果的方法

Python使用Matplotlib实现雨点图动画效果的方法

本文实例讲述了Python使用Matplotlib实现雨点图动画效果的方法。分享给大家供大家参考,具体如下: 关键点 win10安装ffmpeg animation函数使用 update...

使用OpenCV实现仿射变换—缩放功能

使用OpenCV实现仿射变换—缩放功能

前面介绍怎么样实现平移的功能,接着下来演示缩放功能。比如在一个文档里插入一个图片,发现这个图片占用太大的面积了,要把它缩小,才放得下,与文字的比例才合适。这样的需求,就需要使用仿射变换的...