题解 | #争夺前五名#

#include <iostream>
using namespace std;


void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1; // log 3 N
        //每次排gap次
        for (int j = 0; j < n - gap; j++) {
            //插入排序
            int end = j;
            int tmp = a[end + gap];
            while (end >= 0) {
                if (tmp > a[end]) {
                    a[end + gap] = a[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}
int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    // 排序
    ShellSort(arr, n);
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << ' ';
    }
}