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排序算法原理
1、以初始數組（如上圖）為例，進行排序
2、使用Shell排序算法的原始序列(N/2,N/4,…1）作為算法中的間隔。在第一個循環中，如果數組大小，則比較和互換N=8的元素。
N/2=4，比較第0元素與第4元素。如果第0元素大于第4元素，把第4名元素存儲在變量temp中，值更大的元素存儲在第4元素的位置，再把變量temp的值存儲在第0元素的位置。
在N/2間隔內重新排列所有元素
將所有其余元素繼續此過程。
3、在第二個循環中，N/4=8/4=2取一個區間，并再次對位于這些區間的元素進行排序。比較位于N/4間隔的數組中的所有元素。
元素在第4和第2位置進行比較，元素在第2和第0比較。比較陣列中的所有元素都在當前間隔。
4、剩余元素也進行了相同的過程，在N/4間隔內重新排列所有元素。
5、最后，當N/8=8/8=1時，對位于區間1的數組元素進行排序，在N/8間隔內重新排列元素。
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('Sorted Array in Ascending Order:')
print(data)
登錄后復制
