基于python進(jìn)行桶排序與基數(shù)排序的總結(jié)

更新時(shí)間：2018年05月29日 09:08:30 作者：笛在月明

今天小編就為大家分享一篇基于python進(jìn)行桶排序與基數(shù)排序的總結(jié)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

本文首先舉例闡述了兩種排序方法的操作步驟，然后列出了用python進(jìn)行的實(shí)現(xiàn)過(guò)程，最后對(duì)桶式排序方法的優(yōu)劣進(jìn)行了簡(jiǎn)單總結(jié)。

一、桶排序：

排序一個(gè)數(shù)組[5,3,6,1,2,7,5,10]

值都在1-10之間，建立10個(gè)桶：

[0 0 0 0 0 0 0 0 0 0] 桶

[1 2 3 4 5 6 7 8 9 10] 桶代表的值

遍歷數(shù)組，第一個(gè)數(shù)字5，第五個(gè)桶加1

[0 0 0 0 1 0 0 0 0 0]

第二個(gè)數(shù)字3，第三個(gè)桶加1

[0 0 1 0 1 0 0 0 0 0]

遍歷后

[1 1 1 0 2 1 1 0 0 1]

輸出

[1 2 3 5 5 6 7 10]

代碼：

def bucket_sort(lst):
 buckets = [0] * ((max(lst) - min(lst))+1)
 for i in range(len(lst)):
  buckets[lst[i]-min(lst)] += 1
 res=[]
 for i in range(len(buckets)):
  if buckets[i] != 0:
   res += [i+min(lst)]*buckets[i]
 return res

二、基數(shù)排序：

例如，對(duì)如下數(shù)據(jù)序列進(jìn)行排序。

192,221,12,23

可以觀察到它的每個(gè)數(shù)據(jù)至多只有3位，因此可以將每個(gè)數(shù)據(jù)拆分成3個(gè)關(guān)鍵字：百位（高位）、十位、個(gè)位（低位）。如果按照習(xí)慣思維，會(huì)先比較百位，百位大的數(shù)據(jù)大，百位相同的再比較十位，十位大的數(shù)據(jù)大；最后再比較個(gè)位。基數(shù)排序方法對(duì)任一子關(guān)鍵字排序時(shí)必須借助于另一種排序方法，而且這種排序方法必須是穩(wěn)定的。對(duì)于多關(guān)鍵字拆分出來(lái)的子關(guān)鍵字，它們一定位于0-9這個(gè)可枚舉的范圍內(nèi)，這個(gè)范圍不大，因此用桶式排序效率非常好。

代碼：

from random import randint
def radix_sort(lis,d):
 for i in xrange(d):#d輪排序
  s = [[] for k in xrange(10)]#因?yàn)槊恳晃粩?shù)字都是0~9，故建立10個(gè)桶
  for j in lis:
   s[j/(10**i)%10].append(i)
  li = [a for b in s for a in b]
 return li

對(duì)數(shù)組中的元素按照從低位到高位排序，對(duì)于[192,221,12,23]第一輪按照個(gè)位數(shù)字相同的放在一組，是s[1] =[221],s[2]=[192,12],s[3]=23,第二輪按照十位數(shù)字進(jìn)行排序，s[1]=[12],s[2]=[221,23],s[9]=[192],第三輪按照百位數(shù)字進(jìn)行排序，s[0]=[12,23],s[1]=[192],s[2]=[221]

總結(jié)：

桶排序與基數(shù)排序常作為桶式排序出現(xiàn)，基數(shù)排序進(jìn)行了多輪的桶排序。桶式排序不再是一種基于比較的排序方法，它是一種比較巧妙的排序方式，但這種排序方式需要待排序的序列滿足以下兩個(gè)特征：待排序列所有的值處于一個(gè)可枚舉的范圍之類；待排序列所在的這個(gè)可枚舉的范圍不應(yīng)該太大，否則排序開(kāi)銷太大?？梢杂糜趯W(xué)生成績(jī)的排序，因?yàn)樵谌舾蓪W(xué)生中成績(jī)的范圍僅在100以內(nèi)。

桶式排序的空間開(kāi)銷較大，它需要兩個(gè)數(shù)組，第1個(gè)buckets數(shù)組用于記錄“落入”各桶中元素的個(gè)數(shù)，進(jìn)而保存各元素在有序序列中的位置，第2個(gè)數(shù)組用于緩存待排數(shù)據(jù)。它只能排整形數(shù)組。而且當(dāng)k較大，而數(shù)組長(zhǎng)度n較小，即k>>n時(shí)，輔助數(shù)組C[k+1]的空間消耗較大。

以上這篇基于python進(jìn)行桶排序與基數(shù)排序的總結(jié)就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: