希尔排序(shell sort)，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。
算法思想：
先取一个增量 deltaD = n / 2，n为数组元素个数。把所有序号相隔 deltaD 的数组元素放一组，组内进行直接插入排序，
然后取 deltaD = deltaD / 2，重复上述分组和直接插入排序操作； 直至 deltaD = 1。
deltaD = 1其实就是直接插入排序，只是当前数组几乎有序。
直接插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。
void insertSort(vector<int> &array, int deltaD)
{int n = array.size();for(int i = deltaD; i < n; i++){int j = i - deltaD;int tmp = array[i];while(j >= 0 && tmp < array[j])//比插入元素大的元素进行后移操作{array[j + deltaD] = array[j];j = j - deltaD;}array[j + deltaD] = tmp;//插入要插入的元素}for(int k = 0; k < array.size(); k++){cout << array[k] << " ";}cout << endl;
}void shellSort(vector<int> array)
{int n = array.size();int d = n / 2;while(d >= 1){insertSort(array, d);d = d / 2;}for(int k = 0; k < array.size(); k++){cout << array[k] << " ";}
}