一、前言

相關(guān)知識(shí)來(lái)自《python算法設(shè)計(jì)與分析》。初級(jí)排序算法是指幾種較為基礎(chǔ)且容易理解的排序算法。初級(jí)排序算法包括插入排序、選擇排序和冒泡排序3種。相比起初級(jí)排序算法，高級(jí)排序算法往往有更加復(fù)雜的邏輯，但也會(huì)有更高的時(shí)間或空間效率。其中有些高級(jí)排序算法是由初級(jí)排序算法優(yōu)化而來(lái)的。

二、算法描述

希爾排序，又叫“縮小增量排序”，是對(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è)元素開始，以增量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開始遍歷。

需要注意的是，如果要模擬流程圖中的做法，要使用兩個(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上只改變了增量，邏輯上與普通插入排序沒有區(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]

總結(jié)

以上就是本文要講的內(nèi)容，本文介紹了希爾排序的理論知識(shí)和代碼實(shí)現(xiàn)。一般來(lái)說(shuō)，希爾排序的時(shí)間復(fù)雜度為O(n1.3)～O(n2)，它視增量大小而定。希爾排序的空間復(fù)雜度是O(1)，它是一個(gè)不穩(wěn)定的排序算法。

到此這篇關(guān)于python排序算法之希爾排序的文章就介紹到這了,更多相關(guān)python 希爾排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論