希尔排序: 针对插入排序的改进，缩小增量的思想，非稳定排序
希尔排序(Shell sort)也称“缩小增量排序”。它的做法不是每次一个元素挨一个元素的比较。而是先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。这样大大减少了记录移动次数，提高了排序效率。
算法思路：先取一个正整数d1（d1＜n），把全部记录分成d1个组，所有距离为dl的倍数的记录看成是一组，然后在各组内进行插入排序；接着取d2（d2＜d1），重复上述分组和排序操作；直到di=1 (i＞＝1)，即所有记录成为一个组为止。希尔排序对增量序列的选择没有严格规定，一般选d1约为n／2，d2为d1／2，d3为d2／2，…，di＝1。
在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插人排序有较大的改进。
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
void
shell_sort(int *array, int len)
{
int i, j, step, backup;
for(step=len>>1; step>0; step>>=1) {
for(i=step; i<len; ++i) {
backup = array[i];
for(j=i-step; j>=0 && array[j]>backup; j-=step)
array[j+step] = array[j];
array[j+step] = backup;
}
}
}