插入排序每次只能將數(shù)據(jù)移動(dòng)一位。

已知插入排序代碼為：

def insert_sort(a):for i in range(1,len(a)):j=i-1while j>=0 and a[j]>a[i]:a[j+1]=a[j]j-=1a[j+1]=a[i]return a

希爾排序在插入排序的基礎(chǔ)上，將數(shù)據(jù)移動(dòng)n/2,n/4,…,1位。

for i in range(gap, n):

temp = a[i]：把a(bǔ)[i]的值賦給temp，用于比較

j = i j指針從i開始，表示的是從后往前遍歷比大小的下標(biāo)。

當(dāng)j >= gap（為了確保后面的j-gap下標(biāo)還在數(shù)組索引里，不會(huì)超出范圍） and a[j - gap] > temp（j-temp對(duì)應(yīng)的數(shù)大于j對(duì)應(yīng)的數(shù)，把j-gap的數(shù)放到原來的j的位置，然后再往前對(duì)比）:

此時(shí)j下標(biāo)對(duì)應(yīng)的數(shù)是原來j-gap對(duì)應(yīng)的數(shù)：
a[j] = a[j - gap]

因?yàn)楦鶕?jù)插入排序原理，把要插入的數(shù)的大小temp跟前面已經(jīng)排序好的數(shù)以步長為1（ j -= 1）從后往前進(jìn)行對(duì)比，希爾排序也是把要插入的數(shù)的大小temp跟前面已經(jīng)排序好的數(shù)從后往前對(duì)比，但是是以步長為gap往前遍歷。所以： j -= gap

跳出while循環(huán)的條件是已經(jīng)把前面gap步長遇到的所有值排好序了，而且原來的a[j]=a[j-gap]是把j-gap比temp大的值放到了j的位置，那原來的j-gap的位置就空了出來，j-=gap操作后，原來的j-gap就是新的j的位置，把temp放到這個(gè)位置：a[j] = temp。實(shí)現(xiàn)了如果a[j - gap] > temp（a[i]），那么交換位置的操作。

用gap //= 2不斷縮小步長，直到gap=1跟插入排序一致，此時(shí)所有數(shù)據(jù)順序都排好了。

比如有一組示例數(shù)據(jù)如下

7	2	9	1	5	4	6

a數(shù)組長度是7

這里的gap初始值是7//2=3

a[i]初始值從3開始，a[3]=1。

接下來就是以gap的步長往前遍歷，把數(shù)組分為4組：

a[j-temp]  temp
7			1
2			6
9			4
1			6

然后進(jìn)行對(duì)比，如果a[j - gap] > temp，交換位置。

這樣處理后的數(shù)組為：

1	2	4	7	5	9	6

gap //= 2，gap=1。

a[i]初始值從1開始，a[1]=2。

接下來就是以gap的步長往前遍歷比大小：

a[j-temp]  temp
1			2
# 1247596
--------------
2			4
1			4
# 1247596
--------------
4			7
2			7
1			7
# 1247596
--------------
7			5
# 5,7互換
4			5
2			5
1			5
# 1245796
--------------
7			9
5			9
4			9
2			9
1			9
# 1245796
--------------
9			6
# 6,9互換
7			6
# 6,7互換
5			6
4			6
2			6
1			6
# 1245679

然后進(jìn)行對(duì)比，如果a[j - gap] > temp，交換位置。

這樣處理后的數(shù)組為：

1	2	4	5	6	7	9

def shell_sort(a):n = len(a)gap = n // 2while gap > 0:for i in range(gap, n):temp = a[i]j = iwhile j >= gap and a[j - gap] > temp:a[j] = a[j - gap]j -= gapa[j] = tempgap //= 2

希爾排序（Shell Sort）比插入排序（Insertion Sort）更高效的原因是因?yàn)橄柵判蛲ㄟ^使用間隔序列在排序過程中引入了數(shù)據(jù)交換的“跳躍”。這種跳躍允許算法在內(nèi)部循環(huán)中進(jìn)行更遠(yuǎn)距離的交換，從而減少了元素比較和移動(dòng)的次數(shù)。

對(duì)比代碼如下：

import random
import timedef insertion_sort(arr):comparisons = 0moves = 0for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:comparisons += 1arr[j + 1] = arr[j]moves += 1j -= 1comparisons += 1arr[j + 1] = keyreturn comparisons, movesdef shell_sort(arr):comparisons = 0moves = 0gap = len(arr) // 2while gap > 0:for i in range(gap, len(arr)):temp = arr[i]j = iwhile j >= gap and arr[j - gap] > temp:comparisons += 1arr[j] = arr[j - gap]moves += 1j -= gapcomparisons += j >= gaparr[j] = tempgap //= 2return comparisons, moves# 生成隨機(jī)數(shù)組
array_size = 1000
random_array = [random.randint(1, 10000) for _ in range(array_size)]# 復(fù)制數(shù)組以保持原始數(shù)組不變
insertion_array = random_array.copy()
shell_array = random_array.copy()# 插入排序
start_time = time.time()
insertion_comparisons, insertion_moves = insertion_sort(insertion_array)
insertion_time = time.time() - start_time# 希爾排序
start_time = time.time()
shell_comparisons, shell_moves = shell_sort(shell_array)
shell_time = time.time() - start_timeprint(f"Insertion Sort: Comparisons={insertion_comparisons}, Moves={insertion_moves}, Time={insertion_time:.6f}s")
print(f"Shell Sort: Comparisons={shell_comparisons}, Moves={shell_moves}, Time={shell_time:.6f}s")

Insertion Sort: Comparisons=245538, Moves=244539, Time=0.035560s
Shell Sort: Comparisons=14866, Moves=7356, Time=0.000997s