/* * 希尔排序（在具有几万组数据量排序时有较好的表现~） * 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();}