一、桶排序
1. 算法思想：桶排序是將待排序序列中處于相同值域的元素存入同一個(gè)桶中，即將一個(gè)數(shù)據(jù)表分割成許多桶，然后每個(gè)桶中的元素各自排序。它采用分治策略，是一種分布式的排序方法。
2. 算法過(guò)程：
（1）根據(jù)待排序序列中最大元素和最小元素的差值和映射規(guī)則，確定申請(qǐng)的桶個(gè)數(shù)；
（2）遍歷待排序序列，將每一個(gè)元素存儲(chǔ)到對(duì)應(yīng)的桶中；
（3）分別對(duì)每一個(gè)桶中元素進(jìn)行排序，并存儲(chǔ)到原序列中，獲得一個(gè)已排序序列。
3. 圖例分析：
待排序序列為：[29, 25, 3, 49, 9, 37, 21, 43]，以間隔大小10來(lái)區(qū)分不同值域，待申請(qǐng)桶的個(gè)數(shù)為5。
4. 代碼演示：
def bucket_sort(a:list)->list:
??? step = 10 #以間隔大小10來(lái)區(qū)分不同值域
??? maximum, minimum = max(a), min(a)
??? buckets = [[] for i in range(maximum //step - minimum // step + 1)]? #桶的數(shù)量
??? for i in a:?#將處于相同值域（即index相同）的元素存入同一個(gè)桶中
??????? index = i // step - minimum // step
??????? buckets[index].append(i)
??? a.clear()
??? for b in buckets:
??????? b.sort()? #對(duì)每一個(gè)桶中元素進(jìn)行排序
??????? a.extend(b)? #將各個(gè)桶的元素按順序存儲(chǔ)到原序列中
??? return a
二、簡(jiǎn)單計(jì)數(shù)排序
1. 算法思想：若待排序序列的元素均為非負(fù)整數(shù)，且最大值為maximum，則分配maximum+1個(gè)桶，每個(gè)桶的編號(hào)（下標(biāo)）就等于待排序元素的值，每個(gè)桶的元素值就是存入桶中的待排序元素個(gè)數(shù)。為了描述方便，我們將桶序列稱為統(tǒng)計(jì)數(shù)組。
2. 算法過(guò)程：
（1）根據(jù)待排序序列中最大元素值，確定申請(qǐng)的桶個(gè)數(shù)，并將桶全部清空；
（2）統(tǒng)計(jì)待排序序列中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入編號(hào)為i的桶；
（3）依次把數(shù)據(jù)從桶里倒出來(lái)，存儲(chǔ)到原序列中，獲得一個(gè)已排序序列。
3. 圖例分析：
待排序序列為：[3, 5, 1, 0, 3, 0]，待申請(qǐng)桶的個(gè)數(shù)為5+1=6。
4. 代碼演示：
def counting_sort(a:list)->list:
? ? n = max(a) + 1
? ? c = [0] * n #將所有的桶均清空
? ? for num in a: #將值為num的元素存入下標(biāo)為num桶中
? ? ? ? c[num] += 1
? ? a.clear()
? ? for i in range(n): #依次把數(shù)據(jù)從桶里倒出來(lái)
? ? ? ? a.extend([i] * c[i])? #依次存儲(chǔ)所有值為i的元素
return a
三、優(yōu)化計(jì)數(shù)排序
? ? ? ? 簡(jiǎn)單計(jì)數(shù)排序有兩個(gè)缺陷，一是根據(jù)最大元素值來(lái)確定桶的數(shù)量，完全不考慮最小元素值，當(dāng)最小值也很大時(shí)會(huì)造成空間浪費(fèi)。二是統(tǒng)計(jì)數(shù)組中的桶相當(dāng)于一個(gè)“棧”數(shù)據(jù)結(jié)構(gòu)，具有“先進(jìn)后出”特征，如果我們直接按順序把數(shù)據(jù)從桶里倒出來(lái)，存儲(chǔ)到原數(shù)組a中，就會(huì)改變數(shù)組a中等值元素的相對(duì)位置，造成“不穩(wěn)定排序”的后果。
? ? ? ? 下面我們對(duì)這兩個(gè)缺陷進(jìn)行改進(jìn)。
1. 算法思想：對(duì)于待排序序列中的每一個(gè)元素x，確定該序列中值小于x的元素的個(gè)數(shù)。一旦有了這個(gè)信息，就可以將x直接存放到最終的輸出序列的正確位置上。它相當(dāng)于桶排序中step=1的一個(gè)特例，因此它需要?jiǎng)?chuàng)建桶的數(shù)量為maximum - minimum + 1，每個(gè)桶的編號(hào)（下標(biāo)）就等于待排序元素的值，每個(gè)桶的元素值就是存入桶中的待排序元素個(gè)數(shù)。為了描述方便，我們將桶序列稱為統(tǒng)計(jì)數(shù)組。
2. 算法過(guò)程：
（1）根據(jù)待排序序列中最大元素和最小元素的差值，確定申請(qǐng)桶的個(gè)數(shù)，并將桶全部清空；
（2）統(tǒng)計(jì)待排序序列中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入編號(hào)為i的桶；
（3）依次求出每個(gè)桶的前綴和；
（4）反向填充目標(biāo)數(shù)組，每放一個(gè)元素就將對(duì)應(yīng)桶的元素值減一。
3. 圖例分析：
待排序序列為：[3, 5, 1, 0, 3, 0]，待申請(qǐng)桶的個(gè)數(shù)為5-0+1=6。
4. 代碼演示：
def counting_sort2(a:list)->list:
??? maximum, minimum = max(a), min(a)
??? c = [0] * (maximum - minimum + 1)? #將所有的桶均清空
??? for i in a: #將值為i的元素存入下標(biāo)為i桶中
??????? c[i-minimum] += 1
??? for i in range(1, len(c)): #依次求出每個(gè)桶的前綴和
??????? c[i] += c[i-1]
??? b = [0] * len(a)#設(shè)置目標(biāo)數(shù)組
??? for i in a[::-1]: #反向填充目標(biāo)數(shù)組
??????? c[i-minimum] -= 1
??????? b[c[i-minimum]] = i
? ? return b
四、基數(shù)排序
1. 算法思想：基數(shù)排序又稱為“桶子法”，從低位開(kāi)始將待排序的數(shù)按照這一位的值放到相應(yīng)的編號(hào)為0~9的桶中。等到低位排完得到一個(gè)子序列，再將這個(gè)序列按照次低位的大小進(jìn)入相應(yīng)的桶中，一直排到最高位為止，數(shù)組排序完成。
2.? 算法過(guò)程：
（1）將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零；
（2）從最低位開(kāi)始，依次進(jìn)行一次桶排序；
（3）從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列。
3. 圖例分析：
待排序序列為：[53, 3, 542, 748, 14, 214, 154, 63, 616]，數(shù)位長(zhǎng)度為3。
4. 代碼演示：
def radix_sort(a:list)->list:
??? def cout_sort(a:list, exp:int):
??????? c = [0] * 10
??????? for i in a:
??????????? c[(i//exp)%10] += 1
??????? for i in range(1, len(c)): #依次求出每個(gè)桶的前綴和
??????????? c[i] += c[i-1]
??????? t = a[::-1] #將原數(shù)組逆序復(fù)制到臨時(shí)數(shù)組t
??????? for i in t: #反向填充目標(biāo)數(shù)組
??????????? c[(i//exp)%10] -= 1
??????????? a[c[(i//exp)%10]] = i
??? exp, m = 1, max(a)
??? while m // exp > 0:
??????? cout_sort(a, exp)
??????? exp *= 10
??? return a
