python與桶排序

1. 問題提出:

將以下數據:

6, 8, 2, 3, 4, 0, 9, 1, 5,1

按從小到達排列。

2. 桶排序原理:

桶排序也叫計數排序,簡單來說,就是將數據集里面所有元素按順序列舉出來,然后統計元素出現的次數。最后按順序輸出數據集里面的元素。

3.?排序過程如下:

初始化桶的大小

把數據集里面每一個元素當作一個桶,由上面問題看出,原始數據范圍在0--9之間,因此我就需要有10個桶,如下圖

735729-20160729172946544-869311964

第一行為初始化計數為0,第二行為各個元素。

計數

接下來讀入第一原始數據為6,則在下標為6的桶中增加1,如下圖:

735729-20160729173343606-490156583

再讀入下一個原始數據為8,則在下標為8的桶中增加1,如下圖:

735729-20160729173515559-1482838386

以此類推,最后遍歷完所有原始數據時,10個桶的計數如下圖:

735729-20160729173839278-1494572085

輸出數據

在完成原始數據的遍歷計數后,接下來遍歷各個桶,輸出數據:

元素0計數為1,則輸出0,

元素1計數為2,則輸出1 1,

元素2計數為1,則輸出2,

元素3計數為1,則輸出3,

元素4計數為1,則輸出4,

元素5計數為1,則輸出5,

元素6計數為1,則輸出6,

元素7計數為0,則不輸出元素,

元素8計數為1,則輸出8,

元素9計數為1,則輸出9,

最后結果輸出為:0, 1, 1, 2, 3, 4, 5, 6, 8, 9

4. 代碼實現

由上述原理可以看出,桶排序需要以下三個步驟:

  • 1.申請一個包含所有元素的數組,并初始化。
  • 2.遍歷原始數據,并計數。
  • 3.遍歷計數完成后的各個數組元素,輸出數據。

以下是python代碼的實現:

5. 總結:

  • 1.桶排序的優點就是特別快,真的是特別快!特別快!特別塊!
  • 2.缺點就是特別耗資源,如果數據取值的范圍是0---1010, 就要申請一個大小為1010的數組,想想這得多耗內存空間。闊怕!
  • 3.我上面寫的程序也只是一個演示性的,漏洞挺多,目前只能排序大于零的整數。

原文鏈接:http://www.cnblogs.com/king-ding/p/5719359.html

任 江風

發表評論

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: