希爾排序

希爾排序

（摘自wiki） 一個更好理解的希爾排序實現：將數組列在一個表中並對列排序。重復這過程，不過每次用更長的列來進行。最後整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身僅僅對原數組進行排序（通過增加索引的步長，例如是用i += step_size而不是i++）。

例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然後我們對每列進行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

將上述四行數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了，然後再以3為步長進行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之後變為：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最後以1步長進行排序（此時就是簡單的插入排序了）。

#include
using namespace std;
void shellsort(int a[],int N)//希爾排序
{
    int gap;
    int tmp;
    int p;
    int j;
    for (gap = N/2; gap > 0; gap = gap/2)//這裡采用的是最原始的步長1/2
        for ( p = gap; p < N ; p++)
        {
            tmp = a[p];
            for (j = p; j >= gap && tmp < a[j- gap]; j = j - gap)
                a[j] = a[j-gap];
            a[j] = tmp;
        }
}
int main()
{
    int a[]={54,3,2,1,-9};
    shellsort(a , 5);
    for(int i=0;i

已知的最好步長序列是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，該序列的項來自  和  這兩個算式