3、实现希尔排序算法

好的，希尔排序是一种基于插入排序的排序算法，其基本思想是将待排序的元素按照一定的间隔（称为增量）分组，分别对每组使用插入排序，随着增量逐渐减小，每组包含的元素越来越多，当增量为 1 时，整个序列被分为一组，此时的排序就是一般的插入排序。

以下是希尔排序的 C++ 代码实现：

void shellSort(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;
        }
    }
}

其中，arr[] 表示待排序的数组，n 表示数组的长度。算法首先将增量 gap 设为 n 的一半，然后对每个分组使用插入排序，随后将 gap 减半，继续对每个分组使用插入排序，直到 gap 为 1。

时间复杂度为 O(nlogn) 到 O(n^2)，取决于增量序列的选取方式，例如 Shell 提出的增量序列为 gap = n / 2, gap = gap / 2, ..., 直到 gap = 1，此时时间复杂度为 O(n^2)。空间复杂度为 O(1)。