烟台网站制作企业,手机端网站制作教程,模板网站建设的公司,平台设计是做什么的样例输入
3
2
2 1
3
1
2样例输出
3 2样例说明 输入的数组为#xff1a;【3#xff0c;1#xff0c;2】 增量序列为#xff1a;【2#xff0c;1】 当增量 h2#xff1a;对于每一个索引 i#xff0c;我们会将数组元素 arr[i] 与 arr[i−h] 进行比较#xff0c;并进行可… 样例输入
3
2
2 1
3
1
2样例输出
3 2样例说明 输入的数组为【312】 增量序列为【21】 当增量 h2对于每一个索引 i我们会将数组元素 arr[i] 与 arr[i−h] 进行比较并进行可能的交换。 i2: arr[2]2arr[0]3。因为 23所以交换它们。 数组变为[2,1,3]。 这里进行了 1 次比较和 1 次交换。 注意对于 i0 和 i1由于它们的索引小于增量值 2所以不会进行任何操作。 这里相当于希尔排序的gap2 当增量 h1这就是一个普通的插入排序。 i1:arr[1]1arr[0]2。因为 12所以交换它们。 数组变为[1,2,3]。 这里进行了 1 次比较和 1 次交换。i2:arr[2]3arr[1]2。因为 32所以不交换。 这里进行了 1 次比较。
总结总共进行了 3 次比较2 次交换。
解题思路
这里的订单属性值数组相当于订单大小的a数组
这里的增量数组就相当于是希尔排序里面的gap数组。
用希尔排序模板写代码即可
代码
# 订单数组的长度
nint(input())
# a表示订单的属性值大小
a[]
# 增量gap的长度
mint(input())
gaplist(map(int,input().split()))
for _ in range(n):a.append(int(input()))
compare0
exchange0
for k in range(m):ggap[k]for i in range(g,n):tmpa[i]jiwhile j g:compare 1if a[j-g] tmp:a[j] a[j-g]exchange 1j - gelse:breaka[j]tmp
print( .join(map(str,[compare,exchange])))
