希爾排序的實(shí)質(zhì)就是分組插入排序,，該方法又稱縮小增量排序,，因DL．Shell于1959年提出而得名。

該方法的基本思想是：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序,，然后依次縮減增量再進(jìn)行排序,，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí),，再對全體元素進(jìn)行一次直接插入排序,。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的,，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高,。

以n=10的一個(gè)數(shù)組49, 38, 65, 97, 26, 13, 27, 49, 55, 4為例

第一次 gap = 10 / 2 = 5

49   38   65   97   26   13   27   49   55   4

1A                                                  1B

           2A                                                   2B

                     3A                                                    3B

                                 4A                                                   4B

                                            5A                                                  5B

1A,1B，2A,2B等為分組標(biāo)記,，數(shù)字相同的表示在同一組,，大寫字母表示是該組的第幾個(gè)元素， 每次對同一組的數(shù)據(jù)進(jìn)行直接插入排序,。即分成了五組(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)這樣每組排序后就變成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26),，下同。

第二次 gap = 5 / 2 = 2

排序后

13   27   49   55   4    49   38   65   97   26

1A                 1B                 1C                 1D               1E

           2A                2B                 2C                 2D                2E

第三次 gap = 2 / 2 = 1

4   26   13   27   38    49   49   55   97   65

1A    1B      1C     1D        1E       1F       1G      1H       1I       1J

第四次 gap = 1 / 2 = 0 排序完成得到數(shù)組：

4   13   26   27   38    49   49   55   65   97

下面給出嚴(yán)格按照定義來寫的希爾排序

void shellsort1(int a[], int n)

{

       int i, j, gap;

       for (gap = n / 2; gap > 0; gap /= 2)   //步長

              for (i = 0; i < gap; i++)         //按組排序    

              {

                     for (j = i + gap; j < n; j += gap)  

                     {

                            if (a[j] < a[j - gap])

                            {

                                   int temp = a[j];

                                   int k = j - gap;

                                   while (k >= 0 && a[k] > temp)

                                   {

                                          a[k + gap] = a[k];

                                          k -= gap;

                                   }

                                   a[k + gap] = temp;

                            }

                     }

}

}

很明顯,，上面的shellsort1代碼雖然對直觀的理解希爾排序有幫助,，但代碼量太大了，不夠簡潔清晰,。因此進(jìn)行下改進(jìn)和優(yōu)化,，以第二次排序?yàn)槔瓉硎敲看螐?/SPAN>1A到1E,，從2A到2E,，可以改成從1B開始,，先和1A比較,，然后取2B與2A比較，再取1C與前面自己組內(nèi)的數(shù)據(jù)比較…….,。這種每次從數(shù)組第gap個(gè)元素開始,，每個(gè)元素與自己組內(nèi)的數(shù)據(jù)進(jìn)行直接插入排序顯然也是正確的。

void shellsort2(int a[], int n)

{

       int j, gap;

       for (gap = n / 2; gap > 0; gap /= 2)

              for (j = gap; j < n; j++)   //從數(shù)組第gap個(gè)元素開始

                     if (a[j] < a[j - gap])  //每個(gè)元素與自己組內(nèi)的數(shù)據(jù)進(jìn)行直接插入排序      

                     {

                            int temp = a[j];

                            int k = j - gap;

                            while (k >= 0 && a[k] > temp)

                            {

                                   a[k + gap] = a[k];

                                   k -= gap;

                            }

                            a[k + gap] = temp;

                     }

}

再將直接插入排序部分用 白話經(jīng)典算法系列之二 直接插入排序的三種實(shí)現(xiàn) 中直接插入排序的第三種方法來改寫下：

void shellsort3(int a[], int n)

{

       int i, j, gap;

       for (gap = n / 2; gap > 0; gap /= 2)

              for (i = gap; i < n; i++)

                     for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)

                            Swap(a[j], a[j + gap]);

}

這樣代碼就變得非常簡潔了,。

附注：上面希爾排序的步長選擇都是從n/2開始,，每次再減半，直到最后為1,。其實(shí)也可以有另外的更高效的步長選擇,，如果讀者有興趣了解,，請參閱維基百科上對希爾排序步長的說明：