展示系统 网站模板,智慧新零售系统,学网站开发网页制作,软件开发工程师职业满足兴趣因素插入排序每次只能将数据移动一位。
已知插入排序代码为#xff1a;
def insert_sort(a):for i in range(1,len(a)):ji-1while j0 and a[j]a[i]:a[j1]a[j]j-1a[j1]a[i]return a希尔排序在插入排序的基础上#xff0c;将数据移动n/2,n/4,…,1位。
for i in range(ga… 插入排序每次只能将数据移动一位。
已知插入排序代码为
def insert_sort(a):for i in range(1,len(a)):ji-1while j0 and a[j]a[i]:a[j1]a[j]j-1a[j1]a[i]return a希尔排序在插入排序的基础上将数据移动n/2,n/4,…,1位。
for i in range(gap, n):
temp a[i]把a[i]的值赋给temp用于比较
j i j指针从i开始表示的是从后往前遍历比大小的下标。
当j gap为了确保后面的j-gap下标还在数组索引里不会超出范围 and a[j - gap] tempj-temp对应的数大于j对应的数把j-gap的数放到原来的j的位置然后再往前对比:
此时j下标对应的数是原来j-gap对应的数 a[j] a[j - gap]
因为根据插入排序原理把要插入的数的大小temp跟前面已经排序好的数以步长为1 j - 1从后往前进行对比希尔排序也是把要插入的数的大小temp跟前面已经排序好的数从后往前对比但是是以步长为gap往前遍历。所以 j - gap
跳出while循环的条件是已经把前面gap步长遇到的所有值排好序了而且原来的a[j]a[j-gap]是把j-gap比temp大的值放到了j的位置那原来的j-gap的位置就空了出来j-gap操作后原来的j-gap就是新的j的位置把temp放到这个位置a[j] temp。实现了如果a[j - gap] tempa[i]那么交换位置的操作。
用gap // 2不断缩小步长直到gap1跟插入排序一致此时所有数据顺序都排好了。
比如有一组示例数据如下
7291546
a数组长度是7
这里的gap初始值是7//23
a[i]初始值从3开始a[3]1。
接下来就是以gap的步长往前遍历把数组分为4组
a[j-temp] temp
7 1
2 6
9 4
1 6然后进行对比如果a[j - gap] temp交换位置。
这样处理后的数组为
1247596
gap // 2gap1。
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然后进行对比如果a[j - gap] temp交换位置。
这样处理后的数组为
1245679
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更高效的原因是因为希尔排序通过使用间隔序列在排序过程中引入了数据交换的“跳跃”。这种跳跃允许算法在内部循环中进行更远距离的交换从而减少了元素比较和移动的次数。
对比代码如下
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# 生成随机数组
array_size 1000
random_array [random.randint(1, 10000) for _ in range(array_size)]# 复制数组以保持原始数组不变
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(fInsertion Sort: Comparisons{insertion_comparisons}, Moves{insertion_moves}, Time{insertion_time:.6f}s)
print(fShell Sort: Comparisons{shell_comparisons}, Moves{shell_moves}, Time{shell_time:.6f}s)Insertion Sort: Comparisons245538, Moves244539, Time0.035560s
Shell Sort: Comparisons14866, Moves7356, Time0.000997s
