python 希尔排序

好的，下面是 Python 实现的希尔排序代码：

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

希尔排序是插入排序的改进版，通过将数组分成若干个小的子数组进行插入排序，最后再对整个数组进行一次插入排序。希尔排序的时间复杂度约为 $O(n^{1.3})$，在大部分情况下表现良好。