用python写一个希尔排序

下面是使用Python实现希尔排序的代码：

def shellSort(arr):
    n = len(arr)
    gap = n // 2
    # 对数组进行分组，每组的长度为 gap，直到 gap = 1
    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

在这个实现中，我们将原始数组分成了很多子数组，每个子数组都进行插入排序。每个子数组的长度是从整个数组长度的一半自下而上到1。具体来说，代码中的 gap 变量表示着每个子数组的长度，它的初始值为数组长度的一半，每次循环都除以2直到gap等于1。

在每次gap循环中，我们对每个分组进行插入排序。在插入排序中，我们将待排序的子数组分为已排序部分和未排序部分。在已排序部分中，我们将每一个元素与它前面的元素逐一比较，如果它小于前面的元素，则交换两个元素的位置。这样，就能保证已排序部分的元素是有序的。

最终，我们就可以将所有分组的结果合并起来得到一个有序数组。

下面是一个简单的测试代码：

if __name__=='__main__':
    arr = [64, 25, 12, 22, 11]
    print("排序前：", arr)
    sorted_arr = shellSort(arr)
    print("排序后：", sorted_arr)

输出结果：

排序前： [64, 25, 12, 22, 11]
排序后： [11, 12, 22, 25, 64]