本文將介紹希爾排序、歸并排序、基數(shù)排序（桶排序）。
網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了大慶免費(fèi)建站歡迎大家使用！
在所有的排序算法中，冒泡、插入、選擇屬于相類似的排序算法，這類算法的共同點(diǎn)：通過不停地比較，再使用交換邏輯重新確定數(shù)據(jù)的位置。
希爾、歸并、快速排序算法也可歸為同一類，它們的共同點(diǎn)都是建立在分治思想之上。把大問題分拆成小問題，解決所有小問題后，再合并每一個(gè)小問題的結(jié)果，最終得到對原始問題的解答。
通俗而言：化整為零，各個(gè)擊破。
分治算法很有哲學(xué)蘊(yùn)味：老祖宗所言 合久必分，分久必合，分開地目的是為了更好的合并。
分治算法的求解流程：
分解問題：將一個(gè)需要解決的、看起很復(fù)雜 原始問題 分拆成很多獨(dú)立的子問題，子問題與原始問題有相似性。
如：一個(gè)數(shù)列的局部（小問題）有序，必然會(huì)讓數(shù)列最終（原始問題）有序。
求解子問題：子問題除了與原始問題具有相似性，也具有獨(dú)立性，即所有子問題都可以獨(dú)立求解。
合并子問題：合并每一個(gè)子問題的求解結(jié)果最終可以得到原始問題的解。
下面通過深入了解希爾排序算法，看看分治算法是如何以哲學(xué)之美的方式工作的。
講解希爾之前，先要回顧一下插入排序。插入排序的平均時(shí)間復(fù)雜度，理論上而言和冒泡排序是一樣的 O（n2），但如果數(shù)列是前部分有序，則每一輪只需比較一次，對于 n 個(gè)數(shù)字的原始數(shù)列而言，時(shí)間復(fù)雜度可以是達(dá)到 O(n)。
插入排序的時(shí)間復(fù)雜度為什么會(huì)出現(xiàn)如此有意思的變化？
希爾排序算法本質(zhì)就是插入排序，或說是對插入排序的改良。
其算法理念：讓原始數(shù)列不斷趨近于排序，從而降低插入排序的時(shí)間復(fù)雜度。
希爾排序的實(shí)現(xiàn)流程：
希爾排序算法的理念：當(dāng)數(shù)列局部有序時(shí)，全局必然是趨向于有序”。
希爾排序的關(guān)鍵在于如何切分子數(shù)列，切分方式可以有 2 種：
任何時(shí)候使用分治理念解決問題時(shí)，分拆子問題都是關(guān)鍵的也是核心的。
如有原始數(shù)列=[3，9，8，1，6，5，7] 采用前后分成 2 個(gè)子數(shù)列。
前后分算得上是簡單粗暴的切分方案，沒有太多技術(shù)含量，這種一根筋的切分方式，對于原始問題的最終性能優(yōu)化可能起不了太多影響。
如上圖所示，對子數(shù)列排序后，如果要實(shí)現(xiàn)原始數(shù)列中的所有數(shù)字從小到大排列有序，則后部分的數(shù)字差不多全部要移到時(shí)前部分?jǐn)?shù)字的中間，其移動(dòng)量是非常大的。
后面的 4 個(gè)數(shù)字中，1 需要移動(dòng) 3 次，5、6、7 需要移動(dòng) 2 次， 肉眼可見的次數(shù)是 9 次。
這種分法很難實(shí)現(xiàn)數(shù)字局部有序的正態(tài)分布，因?yàn)?strong>數(shù)字的位置變化不大。
如下圖是原始數(shù)列=[3，9，8，1，6，5，7] 的原始位置示意圖：
使用前后切分后的數(shù)字位置變化如下圖所示，和上圖相比較，數(shù)字的位置變化非常有限，而且是限定在一個(gè)很窄的范圍內(nèi)。也就是說子問題的求解結(jié)果對最終問題的結(jié)果的影響很微小。
增量切分采用間隔切分方案，可能讓數(shù)字局部有序以正態(tài)分布。
增量切分，需要先設(shè)定一個(gè)增量值。如對原始數(shù)列=[3，9，8，1，6，5，7] 設(shè)置切分增量為 3 時(shí)，整個(gè)數(shù)列會(huì)被切分成 3 個(gè)邏輯子數(shù)列。增量數(shù)也決定最后能切分多少個(gè)子數(shù)列。
對切分后的 3 個(gè)子數(shù)列排序后可得到下圖：
在此基礎(chǔ)之上，再進(jìn)行插入排序的的次數(shù)要少很多。
使用增量切分后再排序，原始數(shù)列中的數(shù)字的位置變化范圍較大。
如數(shù)字
9原始位置是1，經(jīng)過增量切分再排序后位置可以到4。已經(jīng)很接近9的最終位置6了。
下圖是增量切分后數(shù)字位置的變化圖，可以看出來，幾乎所有的數(shù)字都產(chǎn)生了位置變化 ，且位置變化的跨度較大。有整體趨于有序的勢頭。
實(shí)現(xiàn)希爾排序算法時(shí)，最佳的方案是先初始化一個(gè)增量值，切分排序后再減少增量值，如此反復(fù)直到增量值等于 1 （也就是對原數(shù)列整體做插入排序）。
增量值大，數(shù)字位置變化的跨度就大，增量值小，數(shù)字位置的變化會(huì)收緊。
編碼代碼希爾排序：
重慶分公司
重慶分公司
# 希爾排序
def shell_sort(nums):
# 增量
increment = len(nums) // 2
# 新數(shù)列
while increment > 0:
# 增量值是多少，則切分的子數(shù)列就有多少
for start in range(increment):
insert_sort(nums, start, increment)
# 修改增量值，直到增量值為 1
increment = increment // 2
# 插入排序
def insert_sort(nums, start, increment):
for back_idx in range(start + increment, len(nums), increment):
for front_idx in range(back_idx, 0, -increment):
if nums[front_idx] < nums[front_idx - increment]:
nums[front_idx], nums[front_idx - increment] = nums[front_idx - increment], nums[front_idx]
else:
break
nums = [3, 9, 8, 1, 6, 5, 7]
shell_sort(nums)
print(nums)
這里會(huì)有一個(gè)讓人疑惑的觀點(diǎn)：難道一次插入排序的時(shí)間復(fù)雜度會(huì)高于多次插入排序時(shí)間復(fù)雜度？
通過切分方案，經(jīng)過子數(shù)列的微排序（因子數(shù)列數(shù)字不多，其移動(dòng)交換量也不會(huì)很大），最后一次插入排序的移動(dòng)次數(shù)可以達(dá)到最小，只要增量選擇合適，時(shí)間復(fù)雜度可以控制 在 O(n) 到 O（2） 之間。完全是有可能優(yōu)于單純的使用一次插入排序。
歸并排序算法也是基于分治思想。和希爾排序一樣，需要對原始數(shù)列進(jìn)行切分，但是切分的方案不一樣。
相比較希爾排序，歸并排序的分解子問題，求解子問題，合并子問題的過程分界線非常清晰?？梢哉f，歸并排序更能完美詮釋什么是分治思想。
歸并排序算法的分解過程采用二分方案。
把原始數(shù)列一分為二。
然后在已經(jīng)切分后的子數(shù)列上又進(jìn)行二分。
如此反復(fù)，直到子數(shù)列不能再分為止。
如下圖所示：
如下代碼，使用遞歸算法對原數(shù)列進(jìn)行切分，通過輸出結(jié)果觀察切分過程：
# 切分原數(shù)列
def split_nums(nums):
print(nums)
if len(nums) > 1:
# 切分線，中間位置
sp_line = len(nums) // 2
split_nums(nums[0:sp_line])
split_nums(nums[sp_line:])
nums = [3, 9, 8, 1, 6, 5, 7]
split_nums(nums)
輸出結(jié)果：和上面演示圖的結(jié)論一樣。
[3, 9, 8, 1, 6, 5, 7]
[3, 9, 8]
[3]
[9, 8]
[9]
[8]
[1, 6, 5, 7]
[1, 6]
[1]
[6]
[5, 7]
[5]
[7]
切分后，對每相鄰 2 個(gè)子數(shù)列進(jìn)行合并。當(dāng)對相鄰 2 個(gè)數(shù)列進(jìn)行合并時(shí)，不是簡單合并，需要保證合并后的數(shù)字是排序的。如下圖所示：
如何實(shí)現(xiàn) 2 個(gè)數(shù)字合并后數(shù)字有序？
使用子數(shù)列中首數(shù)字比較算法進(jìn)行合并排序。如下圖演示了如何合并 nums01=[1,3,8,9]、nums02=[5,6,7] 2 個(gè)子數(shù)列。
子數(shù)列必須是有序的?。?/p>
從頭至尾，進(jìn)行首數(shù)字大小比較，最后，可以保證合并后的數(shù)列是有序的。
編寫一個(gè)合并排序代碼：
如果僅僅是合并 2 個(gè)有序數(shù)列，本文提供 2 個(gè)方案：
def merge_sort(nums01, nums02):
# 為 2 個(gè)數(shù)列創(chuàng)建 2 個(gè)指針
idx_01 = 0
idx_02 = 0
while idx_01 < len(nums01) and idx_02 < len(nums02):
if nums01[idx_01] > nums02[idx_02]:
# 這里不額外增加存儲空間，如果數(shù)列 2 中的值大于數(shù)字 1 的插入到數(shù)列 1 中
nums01.insert(idx_01, nums02[idx_02])
idx_02 += 1
# 數(shù)列 1 的指針向右移動(dòng)
idx_01 += 1
# 檢查 nums02 中的數(shù)字是否已經(jīng)全部合并到 nums01 中
while idx_02 < len(nums02):
nums01.append(nums02[idx_02])
idx_02 += 1
nums01 = [1, 2, 8, 9]
nums02 = [5, 6, 7, 12, 15]
merge_sort(nums01, nums02)
# 合并后的數(shù)字都存儲到了第一個(gè)數(shù)列中
print(nums01)
'''
輸出結(jié)果：
[1,2,5,6,7,8,9,12,15]
'''
# 使用附加數(shù)列
nums=[]
def merge_sort(nums01, nums02):
# 為 2 個(gè)數(shù)列創(chuàng)建 2 個(gè)指針
idx_01 = 0
idx_02 = 0
k=0
while idx_01 < len(nums01) and idx_02 < len(nums02):
if nums01[idx_01] > nums02[idx_02]:
nums.append(nums02[idx_02])
idx_02 += 1
else:
nums.append(nums01[idx_01])
idx_01 += 1
k+=1
# 檢查是否全部合并
while idx_02 < len(nums02):
nums.append(nums02[idx_02])
idx_02 += 1
while idx_01 < len(nums01):
nums.append(nums01[idx_01])
idx_01 += 1
nums01 = [1, 2, 8, 9]
nums02 = [5, 6, 7, 12, 15]
merge_sort(nums01, nums02)
print(nums)
前面是分步講解切分和合并邏輯，現(xiàn)在把切分和合并邏輯合二為一，就完成了歸并算法的實(shí)現(xiàn)：
def merge_sort(nums):
if len(nums) > 1:
# 切分線，中間位置
sp_line = len(nums) // 2
nums01 = nums[:sp_line]
nums02 = nums[sp_line:]
merge_sort(nums01)
merge_sort(nums02)
# 為 2 個(gè)數(shù)列創(chuàng)建 2 個(gè)指針
idx_01 = 0
idx_02 = 0
k = 0
while idx_01 < len(nums01) and idx_02 < len(nums02):
if nums01[idx_01] > nums02[idx_02]:
# 合并后的數(shù)字要保存到原數(shù)列中
nums[k] = nums02[idx_02]
idx_02 += 1
else:
nums[k] = nums01[idx_01]
idx_01 += 1
k += 1
# 檢查是否全部合并
while idx_02 < len(nums02):
nums[k] = nums02[idx_02]
idx_02 += 1
k += 1
while idx_01 < len(nums01):
nums[k] = nums01[idx_01]
idx_01 += 1
k += 1
nums = [3, 9, 8, 1, 6, 5, 7]
merge_sort(nums)
print(nums)
個(gè)人覺得，歸并算法對于理解分治思想有大的幫助。
從歸并算法上可以完整的體現(xiàn)分治理念的哲學(xué)之美。
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或 bin sort。
基數(shù)排序沒有使用分治理念，放在本文一起講解，是因?yàn)榛鶖?shù)排序有一個(gè)對數(shù)字自身切分邏輯。
基數(shù)排序的最基本思想：
如對原始數(shù)列 nums = [3, 9, 8, 1, 6, 5, 7] 中的數(shù)字使用基數(shù)排序。
先提供一個(gè)長度為 10 的新空數(shù)列（本文也稱為排序數(shù)列）。
為什么新空數(shù)列的長度要設(shè)置為 10？等排序完畢，相信大家就能找到答案。
。把原數(shù)列中的數(shù)字轉(zhuǎn)存到新空數(shù)列中，轉(zhuǎn)存方案：
nums 中的數(shù)字 3 存儲在新數(shù)列索引號為 3 的位置。
nums 中的數(shù)字 9 存儲在新數(shù)列索引號為 9 的位置。
nums 中的數(shù)字 8 存儲在新數(shù)列索引號為 8 的位置。
……
從上圖可知，原數(shù)列中的數(shù)字所轉(zhuǎn)存到排序數(shù)列中的位置，是數(shù)字所代表的索引號所指的位置。顯然，經(jīng)過轉(zhuǎn)存后，新數(shù)列就是一個(gè)排好序的數(shù)列。
新空數(shù)列的長度定義為多大由原始數(shù)列中數(shù)字的最大值來決定。
編碼實(shí)現(xiàn)：
# 原數(shù)列
nums = [3, 9, 8, 1, 6, 5, 7]
# 找到數(shù)列中的最大值
sort_nums=[0]*(max(nums)+1)
for i in nums:
sort_nums[i]=i
print([i for i in sort_nums if i!=0])
'''
輸出結(jié)果：
[1,3,5,6,7,8,9]
'''
使用上述方案創(chuàng)建新空數(shù)據(jù)，如果數(shù)字之間的間隔較大時(shí)，新數(shù)列的空間浪費(fèi)就非常大。
如對 nums=[1,98,51,2,32,4,99,13,45] 使用上述方案排序，新空數(shù)列的長度要達(dá)到 99 ，真正需要保存的數(shù)字只有 7 個(gè)，如此空間浪費(fèi)幾乎是令人恐怖的。
所以，有必要使用改良方案。如果在需要排序的數(shù)字中出現(xiàn)了 2 位以上的數(shù)字，則使用如下法則：
可看到有可能在同一個(gè)位置保存多個(gè)數(shù)字。這也是基數(shù)排序也稱為桶排序的原因。
一個(gè)位置就是一個(gè)桶，可以存放多個(gè)具有相同性質(zhì)的數(shù)字。如上圖：個(gè)位上數(shù)字相同的數(shù)字就在一個(gè)桶中。
nums=[1，51，2，32，13，4，45，8，99]可以看到，經(jīng)過 2 輪轉(zhuǎn)存后，原數(shù)列就已經(jīng)排好序。
這個(gè)道理是很好理解的：
現(xiàn)實(shí)生活中，我們在比較 2 個(gè)數(shù)字 大小時(shí)，可以先從個(gè)位上的數(shù)字相比較，然后再對十位上的數(shù)字比較。
基數(shù)排序，很有生活的味道??！
編碼實(shí)現(xiàn)基數(shù)排序：
nums = [1, 98, 51, 2, 32, 4, 99, 13, 45]
# 數(shù)列中的最大值
m = max(nums)
# 確定最大位數(shù)，用來確定需要轉(zhuǎn)存多少次
l = len(str(m))
for i in range(l + 1):
# 排序數(shù)列，也是桶
sort_nums = [[] for _ in range(10)]
for n in nums:
# 分解數(shù)字個(gè)位上的數(shù)字
g_s = (n // 10 ** i) % 10
# 根據(jù)個(gè)位上的數(shù)字找到轉(zhuǎn)存位置
sub_nums = sort_nums[g_s]
sub_nums.append(n)
# 合并數(shù)據(jù)
nums = []
for l in sort_nums:
nums.extend(l)
print(nums)
'''
輸出結(jié)果：
[1, 2, 4, 13, 32, 45, 51, 98, 99]
'''
上述轉(zhuǎn)存過程是由低位到高位，也稱為 LSD ，也可以先高位后低位方案轉(zhuǎn)存MSD。
分治很有哲學(xué)味道，當(dāng)你遇到困難，應(yīng)該試著找到問題的薄弱點(diǎn)，然后一點(diǎn)點(diǎn)地突破。
當(dāng)遇到困難時(shí)，老師們總會(huì)這么勸解我們。
分治其實(shí)和項(xiàng)目開發(fā)中的組件設(shè)計(jì)思想也具有同工異曲之處。
