希尔排序

希尔排序是一种插入排序的改进版。最坏情况下的时间复杂度是O(n²)，平均时间复杂度可以达到 O(nlogn)。

【输入描述】

输入两行。第一行输入数组大小 n ，第二行输入 n 个数字。

【输出描述】

输出一行。输出排序后的数字。

【输入样例】

8
7 13 4 5 8 1 11 9
【输出样例】

1 4 5 7 8 9 11 13
【参考程序】

// 小牛编程
#include <iostream>
using namespace std;

int arr[10001];

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

    // 输入数组元素
    int arr[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;
            while (j >= gap && arr[j - gap] > key) { //降序改成<
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }

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

    return 0;
}

经典算法

希尔排序