希爾排序法 附程式碼

比插入排序快 最少跟插入排序一樣

因為   interval最後會變為1 這時就是插入排序了

會比插入排序快的因為 

希爾排序先兩兩處裡了一些順序

interval為1時作插入排序所以可減省插入排序的時間

可以看成再插入排序前先整了一番順序

可參考此影片

int arr2[7] = {16,51,63,1,25,70,15};

    int len = 7;

    //習慣間隔是陣列長度除2 len >>1 表示除2

   for (int interval=len>>1;interval > 0;interval>>=1){

       for (int k = interval;k < len;k++){

           int target =arr2[k];

           int x = k - interval;//取得左邊與k差為interval的區間

            while(x > -1 && arr2[x] > target){

                arr2[x+interval] = arr2[x];

                x-=interval;

            }

           arr2[x+interval] =target;

       }

   }

    //java 可換成foreach 輪巡陣列

    for (auto v : arr2){

        cout << v << ' ';

    }