如何實作希爾排序演算法在Python中

演算法描述

希爾排序，又叫“縮小增量排序”，是對插入排序進行最佳化後產生的一種排序演算法。它的執行思路是：把數組內的元素按標增量分組，對每一組元素進行插入排序後，縮小增量並重複之前的步驟，直到增量到達1。

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

以下是使用（陣列長度/2）作為初始增量的升序希爾排序，每一輪排序過後，增量都縮小一半。

第一步：

如圖2-28所示，從第一個元素開始，以增量4來分組。可以看出，當增量為4時，一組內只有兩個元素，否則元素的下標就超出了陣列的範圍。

第二步：

#如圖2-29所示，對群組內的元素進行插入排序。

第三步：

#如圖2-30所示，繼續用相同的方法分組，對群組內的元素進行插入排序使得它們有序。

整個陣列內的數都被遍歷完成後，這一輪排序就結束了。把增量縮小一半，繼續進行下一輪排序。

第四步：

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

步驟五：

最後一輪排序如圖2-32所示，再次把增量縮小一半；這時增量為1 ，相當於對整個陣列進行插入排序，也就是最後一輪排序。

最後一輪排序結束後，整個希爾排序就結束了。

程式碼實作

在for迴圈中，由於每組的第一個元素不用進行插入排序，而它們的下標處於0～step-1，所以從下標step開始遍歷。

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

普通插入排序等同於增量為1的希爾排序，跨元素的希爾排序實際上只改變了增量，邏輯上與普通插入排序沒有區別。

希爾排序代碼：

nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
  step = len(nums)//2　　　　　　　　 #初始化增量为数组长度的一半
  while step > 0:　　　　　　　　　　 #增量必须是大于0的整数
   for i in range(step,len(nums)):　#遍历需要进行插入排序的数
     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)

運行程序，輸出結果為：

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

以上是如何實作希爾排序演算法在Python中的詳細內容。更多資訊請關注PHP中文網其他相關文章！