希尔排序的实现pta

### 希尔排序简介

希尔排序是一种基于插入排序的高效排序算法，通过比较相隔一定间隔的元素来工作。随着算法运行，这些间隔逐渐减小直到变为1，在最后阶段，希尔排序退化成普通的插入排序[^1]。

### C++ 实现希尔排序

以下是使用C++编写的希尔排序函数：

void shell_sort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

这段代码实现了经典的希尔排序逻辑，其中`gap`表示当前处理序列之间的距离，每次循环都将`gap`除以2直至其等于1。

### 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

此段Python代码同样遵循了上述提到的原则，并且利用列表切片特性简化了一些操作。