希尔排序（Shell’s Sort）又称“缩小增量排序”（Diminishing Increment Sort），它也是一种属于插入排序类的方法，但在时间效率上较前述几种排序方法有较大的改进。时间复杂度为O(n^3/2)。理解：先将整个待排记录序列分割成为若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
void CInsertionSort::ShellSort(void)
{
const int count = 9, length = count -1;
int L[count] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
const int t = 3;
int dlta[t] = {3, 2 , 1};
for (int k = 0; k < t; ++k)
{
ShellInsert(L, length, dlta[k]);
}
//打印排序结果。
for (int i = 0; i <= length; ++ i)
{
cout << L[i] << "\t";
}
cout << endl;
}
void CInsertionSort::ShellInsert(int L[], int length, int dk)
{
for (int i = dk + 1; i <= length; ++ i)
{
if (L[i] < L[i - dk])
{
L[0] = L[i];
int j = i - dk;
while (j > 0 && L[0] < L[j])
{
L[j + dk] = L[j];
j -= dk;
}
L[j + dk] = L[0];
}
}
}
和直接排序差不多，只不过是先三三比较，再两两比较，即第一轮[4]和[1]比较，[5]和[2]，[6]和[3]，[7]和[4]，[8]和[5]。简单来说是这样来比较，复杂来说，这只是第一轮的第一次比较，如果符合条件还会进行第一轮的第二次比较。即for循环的while子循环。把数值代进来用大脑跑一下就OK了。