一疙挺、桶排序
1. 算法思想：桶排序是將待排序序列中處于相同值域的元素存入同一個桶中扛邑，即將一個數(shù)據(jù)表分割成許多桶，然后每個桶中的元素各自排序铐然。它采用分治策略蔬崩，是一種分布式的排序方法。
2. 算法過程：
（1）根據(jù)待排序序列中最大元素和最小元素的差值和映射規(guī)則搀暑，確定申請的桶個數(shù)沥阳；
（2）遍歷待排序序列，將每一個元素存儲到對應(yīng)的桶中自点；
（3）分別對每一個桶中元素進行排序桐罕，并存儲到原序列中，獲得一個已排序序列桂敛。
3. 圖例分析：
待排序序列為：[29, 25, 3, 49, 9, 37, 21, 43]功炮，以間隔大小10來區(qū)分不同值域，待申請桶的個數(shù)為5术唬。
4. 代碼演示：
def bucket_sort(a:list)->list:
??? step = 10 #以間隔大小10來區(qū)分不同值域
??? maximum, minimum = max(a), min(a)
??? buckets = [[] for i in range(maximum //step - minimum // step + 1)]? #桶的數(shù)量
??? for i in a:?#將處于相同值域（即index相同）的元素存入同一個桶中
??????? index = i // step - minimum // step
??????? buckets[index].append(i)
??? a.clear()
??? for b in buckets:
??????? b.sort()? #對每一個桶中元素進行排序
??????? a.extend(b)? #將各個桶的元素按順序存儲到原序列中
??? return a
二薪伏、簡單計數(shù)排序
1. 算法思想：若待排序序列的元素均為非負整數(shù)，且最大值為maximum粗仓，則分配maximum+1個桶嫁怀，每個桶的編號（下標）就等于待排序元素的值，每個桶的元素值就是存入桶中的待排序元素個數(shù)借浊。為了描述方便塘淑，我們將桶序列稱為統(tǒng)計數(shù)組。
2. 算法過程：
（1）根據(jù)待排序序列中最大元素值蚂斤，確定申請的桶個數(shù)存捺，并將桶全部清空；
（2）統(tǒng)計待排序序列中每個值為i的元素出現(xiàn)的次數(shù)橡淆，存入編號為i的桶召噩；
（3）依次把數(shù)據(jù)從桶里倒出來母赵，存儲到原序列中，獲得一個已排序序列具滴。
3. 圖例分析：
待排序序列為：[3, 5, 1, 0, 3, 0]凹嘲，待申請桶的個數(shù)為5+1=6。
4. 代碼演示：
def counting_sort(a:list)->list:
? ? n = max(a) + 1
? ? c = [0] * n #將所有的桶均清空
? ? for num in a: #將值為num的元素存入下標為num桶中
? ? ? ? c[num] += 1
? ? a.clear()
? ? for i in range(n): #依次把數(shù)據(jù)從桶里倒出來
? ? ? ? a.extend([i] * c[i])? #依次存儲所有值為i的元素
return a
三构韵、優(yōu)化計數(shù)排序
? ? ? ? 簡單計數(shù)排序有兩個缺陷周蹭，一是根據(jù)最大元素值來確定桶的數(shù)量，完全不考慮最小元素值疲恢，當最小值也很大時會造成空間浪費凶朗。二是統(tǒng)計數(shù)組中的桶相當于一個“棧”數(shù)據(jù)結(jié)構(gòu)显拳，具有“先進后出”特征棚愤，如果我們直接按順序把數(shù)據(jù)從桶里倒出來，存儲到原數(shù)組a中杂数，就會改變數(shù)組a中等值元素的相對位置宛畦，造成“不穩(wěn)定排序”的后果。
? ? ? ? 下面我們對這兩個缺陷進行改進揍移。
1. 算法思想：對于待排序序列中的每一個元素x次和，確定該序列中值小于x的元素的個數(shù)。一旦有了這個信息那伐，就可以將x直接存放到最終的輸出序列的正確位置上踏施。它相當于桶排序中step=1的一個特例，因此它需要創(chuàng)建桶的數(shù)量為maximum - minimum + 1罕邀，每個桶的編號（下標）就等于待排序元素的值畅形，每個桶的元素值就是存入桶中的待排序元素個數(shù)。為了描述方便诉探，我們將桶序列稱為統(tǒng)計數(shù)組束亏。
2. 算法過程：
（1）根據(jù)待排序序列中最大元素和最小元素的差值，確定申請桶的個數(shù)阵具，并將桶全部清空；
（2）統(tǒng)計待排序序列中每個值為i的元素出現(xiàn)的次數(shù)定铜，存入編號為i的桶阳液；
（3）依次求出每個桶的前綴和；
（4）反向填充目標數(shù)組揣炕，每放一個元素就將對應(yīng)桶的元素值減一帘皿。
3. 圖例分析：
待排序序列為：[3, 5, 1, 0, 3, 0]，待申請桶的個數(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的元素存入下標為i桶中
??????? c[i-minimum] += 1
??? for i in range(1, len(c)): #依次求出每個桶的前綴和
??????? c[i] += c[i-1]
??? b = [0] * len(a)#設(shè)置目標數(shù)組
??? for i in a[::-1]: #反向填充目標數(shù)組
??????? c[i-minimum] -= 1
??????? b[c[i-minimum]] = i
? ? return b
四鹰溜、基數(shù)排序
1. 算法思想：基數(shù)排序又稱為“桶子法”虽填，從低位開始將待排序的數(shù)按照這一位的值放到相應(yīng)的編號為0~9的桶中。等到低位排完得到一個子序列曹动，再將這個序列按照次低位的大小進入相應(yīng)的桶中斋日，一直排到最高位為止，數(shù)組排序完成墓陈。
2.? 算法過程：
（1）將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長度恶守，數(shù)位較短的數(shù)前面補零；
（2）從最低位開始贡必，依次進行一次桶排序兔港；
（3）從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。
3. 圖例分析：
待排序序列為：[53, 3, 542, 748, 14, 214, 154, 63, 616]仔拟，數(shù)位長度為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)): #依次求出每個桶的前綴和
??????????? c[i] += c[i-1]
??????? t = a[::-1] #將原數(shù)組逆序復制到臨時數(shù)組t
??????? for i in t: #反向填充目標數(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
