快捷導(dǎo)航

python算法學(xué)習(xí)之桶排序算法實(shí)例(分塊排序)

更新時(shí)間：2013年12月18日 10:02:16 作者：

本代碼介紹了python算法學(xué)習(xí)中的桶排序算法實(shí)例，大家參考使用吧

# -*- 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個(gè)數(shù)分布到各個(gè)桶中
    4 for i ← 0 to n-1
    5    do sort list B[i] with insertion sort // 對(duì)各個(gè)桶中的數(shù)進(jìn)行排序
    6 concatenate the lists B[0],B[1],...,B[n-1] together in order // 依次串聯(lián)各桶中的元素

    桶排序假設(shè)輸入由一個(gè)隨機(jī)過(guò)程產(chǎn)生，該過(guò)程將元素均勻地分布在區(qū)間[0,1)上。
    """
    n = len(A)
    buckets = [[] for _ in xrange(n)] # n個(gè)空桶
    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)文章

解決tensorflow測(cè)試模型時(shí)NotFoundError錯(cuò)誤的問(wèn)題
今天小編就為大家分享一篇解決tensorflow測(cè)試模型時(shí)NotFoundError錯(cuò)誤的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2018-07-07
Python自動(dòng)化中三種等待時(shí)間方式
這篇文章主要介紹了Python自動(dòng)化中三種等待時(shí)間方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2024-02-02
Python線性分類(lèi)介紹
這篇文章主要介紹了Python線性分類(lèi)，線性分類(lèi)指在機(jī)器學(xué)習(xí)領(lǐng)域，分類(lèi)的目標(biāo)是指將具有相似特征的對(duì)象聚集。而一個(gè)線性分類(lèi)器則透過(guò)特征的線性組合來(lái)做出分類(lèi)決定，以達(dá)到此種目的。對(duì)象的特征通常被描述為特征值，而在向量中則描述為特征向量,需要的朋友可以參考下
2022-02-02
基于Python實(shí)現(xiàn)智能停車(chē)場(chǎng)車(chē)牌識(shí)別計(jì)費(fèi)系統(tǒng)
這篇文章主要為大家介紹了如何利用Python實(shí)現(xiàn)一個(gè)智能停車(chē)場(chǎng)車(chē)牌識(shí)別計(jì)費(fèi)系統(tǒng)，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以動(dòng)手嘗試一下
2022-04-04
Python使用Matplotlib模塊時(shí)坐標(biāo)軸標(biāo)題中文及各種特殊符號(hào)顯示方法
這篇文章主要介紹了Python使用Matplotlib模塊時(shí)坐標(biāo)軸標(biāo)題中文及各種特殊符號(hào)顯示方法,結(jié)合具體實(shí)例分析了Python使用Matplotlib模塊過(guò)程中針對(duì)中文及特殊符號(hào)的顯示方法,需要的朋友可以參考下
2018-05-05
wxpython 學(xué)習(xí)筆記第一天
wxPython是Python編程語(yǔ)言的一個(gè)GUI工具箱。他使得Python程序員能夠輕松的創(chuàng)建具有健壯、功能強(qiáng)大的圖形用戶(hù)界面的程序。
2009-02-02
對(duì)django中foreignkey的簡(jiǎn)單使用詳解
今天小編就為大家分享一篇對(duì)django中foreignkey的簡(jiǎn)單使用詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2019-07-07
Python3 數(shù)據(jù)結(jié)構(gòu)示例詳解
本文介紹了Python中的四種基本數(shù)據(jù)結(jié)構(gòu)——列表、元組、集合和字典,以及如何根據(jù)具體需求選擇合適的數(shù)據(jù)結(jié)構(gòu),文章還展示了如何使用這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行基本操作,并提供了示例代碼,感興趣的朋友跟隨小編一起看看吧
2025-11-11
Python self參數(shù)詳細(xì)介紹
事實(shí)上，Python只是規(guī)定，無(wú)論是構(gòu)造方法還是實(shí)例方法，最少要包含一個(gè)參數(shù)，并沒(méi)有規(guī)定該參數(shù)的具體名稱(chēng)。之所以將其命名為self，只是程序員之間約定俗成的一種習(xí)慣，遵守這個(gè)約定，可以使我們編寫(xiě)的代碼具有更好的可讀性
2023-01-01
python實(shí)現(xiàn)將漢字保存成文本的方法
今天小編就為大家分享一篇python實(shí)現(xiàn)將漢字保存成文本的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2018-11-11