Python-排序-有哪些時間複雜度為O(n)的排序演算法？
人到中年，容易變得油膩，思想懶惰，身體就容易發胖。為了擺脫中年油膩，不如和我一起學習演算法來燒燒腦子，燃燒你的卡路里。
燒腦題目：如何在 O(n) 的時間複雜度內按年齡給 100 萬用戶信息排序？
帶著這個問題來學習下三個線性排序演算法。
前幾篇文章介紹了幾個常用的排序演算法：冒泡、選擇、插入、歸併、快速，他們的時間複雜度從 O(n^2) 到 O(nlogn)，其實還有時間複雜度為 O(n) 的排序演算法，他們分別是桶排序，計數排序，基數排序，因為這些排序演算法的時間複雜度是線性的，所以這類演算法也叫線性排序。
你可能會問了，為什麼這些時間複雜度低至 O(n) 的排序演算法會很少使用呢？ 那就是因為這些排序演算法對待排序的數據要求比較苛刻，這些演算法理解其來比較簡單，學習這類演算法重要的是掌握它們的適用場景。下面我給出每一種演算法的實現思路，Python程序實現和應用場景。
1、桶排序
桶排序，可以這樣去理解：想像你面前有 m 個桶，有一堆待排序的 n 個數據，可以將這 n 個數據先按次序劃分成 m 個區間，對應依次放入這 m 個桶裏，然後對每個桶內的數據進行排序，再依次從 1 到 m 個桶裏依次取出就得到有序的結果。
換成這樣描述會更容易理解。假如要對 100 個訂單的金額進行排序，訂單的金額都是整數，訂單金額從 1 到 100 不等，那麼可以將這 100 個訂單分成 10 個區間，放到 10 個桶中，1 至 10 元的放在 1 桶，11 至 20元的到 2 桶... 91 至 100 的放到第 10 個桶中，然後對每個桶內的數據進行快速排序，再依次從1 桶、2 桶、3 桶 、10 桶取出元素，就得到有序的訂單信息。
你可能會問了，假如桶的個數是 m，每個桶中的數據量平均 n/m, 這個時間複雜度明明是 m*(n/m)*(log(n/m)) = n log(n/m)，怎麼可能是 O(n) 呢 ？ 這個問題非常好，原因是這樣的，當桶的個數 m 接近與 n 時，log(n/m) 就是一個非常小的常數，在時間複雜度時常數是可以忽略的。比如極端情況下桶的個數和元素個數相等，即 n = m， 此時時間複雜度就可以認為是 O(n)。
編程思路
1、初始化桶的大小為K
2、獲取 n 個數據中的最大值 max，最小值 min
3、將數據放入到 n/K +1 個桶中，a[i] 放入哪個桶的規則為 (a[i]-min)/K
4、對 n/K 個桶分別進行快速排序並輸出。
演算法實現 Python 版
#encoding = utf-8
import random
from quick_sort import quick_sort
DEFAULT_BUCKET_SIZE = 5
def bucket_sort(data_list,bucket_size = DEFAULT_BUCKET_SIZE):
length = len(data_list)
min = max = data_list[0]
#尋找最小值和最大值
for i in range(0,length):
if data_list[i] < min:
min = data_list[i]
if data_list[i] > max:
max = data_list[i]
#定義多個桶並初始化
num_of_buckets = (max - min) // bucket_size +1
buckets = []
for i in range(num_of_buckets):
buckets.append([])
#將數據放入桶中
for i in range(0,length):
buckets[(data_list[i] - min)//bucket_size ].append(data_list[i])
#依次對桶內數據進行快速排序
data_list.clear()
for i in range(num_of_buckets):
print(f"第{i}個桶排序前的內容是{buckets[i]}")
quick_sort(buckets[i])
# print(f"第{i}個桶排序後的內容是{buckets[i]}")
for data in buckets[i]:
data_list.append(data)
if __name__ == "__main__":
data_list = [random.randint(0,15) for _ in range(0,15)]
print(data_list)
bucket_sort(data_list)
print(data_list)
執行結果如下所示：
[13, 7, 12, 7, 8, 14, 3, 10, 1, 13, 0, 0, 4, 3, 5]
第0個桶排序前的內容是[3, 1, 0, 0, 4, 3]
第1個桶排序前的內容是[7, 7, 8, 5]
第2個桶排序前的內容是[13, 12, 14, 10, 13]
[0, 0, 1, 3, 3, 4, 5, 7, 7, 8, 10, 12, 13, 13, 14]
這裡請注意：如果桶內的數據極不均勻，極端情況下，只有一個桶有數據，那麼桶排序的時間複雜度就退化為 O(nlogn)。因此桶排序適合對每個區間內分佈比較均勻的數據進行排序。
桶排序適用場景
桶排序適合外部排序，外部排序就是數據在內存之外，比如磁碟上，數據量比較大，無法一次性讀入內存。舉個例子，假如老闆給你一份 10 GB 大小的文件，是訂單的交易明細數據，要求你按訂單金額從大到小排序，而你的內存內有 4GB，實際可用內存只有 2 GB，那麼此時就是桶排序發揮作用的時候了。 1. 將文件逐行讀入內存（幾乎每個編程語言都可以），掃描並記錄最小值，最大值，假如最小值為 1 元，最大值為 10 萬元，且都為整數，不是整數也沒關係，可以先乘以 100 換成整數，排序後再除以 100 還原。
- 設置初始的桶大小為 1000，也就是說每 1000 元做一個分區，放在一個桶內，這樣就有 10萬/1000 = 100 個桶。再次逐行讀入文件，訂單金額在 1 到 1000 元的放在第 1 個桶裏，在 1001 到 2000 元的放第 2 個桶裏，依次類推，這裡的桶是個形象的比喻，其實就是對應磁碟上的文件，這裡的放，其實就是逐行寫入磁碟上的文件中，相當於將 10 GB的文件分隔成 100 個小文件。
- 如果訂單金額是均勻分佈的，那麼這 100 個小文件平均每個佔內存 100 MB。第一次分區後如果小文件均小於可用內存大小，那麼可以依次對這些小文件數據全部讀入內存進行快速排序，排序完再寫回磁碟，最後依次讀取這些小文件並輸出到一個大文件中，達到排序的效果。如果仍有小文件超過可用內在，那麼再對該文件再次分區，直到可用內存能容下為止。
2、計數排序
計數排序是桶排序的一種特殊情況，當待排序的元素的最大值為 K 時，就把數據劃分為 K 個桶。每個桶內的數據都是相等的，這樣就節省了桶內排序的時間。
典型的應用場景就是：高考分數排名。高考成績滿分 750 分，就設置 751 個桶，對應 0，1，...750 的分數，只需要將數百萬的考生按成績放在每個桶中，再依次從每個桶中輸出學生信息，就完成了排序。
那麼，為什麼叫計數排序呢？為方便描述，假如有 8 個考生，滿分為 5 分，他們的成績分別為 2，5，3，0，2，3，0，3。那麼就設計 6 個桶，簡單點,定義數組 B[6] 表示 6 個桶，每個桶存放該分數的考生個數，只需要遍歷一下考生成績，即可得到桶 B[6] = [2,0,2,3,0,1] ,B[3]=3 表示成績為 3 的考生有 3 個，而成績小於 3 的考生前面有 4 個，也就是說成績為 3 的考生，應該排列在有序數組的 5，6，7 三個位置，如何得到其他分數所在的位置呢？
首先對 B[6] 累計求和，得到新的 B[6] = [2,2,4,7,7,8]，B[3]=7 就表示小於等於 3 分的考生個數為 7 個。 根據 B[6] = [2,2,4,7,7,8] 和初始序列 2，5，3，0，2，3，0，3，我們可以得到有序序列 [ 0,0,2,2,3,3,3,5 ] 。這裡使用另外一個數組來計數的實現方式非常巧秒，如下所示：
#encoding=utf-8
#實現極客專欄 數據結構與演算法之美 第13節 線性排序中的計數排序演算法
def counting_sort(data_list):
length = len(data_list)
#定義桶
bucket = []
max = data_list[0]
for d in data_list:
if d > max:
max = d
#初始化
for i in range(max+1):
bucket.append(0)
#計數
for i in range(length):
bucket[data_list[i]] = bucket[data_list[i]] + 1
##累加
for i in range(1,max+1):
bucket[i] = bucket[i]+bucket[i-1]
#計數排序,定義結果數組並初始化
result = []
for i in range(length):
result.append(0)
#從尾至頭查找分數在result的插入位置，如果從頭到尾的話就不是穩定的排序演算法。
for i in range(length-1,-1,-1):
result[bucket[data_list[i]]-1] = data_list[i]
bucket[data_list[i]] = bucket[data_list[i]] -1
#將結果複製到原來的數組中，達到修改傳入數組的效果
for i in range(length):
data_list[i] = result[i]
if __name__ == "__main__":
data_list = [2,5,3,0,2,3,0,3]
print(data_list)
counting_sort(data_list)
print(data_list)
執行結果如下所示：
[2, 5, 3, 0, 2, 3, 0, 3]
[0, 0, 2, 2, 3, 3, 3, 5]
計數排序適用場景
計數排序只能用在數據範圍不大的場景中，如果數據範圍 k 比要排序的數據 n 大很多，就不適合用計數排序了。而且，計數排序只能給非負整數排序，如果要排序的數據是其他類型的，要將其在不改變相對大小的情況下，轉化為非負整數。
3、基數排序
我們再來看這樣一個排序問題。假設我們有 10 萬個手機號碼，希望將這 10 萬個手機號碼從小到大排序，你有什麼比較快速的排序方法呢？
如果直接用快排，時間複雜度是O(nlogn)，如果使用基數排序，時間複雜度為O(n)。
手機號碼這類數據有個特點：定長，只要前面某一位大小確定，後面的位就不需要在一一比較。因此我們可以藉助穩定的排序演算法，先按照最後一位來排序手機號碼，然後，再按照倒數第二位重新排序，以此類推，最後按照第一位重新排序。經過 11 次排序之後，手機號碼就都有序了。
根據每一位來排序，我們利用上述桶排序或者計數排序，它們的時間複雜度可以做到 O(n)。如果要排序的數據有 k 位，那我們就需要 k 次桶排序或者計數排序，總的時間複雜度是 O(k*n)。當 k 不大的時候，比如手機號碼排序的例子，k 最大就是 11，所以基數排序的時間複雜度就近似於 O(n)。
這裡給出我自己實現的代碼（python）
#encoding=utf-8
import random
class phone_num(object):
num = ""
def __init__(self,num=""):
self.num = num
def get_bit(self,bit):
return int(self.num[bit-1:bit])
def __str__(self):
return self.num
def __repr__(self):
return self.num
def radix_sort(data_list):
radix = 11
##藉助穩定排序演算法從尾至頭排序 radix 次
for i in range(radix,0,-1):
counting_sort(data_list,i)
#改寫的計數排序，方便基數排序調用,radix 指示是待排序數據的哪一位
def counting_sort(data_list,radix):
length = len(data_list)
#定義桶
bucket = []
max = data_list[0].get_bit(radix)
for i in range(length):
if data_list[i].get_bit(radix) > max:
max = data_list[i].get_bit(radix)
#初始化
for i in range(max+1):
bucket.append(0)
#計數
for i in range(length):
bucket[data_list[i].get_bit(radix)] = bucket[data_list[i].get_bit(radix)] + 1
##累加
for i in range(1,max+1):
bucket[i] = bucket[i]+bucket[i-1]
#計數排序,定義結果數組並初始化
result = []
for i in range(length):
result.append(0)
#從尾至頭查找分數在result的插入位置，如果從頭到尾的話就不是穩定的排序演算法。
for i in range(length-1,-1,-1):
result[bucket[data_list[i].get_bit(radix)]-1] = data_list[i]
bucket[data_list[i].get_bit(radix)] = bucket[data_list[i].get_bit(radix)] -1
#將結果複製到原來的數組中，達到修改傳入數組的效果
for i in range(length):
data_list[i] = result[i]
def create_phone_num():
prelist = ["130", "131", "132", "133", "134", "135", "136", "137", "138", "139", "147", "150", "151", "152",
"153", "155", "156", "157", "158", "159", "186", "187", "188"]
randomPre = random.choice(prelist)
Number = "".join(random.choice("0123456789") for i in range(8))
phoneNum = randomPre +Number
return phoneNum
if __name__ == "__main__":
data_list = [phone_num(create_phone_num()) for _ in range(10)]
print("排序前")
for i in data_list:
print(i)
radix_sort(data_list)
print("排序後")
for i in data_list:
print(i)
代碼的最開始處，先定義電話號碼的類，並實現返回某一位數值的函數get_bit()，這樣在計數排序函數中根據某一位來排序了，也可以直接使用字元串數組，只不過那樣寫的話代碼的可讀性不好。代碼還修改了計數排序函數，使之適用於基數排序。在排序前隨機的生成了 10 個手機號碼，執行結果如下所示：
排序前
13834120744
13512786443
13243514461
13602161246
18691910549
14759154249
13080747777
13890979666
13995122272
15248505554
排序後
13080747777
13243514461
13512786443
13602161246
13834120744
13890979666
13995122272
14759154249
15248505554
18691910549
可以看出，基數排序調用了 11 次計數排序對手機號碼進行排序，每次計數排序的時間複雜度為 O(n)，因此使用基數排序對類似這樣的數據排序的時間複雜度也為 O(n)。
基數排序的適用場景
基數排序對要排序的數據是有要求的，需要可以分割出獨立的「位」來比較，而且位之間有遞進的關係，如果 a 數據的高位比 b 數據大，那剩下的低位就不用比較了。除此之外，每一位的數據範圍不能太大，要可以用線性排序演算法來排序，否則，基數排序的時間複雜度就無法做到 O(n) 了。
在實際應用中，字元串之間排序就可以使用基數排序，如果待排序的字元串位數不一致，可以通過在字元串尾部補 0 來使他們位數一致，這與小數轉整數後再排序的道理是一致的。
解答開篇
到這裡，我想你已經知道如何給根據年齡給 100 萬用戶排序了，就類似按照成績給 100 萬考生排序。我們假設年齡的範圍最小 1 歲，最大不超過 120 歲。我們可以遍歷這 100 萬用戶，根據年齡將其劃分到這 120 個桶裏，然後依次順序遍歷這 120 個桶中的元素。這樣就得到了按照年齡排序的 100 萬用戶數據。
系列文章：
為什麼要學習數據結構與演算法（文末福利）
Python-排序-冒泡排序-優化
Python-排序-選擇排序-優化
Python 排序-插入排序-優化
Python-排序-歸併排序-優化
Python|演算法|快速排序|如何在O(n)查找第K大元素
（完）
關注個人微信公眾號 somenzz，獲得原創技術乾貨，和你一起學習。
推薦閱讀：
