希尔排序及其实现

2744557306

希尔排序（Shell Sort）是一种基于插入排序的排序算法，它通过将待排序的元素按步长进行分组，然后对每组进行插入排序，逐步缩小步长，最终完成排序。
1 y/ B0 Z9 ?3 W( ~# [- l- n下面是希尔排序的基本思路：

1.选择一个步长序列，通常选取希尔增量（Shell Increment），可以是固定的序列，也可以是动态生成的序列。
1 U0 r9 F! l5 u7 l! L0 q2.根据选定的步长序列，对待排序的列表进行分组。
6 `: Q2 H- U, m+ ~2 R7 r: k3.对每个分组进行插入排序。
1 J: ?  H# b4 _6 m4 s8 Q+ X4.缩小步长，重复步骤 2 和 3，直到步长为 1。

, }$ k! z" B6 c: G- W! f下面是使用Python编写的希尔排序代码实现：
; |  E0 D8 y+ k$ [" bdef shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始化步长为数组长度的一半

    while gap > 0:
- Z& B' R6 {3 Q7 w        for i in range(gap, n):
4 @8 u* H  ]* Y            temp = arr[i]  # 当前待插入元素
            j = i

            while j >= gap and arr[j - gap] > temp:
2 [1 r) ^9 M/ I! P8 h' ]1 R                arr[j] = arr[j - gap]  # 后移元素
) q! W) R) A; ~0 \. Z; C) A% p0 {                j -= gap
( h8 {" J: }+ Y% c
            arr[j] = temp  # 插入元素到正确位置
  q8 e4 R$ n0 m& R6 ~" \
8 n8 m3 Y( h. _+ h! g        gap //= 2  # 缩小步长
! a* ~5 y. x: |+ p
  L- r0 J3 v8 P* ?    return arr

你可以调用 shell_sort 函数并传入待排序的列表，函数将返回排序后的列表。
( o# m0 c" c7 ~3 I; O7 H0 Z7 G5 m希尔排序的时间复杂度取决于选定的步长序列，最优的步长序列可以达到 O(n log^2 n)，但并不容易确定最优的步长序列。希尔排序相对于其他排序算法具有一定的优势，但在某些特殊情况下可能性能不如快速排序、归并排序等算法。
. X% q& p# k2 B% A' a9 S: p
8 r( ^5 s% U4 z# g" H2 s8 O: C& [7 z
8 z0 ?; d1 P7 d4 I5 K+ B