首頁  >  文章  >  後端開發  >  Python實作希爾排序演算法並附帶原理圖解

Python實作希爾排序演算法並附帶原理圖解

PHPz
PHPz轉載
2024-01-23 15:33:051100瀏覽

Shell排序算法是插入排序算法的强化版本。算法将原始集合分解为更小的子集,然后使用插入排序对每个子集进行排序。

Shell排序算法中可以使用的最佳序列

原始序列:N/2,N/4,…,1

诺斯增量序列:1,4,13,…,(3k–1)/2

Sedgewic增量序列:1,8,23,77,281,1073,4193,16577...4j+1+3·2j+1

Hibbard增量序列:1,3,7,15,31,63,127,255,511…

Papernov&Stasevich增量序列:1,3,5,9,17,33,65,...

普拉提序列:1,2,3,4,6,9,8,12,18,27,16,24,36,54,81....

Shell排序算法原理

Shell排序算法原理图解 Python实现shell排序算法

1、以初始数组(如上图)为例,进行排序

2、使用Shell排序算法的原始序列(N/2,N/4,...1)作为算法中的间隔。在第一个循环中,如果数组大小,则比较和互换N=8的元素。

N/2=4,比较第0元素与第4元素。如果第0元素大于第4元素,把第4名元素存储在变量temp中,值更大的元素存储在第4元素的位置,再把变量temp的值存储在第0元素的位置。

在N/2间隔内重新排列所有元素

Shell排序算法原理图解 Python实现shell排序算法

将所有其余元素继续此过程。

Shell排序算法原理图解 Python实现shell排序算法

3、在第二个循环中,N/4=8/4=2取一个区间,并再次对位于这些区间的元素进行排序。比较位于N/4间隔的数组中的所有元素。

Shell排序算法原理图解 Python实现shell排序算法

Shell排序算法原理图解 Python实现shell排序算法

元素在第4和第2位置进行比较,元素在第2和第0比较。比较阵列中的所有元素都在当前间隔。

4、剩余元素也进行了相同的过程,在N/4间隔内重新排列所有元素。

Shell排序算法原理图解 Python实现shell排序算法

5、最后,当N/8=8/8=1时,对位于区间1的数组元素进行排序,在N/8间隔内重新排列元素。

Shell排序算法原理图解 Python实现shell排序算法

Python实现shell排序算法

def shellSort(array,n):
      interval=n//2
    while interval>0:
    for i in range(interval,n):
      temp=array<i>
      j=i
      while j>=interval and array[j-interval]>temp:
            array[j]=array[j-interval]
            j-=interval
      array[j]=temp
      interval//=2

data=[9,8,3,7,5,6,4,1]
size=len(data)
shellSort(data,size)
print(&#x27;Sorted Array in Ascending Order:&#x27;)
print(data)

以上是Python實作希爾排序演算法並附帶原理圖解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:163.com。如有侵權,請聯絡admin@php.cn刪除

相關文章

看更多