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

赞 (0)

相关推荐

  • python 实现插入排序算法

    复制代码 代码如下: #!/usr/bin/python def insert_sort(array): for i in range(1, len(array)): key = array[i] j = i - 1 while j >= 0 and key < array[j]: array[j + 1] = array[j] j-=1 array[j + 1] = key if __name__ == "__main__": array = [2, 4, 32, 64,

  • Python实现的几个常用排序算法实例

    前段时间为准备百度面试恶补的东西,虽然最后还是被刷了,还是把那几天的"战利品"放点上来,算法一直是自己比较薄弱的地方,以后还要更加努力啊. 下面用Python实现了几个常用的排序,如快速排序,选择排序,以及二路并归排序等等. 复制代码 代码如下: #encoding=utf-8import randomfrom copy import copy def directInsertSort(seq): """ 直接插入排序 """

  • python冒泡排序算法的实现代码

    1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是已经好了的. 2.python冒泡排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def bubble(l):    flag = True    for i in range(len(l)-1, 0, -1):        if flag:             flag = False

  • python实现八大排序算法（2）

    python实现八大排序算法（2）

    本文接上一篇博客python实现的八大排序算法part1,将继续使用python实现八大排序算法中的剩余四个:快速排序.堆排序.归并排序.基数排序 5.快速排序 快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的. 算法思想: 已知一组无序数据a[1].a[2].--a[n],需将其按升序排列.首先任取数据a[x]作为基准.比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数

  • python 实现归并排序算法

    理论不多说: 复制代码 代码如下: #!/usr/bin/python import sys def merge(array, q, p, r): left_array = array[q:p+1] right_array = array[p+1:r+1] left_array_num = len(left_array) right_array_num = len(right_array) i, j , k= [0, 0, q] while i < left_array_num and j <

  • python实现的各种排序算法代码

    复制代码 代码如下: # -*- coding: utf-8 -*-# 测试各种排序算法# link:www.jb51.net# date:2013/2/2 #选择排序def select_sort(sort_array):    for i, elem in enumerate(sort_array):        for j, elem in enumerate(sort_array[i:]):            if sort_array[i] > sort_array[j + i]

  • 八大排序算法的Python实现

    Python实现八大排序算法,具体内容如下 1.插入排序 描述 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法.插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 代码实现 def inser

  • python插入排序算法的实现代码

    1.算法:设有一组关键字{ K 1 , K 2 ,-, K n }:排序开始就认为 K 1 是一个有序序列:让 K 2 插入上述表长为 1 的有序序列,使之成为一个表长为 2 的有序序列:然后让 K 3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列:依次类推,最后让 K n 插入上述表长为 n-1 的有序序列,得一个表长为 n 的有序序列. 2.python插入排序代码 复制代码 代码如下: def insertion_sort(list2):    for i in ra

  • python选择排序算法的实现代码

    1.算法:对于一组关键字{K1,K2,-,Kn}, 首先从K1,K2,-,Kn中选择最小值,假如它是 Kz,则将Kz与 K1对换:然后从K2,K3,- ,Kn中选择最小值 Kz,再将Kz与K2对换.如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1.Kn中选择最小值 Kz将Kz与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成. 2.python 选择排序代码: 复制代码 代码如下: def selection_sort(list2):    for i in

  • python 实现堆排序算法代码

    复制代码 代码如下: #!/usr/bin/python import sys def left_child(node): return node * 2 + 1 def right_child(node): return node * 2 + 2 def parent(node): if (node % 2): return (i - 1) / 2 else: return (i - 2) / 2 def max_heapify(array, i, heap_size): l = left_c

随机推荐