八十五、再探希爾排序，桶排序，計(jì)數(shù)排序和基數(shù)排序

「@Author：Runsen」

編程的本質(zhì)來(lái)源于算法，而算法的本質(zhì)來(lái)源于數(shù)學(xué)，編程只不過(guò)將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

關(guān)于排序，其實(shí)還有很多，比如常見(jiàn)的希爾排序，桶排序，計(jì)數(shù)排序和基數(shù)排序，今天一口氣把十大排序剩下的全部解決。

在此之前，需要對(duì)網(wǎng)上流傳千久的十大排序算法空間時(shí)間復(fù)雜度圖刻入腦海中。

希爾排序

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)之后的一個(gè)更高效的版本，也稱(chēng)為縮小增量排序，同時(shí)該算法是沖破的第一批算法之一。

希爾排序的思路：「將待排序列劃分為若干組，在每一組內(nèi)進(jìn)行插入排序，以使整個(gè)序列基本有序，然后再對(duì)整個(gè)序列進(jìn)行插入?！?/strong>

我們先回看插入排序的代碼，如果插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位。，則將當(dāng)前元素后移一位，直到找到一個(gè)當(dāng)前元素小于插入元素。

def?insertionSort(arr):
????for?i?in?range(len(arr)):
????????preIndex?=?i?-?1
????????current?=?arr[i]
????????while?preIndex?>=?0?and?arr[preIndex]?>?current:
????????????arr[preIndex?+?1]?=?arr[preIndex]
????????????preIndex?-=?1
????????arr[preIndex?+?1]?=?current
????return?arr

if?__name__?==?'__main__':
????nums?=?[54,?26,?93,?17,?77,?31,?44,?55,?20]
????insert_sort(nums)
????print(nums)?#?[17,?20,?26,?31,?44,?54,?55,?77,?93]

希爾排序的基本思想是：把記錄按步長(zhǎng) gap 分組（gap一般是數(shù)組長(zhǎng)度的中間數(shù)），對(duì)每組記錄采用直接插入排序方法進(jìn)行排序。

隨著步長(zhǎng)逐漸減?。?strong style="color: rgb(145, 109, 213);">「進(jìn)行除以二操作」），所分成的組包含的記錄越來(lái)越多，當(dāng)步長(zhǎng)的值減小到 1 時(shí)，整個(gè)數(shù)據(jù)合成為一組，構(gòu)成一組有序記錄，則完成排序。

def?shell_sort(nums):
????size?=?len(nums)
????gap?=?size?>>?1?#相當(dāng)于size//2
????while?gap?>?0:
????????#?代碼和插入排序一樣
????????for?i?in?range(gap,?size):
????????????j?=?i
????????????while?j?>=?gap?and?nums[j?-?gap]?>?nums[j]:
????????????????nums[j?-?gap],?nums[j]?=?nums[j],?nums[j?-?gap]
????????????????#?這里減的不是一，而且gap
????????????????j?-=?gap
????????gap?=?gap?>>?1

if?__name__?==?'__main__':
????nums?=?[54,?26,?93,?17,?77,?31,?44,?55,?20]
????shell_sort(nums)
????print(nums)?#?[17,?20,?26,?31,?44,?54,?55,?77,?93]

希爾排序?qū)τ诓迦肱判騺?lái)說(shuō)，當(dāng)間隔比較大時(shí)，移動(dòng)的次數(shù)比較少，間隔比較小時(shí)，移動(dòng)的距離比較短。因此希爾排序的效率明顯高于插入排序。

「但是希爾排序是一個(gè)不穩(wěn)定的排序算法。」 對(duì)于排序算法，所謂的不穩(wěn)定指的就是「相同元素在排序過(guò)程中被移動(dòng)?！?/strong> 一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以希爾排序是一個(gè)不穩(wěn)定的排序算法。

計(jì)數(shù)排序

計(jì)數(shù)排序是一種思維很高的排序，使用的場(chǎng)景是「待排序序列中元素的取值范圍比較小」，這種算法有時(shí)候會(huì)比快速排序還要快。

因此計(jì)數(shù)排序需要使用一個(gè)輔助數(shù)組計(jì)數(shù)列表，也可以叫做，因此空間復(fù)雜度不是，是一種犧牲空間換取時(shí)間的排序算法。

計(jì)數(shù)排序的核心思想：遍歷待排序的數(shù)據(jù)，尋找最大值 k，然后開(kāi)辟一個(gè)長(zhǎng)度為k+1的計(jì)數(shù)列表，計(jì)數(shù)列表中的值都為0。如果走訪到的元素值為i，則計(jì)數(shù)列表中索引i的值加1。

走訪完整個(gè)待排序列表，計(jì)數(shù)列表中索引i的值j表示i的個(gè)數(shù)為j，統(tǒng)計(jì)出待排序列表中每個(gè)值的數(shù)量。

待排序數(shù)據(jù)的值就是輔助數(shù)組的索引，輔助數(shù)組索引對(duì)應(yīng)的位置保存這個(gè)待排序數(shù)據(jù)出現(xiàn)的次數(shù)。最后從輔助數(shù)組中取出待排序的數(shù)據(jù)，放到排序后的數(shù)組中。

最后創(chuàng)建一個(gè)新列表，遍歷計(jì)數(shù)列表，對(duì)新列表進(jìn)行添加數(shù)據(jù)就可以了。

「沒(méi)看明白，不急，后面來(lái)張圖就搞明白了」

因此，你就知道如果一個(gè)數(shù)據(jù)非常大，比如1000，那么這個(gè)輔助數(shù)組就變得非常大，所以計(jì)數(shù)排序只適合待排序序列中元素的取值范圍比較小的排序。

def?count_sort(s):
????"""計(jì)數(shù)排序"""
????#?找到最大最小值
????min_num?=?min(s)
????max_num?=?max(s)
????#?計(jì)數(shù)列表
????count_list?=?[0]*(max_num-min_num+1)
????#?計(jì)數(shù)
????for?i?in?s:
????????count_list[i-min_num]?+=?1
????s.clear()
????#?填回
????for?ind,i?in?enumerate(count_list):
????????while?i?!=?0:
????????????s.append(ind+min_num)
????????????i?-=?1

if?__name__?==?'__main__':
????a?=?[3,6,8,4,2,6,7,3]
????count_sort(a)
????print(a)

桶排序

個(gè)人覺(jué)得桶排序其實(shí)也是一個(gè)分治算法的思想，我想到桶排序，就會(huì)聯(lián)想到高考分?jǐn)?shù)排名，廣東高考七十多萬(wàn)考生，我們只需要對(duì)不同區(qū)域進(jìn)行劃分，比如在700到750這個(gè)階段的人數(shù)進(jìn)行排序，其實(shí)對(duì)不同區(qū)域進(jìn)行劃分這個(gè)操作，就是劃分不同的桶。不同的桶就各自排序，所以叫做桶排序。

關(guān)于桶排序的代碼編寫(xiě)，其實(shí)說(shuō)簡(jiǎn)單也簡(jiǎn)單，說(shuō)難也挺難。

下面，我以區(qū)間為10的來(lái)劃分不同的桶。桶里面的排序選擇快排，因此也需要用遞歸寫(xiě)一個(gè)快排算法，具體代碼如下。

def?quicksort(array):
??if?len(array)?2:
????#?基本情況下，具有0或1個(gè)元素的數(shù)組是已經(jīng)“排序”的
????return?array
??else:
????#?遞歸情況
????pivot?=?array[0]
????#?小于基準(zhǔn)值的所有元素的子數(shù)組
????less?=?[i?for?i?in?array[1:]?if?i?<=?pivot]
????#?大于基準(zhǔn)值的所有元素的子數(shù)組
????greater?=?[i?for?i?in?array[1:]?if?i?>?pivot]
????return?quicksort(less)?+?[pivot]?+?quicksort(greater)
????
????
def?bucket_sort(arr):
????maximum,?minimum?=?max(arr),?min(arr)
????bucketArr?=?[[]?for?i?in?range((maximum?-?minimum)//10+1)]???#?設(shè)置桶的個(gè)數(shù)。
????for?i?in?arr:???????#?把每個(gè)數(shù)組的元素放到到對(duì)應(yīng)的桶中。
????????index?=?(i?-?minimum)//10
????????bucketArr[index].append(i)
????arr.clear()
????for?j?in?bucketArr:
????????ls?=?quicksort(j)???#?使用別的排序方法來(lái)排序每個(gè)桶，在此使用快速排序。
????????arr.extend(ls)???#?把每個(gè)桶內(nèi)元素移動(dòng)到數(shù)組中。
????return?arr

if?__name__?==?'__main__':
????res?=?[34,?23,?74,?35,?98,?34,?18,?88,?47,?51,?65,?75,?44,?89]
????sort_res?=?bucket_sort(res)
????print(sort_res)?#[18,?23,?34,?34,?35,?44,?47,?51,?65,?74,?75,?88,?89,?98]

基數(shù)排序

有一種很神奇的排序，基數(shù)排序(Radix Sort)，本質(zhì)上是桶排序，我覺(jué)得基數(shù)排序是桶排序的一個(gè)特例，這誰(shuí)會(huì)想得到用的整數(shù)的個(gè)位、十位、…進(jìn)行排序。

基數(shù)排序就是劃分十個(gè)桶，分別是0到9，這10個(gè)數(shù)字。

第一個(gè)桶0，就可以放10，20，30，100等數(shù)據(jù)，

比如為整數(shù)排序，依次用整數(shù)的個(gè)位、十位…來(lái)排序（LSD低位優(yōu)先）；或者高位到低位依次排序（MSD高位優(yōu)先）。

但是LSD低位優(yōu)先容易理解，比如135、242、192、93、345、11、24、19，收集個(gè)位就變成了11、242、192、93、24、135、345、19。收集十位就變成了11、19、24、135、242、345、192、93。收集百位就變成了11, 19, 24, 93, 135, 192, 242, 345。

具體實(shí)現(xiàn)的代碼如下。

def?radix_sort(ls):
????i?=?0?????????????#?記錄當(dāng)前正在排哪一位，最低位為1
????max_num?=?max(ls)??#?最大值
????j?=?len(str(max_num))??#?記錄最大值的位數(shù)
????while?i?????????bucket_list?=[[]?for?q?in?range(10)]?#初始化桶數(shù)組
????????for?x?in?ls:
????????????bucket_list[int(x?/?(10**i))?%?10].append(x)?#?找到位置放入桶數(shù)組
????????ls.clear()
????????for?x?in?bucket_list:???#?放回原序列
????????????for?y?in?x:
????????????????ls.append(y)
????????i?+=?1
????return?ls

if?__name__?==?'__main__':
????list1?=?[135,242,192,93,345,11,24,19]
????sort_list?=?radix_sort(list1)
????print(sort_list)??#?[11,?19,?24,?93,?135,?192,?242,?345]

這次把希爾排序，桶排序，計(jì)數(shù)排序和基數(shù)排序全部介紹完畢，后面引入有向圖，最后進(jìn)行燒腦的動(dòng)態(tài)規(guī)劃DP算法。

本文已收錄 GitHub，傳送門(mén)~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。