希尔排序（ShellSort）是以它的发明者Donald Shell名字命名的，希尔排序是插入排序的改进版，实现简单，对于中等规模数据的性能表现还不错。
首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。
下面有颜色的是逻辑上的分组，并没有实际地进行分组操作，在数组中的位置还是原来的样子，只是将他们看成这么几个分组（逻辑上分组）
可以看出，他是按下标相隔距离为4分的组，也就是说把下标相差4的分到一组，比如这个例子中a[0]与a[4]是一组、a[1]与a[5]是一组...，这里的差值（距离）被称为增量。
每个分组进行插入排序后，各个分组就变成了有序的了（整体不一定有序）
此时，整个数组变的部分有序了（有序程度可能不是很高）
然后缩小增量为上个增量的一半:2，继续划分分组，此时，每个分组元素个数多了，但是，数组变的部分有序了，插入排序效率同样比较高
同理对每个分组进行排序（插入排序），使其每个分组各自有序
最后设置增量为上一个增量的一半：1，则整个数组被分为一组，此时，整个数组已经接近有序了，插入排序效率高
同理，对这仅有的一组数据进行排序，排序完成
代码实现：
#include<iostream> using namespace std; #define N 9 void insertI(int a[], int gap, int i) { int j, inserted = a[i]; for (j = i - gap; j >= 0 && inserted < a[j]; j -= gap) { a[j + gap] = a[j]; } a[j + gap] = inserted; } void shell_sort(int a[]) { for (int gap = N / 2; gap > 0; gap /= 2) { for (int i = gap; i < N; i++) { insertI(a, gap, i); } } } void main() { int array[] = {5,7,8,3,1,2,4,6,10}; shell_sort(array); for (int i = 0; i < N; i++) { cout << array[i] <<" "; } cout << endl; }代码输出结果：
1 2 3 4 5 6 7 8 10
