希尔排序（Shell Sort）又称为缩小增量排序，输入插入排序算法，是对直接排序算法的一种改进。本文介绍希尔排序算法。
对于插入排序算法来说，如果原来的数据就是有序的，那么数据就不需要移动，而插入排序算法的效率主要消耗在数据的移动中。因此可知：如果数据的本身就是有序的或者本身基本有序，那么效率就会得到提高。
希尔排序的基本思想是：将需要排序的序列划分成为若干个较小的子序列，对子序列进行插入排序，通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。
在希尔排序中首先解决的是子序列的选择问题。对于子序列的构成不是简单的分段，而是采取相隔某个增量的数据组成一个序列。增量一般的选择原则是：取上一个增量的一半作为此次序列的划分增量。首次选择序列长度的一半为增量。
先假如：数组的长度为10，数组元素为：25、19、6、58、34、10、7、98、160、0
整个希尔排序的算法过程如下如所示：
上图是原始数据和第一次选择的增量 d = 5。本次排序的结果如下图： 
上图是第一次排序的结果，本次选择增量为 d=2。 本次排序的结果如下图： 
当d=1 是进行最后一次排序，本次排序相当于冒泡排序的某一次循环。最终结果如下： 
在实际使用过程中，带排序的数据肯定不是只有十个，但是上述是希尔排序的思想。其实希尔排序只是插入排序的一种优化。
C++实现希尔排序的代码如下所示：
#include<iostream>
using namespace std;
void shell_sort(int array[] , int length)
{
int i , j , temp;
int d = length/2; // 设置希尔排序的初始增量
while(d >= 1)
{
for(i = d ; i < length ; ++i)
{
temp = array[i];
j = i - d; // 步长为d的前面一个位置
while(j >= 0 && array[j] > temp) // 从后往前进行插入排序
{
array[j + d] = array[j];
j -= d;
}
array[j + d] = temp; // 找到了插入位置
}
d /= 2;
}
}
int main(void)
{
int i , a[]={25,19,6,58,34,10,7,98,160,0};
shell_sort(a , 10);
for(i = 0 ; i < 10 ; ++i)
cout<<a[i]<<" ";
cout<<endl;
system("pause");
return 0;
}
