/*
 * 希尔排序（在具有几万组数据量排序时有较好的表现~）
 * 1.希尔排序的整体时间复杂度与增量序列的选取有关，目前没有统一的最优增量序列。
 * 2.Sedgewick增量序列：{1,5,19,41,109，。。} 按照 9*4^i-9*2^i+1或4^i-3*2^i+1进行选取。
   猜想时间复杂度： 平均：O(n^6/7) 最坏： O(n*4/3)..
 */
#include "iostream"
using namespace std;    
int N = 10;
int a[10] = { 3,2,1,5,7,6,9,8,2,0 };
void shellSort() {
    int si, d, p, i;
    int Sedgewick[] = { 929,505,209,41,19,5,1,0 };
    for (si = 0; Sedgewick[si] >= N; si++); /* 初始的sedgeWick[si]不能超过排序数组的长度 */ 

        for (d = Sedgewick[si]; d > 0; d = Sedgewick[++si])
            for (p = d; p < N; p++) { /* 插入排序 */
                int temp = a[p];
                for (i = p; i >= d&& a[i - d] > temp; i -= d)
                    a[i] = a[i - d];
                a[i] = temp;
            }
}
void print() {
    for (int i = 0; i < N; i++)
        cout << a[i] << " ";
    cout << endl;
}
int main() {
    shellSort();
    print();
}