本文首先舉例闡述了兩種排序方法的操作步驟，然后列出了用python進行的實現過程，最后對桶式排序方法的優劣進行了簡單總結。
一、桶排序：
排序一個數組[5,3,6,1,2,7,5,10]
值都在1-10之間，建立10個桶：
[0 0 0 0 0 0 0 0 0 0] 桶
[1 2 3 4 5 6 7 8 9 10] 桶代表的值
遍歷數組，第一個數字5，第五個桶加1
|
1
|
[0 0 0 0 1 0 0 0 0 0] |
第二個數字3，第三個桶加1
|
1
|
[0 0 1 0 1 0 0 0 0 0] |
遍歷后
|
1
|
[1 1 1 0 2 1 1 0 0 1] |
輸出
|
1
|
[1 2 3 5 5 6 7 10] |
代碼：
|
1
2
3
4
5
6
7
8
9
|
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 |
二、基數排序：
例如，對如下數據序列進行排序。
|
1
|
192,221,12,23 |
可以觀察到它的每個數據至多只有3位，因此可以將每個數據拆分成3個關鍵字：百位（高位）、十位、個位（低位）。如果按照習慣思維，會先比較百位，百位大的數據大，百位相同的再比較十位，十位大的數據大；最后再比較個位。基數排序方法對任一子關鍵字排序時必須借助于另一種排序方法，而且這種排序方法必須是穩定的。對于多關鍵字拆分出來的子關鍵字，它們一定位于0-9這個可枚舉的范圍內，這個范圍不大，因此用桶式排序效率非常好。
代碼：
|
1
2
3
4
5
6
7
8
|
from random import randintdef radix_sort(lis,d): for i in xrange(d):#d輪排序 s = [[] for k in xrange(10)]#因為每一位數字都是0~9，故建立10個桶 for j in lis: s[j/(10**i)%10].append(i) li = [a for b in s for a in b] return li |
對數組中的元素按照從低位到高位排序，對于[192,221,12,23]第一輪按照個位數字相同的放在一組，是s[1] =[221],s[2]=[192,12],s[3]=23,第二輪按照十位數字進行排序，s[1]=[12],s[2]=[221,23],s[9]=[192],第三輪按照百位數字進行排序，s[0]=[12,23],s[1]=[192],s[2]=[221]
總結：
桶排序與基數排序常作為桶式排序出現，基數排序進行了多輪的桶排序。桶式排序不再是一種基于比較的排序方法，它是一種比較巧妙的排序方式，但這種排序方式需要待排序的序列滿足以下兩個特征：待排序列所有的值處于一個可枚舉的范圍之類；待排序列所在的這個可枚舉的范圍不應該太大，否則排序開銷太大。可以用于學生成績的排序，因為在若干學生中成績的范圍僅在100以內。
桶式排序的空間開銷較大，它需要兩個數組，第1個buckets數組用于記錄“落入”各桶中元素的個數，進而保存各元素在有序序列中的位置，第2個數組用于緩存待排數據。它只能排整形數組。而且當k較大，而數組長度n較小，即k>>n時，輔助數組C[k+1]的空間消耗較大。
以上這篇基于python進行桶排序與基數排序的總結就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/iqqiqqiqqiqq/article/details/54837711
