希尔排序是一种插入排序的改进版。

最坏情况下的时间复杂度是O(n²)，平均时间复杂度可以达到 O(nlogn)。

【输入样例】

8
7 13 4 5 8 1 11 9

【输出样例】

1 4 5 7 8 9 11 13

【参考程序】

//爱码岛编程
#include <iostream>
using namespace std;

// { 7, 13, 4, 5, 8, 1, 11, 9 }
int arr[10005];

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

    // 输入数组元素
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 希尔排序（升序）
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > key) { //降序 <
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = key;
        }
    }

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

    return 0;
}