33 lines
1.3 KiB
Python
33 lines
1.3 KiB
Python
|
"""
|
|||
|
|
希尔排序：也称递减递增排序，它将原始集合分为多个较小的子集合，然后对每个集合
|
|||
|
|
运用插入排序
|
|||
|
|
1. 当增量为3时，表示每相隔两个的元素（索引差3）为一个子序列，将原序列分为了三组子序列
|
|||
|
|
2. 对每个子序列使用插入排序，此时每个子序列就是有序的
|
|||
|
|
3. 逐渐减小增量，重复第二2步
|
|||
|
|
4. 当增量为1时，再执行一次插入排序，此时完整序列就是有序的
|
|||
|
|
|
|||
|
|
希尔排序的复杂度分析稍微复杂一些，但其大致分布在 O(n) 到 O(n^2) 之间。
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
def shell_sort(nums: list[int]):
|
|||
|
|
step = len(nums) >> 1
|
|||
|
|
while step >= 1:
|
|||
|
|
# 分成了 step 个子序列，循环 step 次，对每个子序列使用插排
|
|||
|
|
for i in range(step):
|
|||
|
|
for j in range(i + step, len(nums), step):
|
|||
|
|
pos = j
|
|||
|
|
cur = nums[j]
|
|||
|
|
# 无法对子序列使用二分查找，查找插入位置，因为中间位置无法确定
|
|||
|
|
while pos >= step and cur < nums[pos - step]:
|
|||
|
|
# 将比当前值大的往后移 step 位
|
|||
|
|
nums[pos] = nums[pos - step]
|
|||
|
|
pos -= step
|
|||
|
|
|
|||
|
|
nums[pos] = cur
|
|||
|
|
step >>= 1
|
|||
|
|
|
|||
|
|
|
|||
|
|
nums = [47, 29, 71, 99, 78, 19, 24, 47]
|
|||
|
|
shell_sort(nums)
|
|||
|
|
print(nums)
|