一、前言

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

二、算法描述

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

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

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

第一步：

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

第二步：

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

第三步：

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

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

第四步：

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

第五步：

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

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

三、代碼實現(xiàn)

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

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

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

希爾排序代碼：

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

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

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

總結(jié)

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

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

最新評論