感謝部落客 http://www.cnblogs.com/90zeng/p/shell_sort.html
1.原理介紹
希爾排序又稱為縮小增量排序，由D.L.Shell在1959年提出而得名。
該算法先取一個小于資料表中元素個數 n 的整數gap, 并以此作為第一個間隔，将資料分為gap個子序列，所有距離為gap的對象存放在同一個子序列中，于是資料表中的元素就被分成了gap個組，分組确定後，在每一個小組中進行直接插入排序，局部排序完成後，縮小gap, 重複上述步驟，直至取到gap=1時，完成最後一次直接插入排序。
為什麼這個算法會起作用：開始的時候gap較大，子序列中的資料較少，是以最開始的時候算法運作較快，随着算法進行，gap 逐漸變小，子序列中元素的個數也就越來越多，是以排序工作可能會變慢，但是由于前面已經完成了部分排序工作，因而在很大程度上減輕了後來的工作量，于是最終總體的排序速度還是比較快的。
2.舉例說明
資料表：
第一輪：資料表共有6個元素，初始化gap = 6, 第一輪取取gap = MT(gap/2)=3,注意這裡MT(X)表示取不小于X的最小整數，即向上取整！
第二輪：gap = MT(gap/2)=2;
第三輪：gap = MT(gap/2) = 1,但是由于第二輪結束後資料表實際上已經有序了，是以第三輪做的事幾乎為0.
3.C++實作
1 #ifndef SHELLSORT_H
2 #define SHELLSORT_H
3 #include <vector>
4 #include <iostream>
5 using std::vector;
6 using std::cout;
7 using std::endl;
8
9 template <typename T>
10 class ShellSort
11 {
12 private:
13 unsigned len;
14 vector<T> list;
15 public:
16 /*
17 * Construction function
18 */
19 ShellSort(vector<T> _list, unsigned _len)
20 {
21 for (unsigned i = 0; i < _len; ++i) list.push_back(_list[i]);
22 this->len = _len;
23 }
24 /*
25 * Shellsort function
26 */
27 void shellSort()
28 {
29 int insertNum;
30 unsigned gap = len/2; // initial increment
31 while(gap) // while gap>=1
32 {
33 for (unsigned i = gap; i < len; ++i) // Insertsort within subsequence
34 {
35 insertNum = list[i];//Target number to be inserted into the subsequence
36 unsigned j = i;
37 while (j >= gap && insertNum < list[j-gap])//Find position
38 {
39 list[j] = list[j - gap];
40 j -= gap;
41 }
42 list[j] = insertNum;
43 }//end for
44 gap /= 2;
45 }//end while(gap)
46 }// end shellSort
47
48 /*
49 * Display the sorted result
50 */
51 void out()
52 {
53 for (unsigned i = 0; i < len; ++i)
54 {
55 cout << list[i] << " ";
56 if ((i + 1) % 18 == 0) cout << endl;
57 }
58 cout << endl;
59 }
60 };
61 #endif
62
63 //shellSortTest
64 #include "ShellSort.h"
65 #include <vector>
66 using namespace std;
67
68 const unsigned numEle = 8;
69 int data[numEle] = {1,5,7,3,8,2,6,4};
70
71
72 int main()
73 {
74 vector<int> testData;
75 for (unsigned i = 0; i < numEle; ++i) testData.push_back(data[i]);
76
77 ShellSort<int> test(testData, numEle);
78 test.shellSort();
79 test.out();
80 return 0;
81 } 4.參考文獻
左飛：C++資料結構原理與經典問題求解
請尊重原創知識，本人非常願意與大家分享 轉載請注明出處：http://www.cnblogs.com/90zeng/ 作者：部落格園-太白路上的小混混