在Python中怎么實(shí)現(xiàn)希爾排序算法

這篇文章主要講解了“在Python中怎么實(shí)現(xiàn)希爾排序算法”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“在Python中怎么實(shí)現(xiàn)希爾排序算法”吧！

算法描述

希爾排序，又叫“縮小增量排序”，是對(duì)插入排序進(jìn)行優(yōu)化后產(chǎn)生的一種排序算法。它的執(zhí)行思路是：把數(shù)組內(nèi)的元素按下標(biāo)增量分組，對(duì)每一組元素進(jìn)行插入排序后，縮小增量并重復(fù)之前的步驟，直到增量到達(dá)1。

一般來(lái)說(shuō)，希爾排序的時(shí)間復(fù)雜度為O(n1.3)～O(n2)，它視增量大小而定。希爾排序的空間復(fù)雜度是O(1)，它是一個(gè)不穩(wěn)定的排序算法。進(jìn)行希爾排序時(shí)，元素一次移動(dòng)可能跨越多個(gè)元素，從而可能抵消多次移動(dòng)，提高了效率。

下面是使用（數(shù)組長(zhǎng)度/2）作為初始增量的升序希爾排序，每一輪排序過(guò)后，增量都縮小一半。

第一步：

如圖2-28所示，從第一個(gè)元素開(kāi)始，以增量4來(lái)分組?？梢钥闯觯?dāng)增量為4時(shí)，一組內(nèi)只有兩個(gè)元素，否則元素的下標(biāo)就超出了數(shù)組的范圍。

第二步：

如圖2-29所示，對(duì)組內(nèi)的元素進(jìn)行插入排序。

第三步：

如圖2-30所示，繼續(xù)用相同的方法分組，對(duì)組內(nèi)的元素進(jìn)行插入排序使得它們有序。

整個(gè)數(shù)組內(nèi)的數(shù)都被遍歷完成后，這一輪排序就結(jié)束了。把增量縮小一半，繼續(xù)進(jìn)行下一輪排序。

第四步：

如圖2-31所示，增量為2時(shí)，可以看出每一組內(nèi)的元素增多了，組的總數(shù)減少了。繼續(xù)對(duì)每一組內(nèi)的元素進(jìn)行插入排序，直到每一組都遍歷完成。

第五步：

最后一輪排序如圖2-32所示，再次把增量縮小一半；這時(shí)增量為1，相當(dāng)于對(duì)整個(gè)數(shù)組進(jìn)行插入排序，也就是最后一輪排序。

最后一輪排序結(jié)束后，整個(gè)希爾排序就結(jié)束了。

代碼實(shí)現(xiàn)

在for循環(huán)中，由于每組的第一個(gè)元素不用進(jìn)行插入排序，而它們的下標(biāo)處于0～step-1，所以從下標(biāo)step開(kāi)始遍歷。

需要注意的是，如果要模擬流程圖中的做法，要使用兩個(gè)循環(huán)：先分組，然后一次性使同組內(nèi)的元素有序。為了提高效率，我們直接使用一個(gè)for循環(huán)，每遍歷到一個(gè)數(shù)，就對(duì)它所在的組進(jìn)行插入排序。這樣遍歷同樣符合插入排序的順序要求。在插入排序中，要改變當(dāng)前下標(biāo)的值，所以使用變量ind存儲(chǔ)當(dāng)前下標(biāo)，防止影響for循環(huán)。

普通插入排序等同于增量為1的希爾排序，跨元素的希爾排序?qū)嶋H上只改變了增量，邏輯上與普通插入排序沒(méi)有區(qū)別。

希爾排序代碼：

nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
  step = len(nums)//2　　　　　　　　 #初始化增量為數(shù)組長(zhǎng)度的一半
  while step > 0:　　　　　　　　　　 #增量必須是大于0的整數(shù)
   for i in range(step,len(nums)):　#遍歷需要進(jìn)行插入排序的數(shù)
     ind = i
     while ind >= step and nums[ind] < nums[ind-step]: #對(duì)每組進(jìn)行插入排序
      nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
      ind -= step
   step //= 2　　　　　　　　　　　#增量縮小一半
  print(nums)
ShellSort(nums)

運(yùn)行程序，輸出結(jié)果為：

[1,2,3,4,5,6,7,8]

感謝各位的閱讀，以上就是“在Python中怎么實(shí)現(xiàn)希爾排序算法”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)在Python中怎么實(shí)現(xiàn)希爾排序算法這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！