id:317】【20分】C. DS排序--希尔排序 时间限制 1s 内存限制 128MB 题目描述 给出一个数据序列，使用希尔排序算法进行降序排序。 间隔gap使用序列长度循环除2直到1 输入 第一行输入t，表示有t个测试示例 第二行输入n，表示第一个示例有n个数据(n>1) 第三行输入n个数据，都是正整数，数据之间用空格隔开 以此类推 输出 对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。

以下是希尔排序的实现方式，可以输出每一趟排序的结果：

#include <iostream>
#include <vector>
using namespace std;

void shellSort(vector<int>& arr, int n) {
    // 计算间隔序列
    int gap = n / 2;
    while (gap > 0) {
        // 对间隔为 gap 的子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i - gap; j >= 0 && arr[j] < temp; j -= gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }

        // 输出本趟排序结果
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;

        // 更新间隔
        gap /= 2;
    }
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        shellSort(arr, n);

        if (t > 0) {
            cout << endl;
        }
    }

    return 0;
}

对于每组测试数据，先读入数组，然后使用希尔排序进行排序，并输出每一趟排序的结果。最后注意在不同组测试数据之间输出一个空行即可。