//
// Created by tangs on 2018/11/18.
//

#include <iostream>

using namespace std;

// 抄书的算法;
// 希尔排序的时间复杂度涉及到一个未解决的数学难题，当n在某个范围内时，可以达到O(n^1.3).
// 最坏的时候为O(n^2).
void ShellSort(int A[], int n) {
    int dk, i, j;
    for (dk = n / 2; dk >= 1; dk /= 2) {
        for (i = dk ; i < n; i++) {
            if (A[i] < A[i - dk]) {
                A[0] = A[i];
                for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk) {
                    A[j + dk] = A[j];
                }
                A[j + dk] = A[0];
            }
        }
    }
}

void ShellSortBySelf(int A[], int n) {
    int dk, i, j;
    int temp;
    for (dk = n / 2; dk >= 1; dk /= 2) {
        for (i = dk; i < n; i++) {
            if (A[i] < A[i - dk]) {
                temp = A[i];
                for (j = i-dk; j >= 0 && A[j]>temp; j -= dk) {
                    A[j + dk] = A[j];
                }
                A[j + dk] = temp;
            }
        }
    }
}

int main(){
    int A1[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0};
    ShellSort(A1, 10);

    // print:
    // 0 0 1 1 2 5 7 9 10 24
    for (int i = 0; i < 10; i++) {
        cout << A1[i] << " ";
    }
    cout << endl;

    // --------------------------------------------------------------------------

    int A2[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0};
    ShellSortBySelf(A2, 10);

    // print:
    // 0 1 1 2 5 6 7 9 10 24
    for (int i = 0; i < 10; i++) {
        cout << A2[i] << " ";
    }
    cout << endl;

    return 0;
}