shell排序

SHELL排序是直接插入法排序的一种改建，直接插入法一趟只处理一个数，其他数的信息未被处理。
SHELL排序的核心思想是：
（1）把待排序列分为n个组，每个组内部执行一次插入排序；
（2）减小n值，重新分组，每组内部执行一次插入排序；直到n=1，执行插入排序后完成。

例如，待排序列：
1    9    2    7    35    0    3    8 （长度8）

第一轮：
按常见的序列长度2折法分组，第一次分为 4组（ 8 / 2 )
1， 35  ——  1， 35
9， 0    ——  0， 9
2， 3    ——  2， 3
7， 8    ——  7， 8
第一轮分组，执行插入排序后：
1    0    2    7     35    9    3    8

第二轮：
第二轮分组为2（4 / 2）
1， 2， 35， 3  ——  1， 2， 3， 35
0， 7， 9， 8 —— 0， 7， 8， 9
第二轮分组，执行插入排序后：
1    0    2    7    3    8    35    9

第三轮：
第三分组为1 （2 / 2)
1， 0， 2， 7， 3， 8， 35， 9  ——  0， 1， 2， 3， 7， 8， 9， 35

SHELL排序是一种不稳定的排序算法，文献表明其时间复杂度受增量序列的影响明显大于其他因素，最坏的情况是o(n2)，好的情况在o(n1.3)，与增量序列选择有关。
下面是一种实现（增序）：

void shellSort(int list[], int len)
{
    int increment = len / 2;

    int insertKey;
    int cursor;
    int i,j;

    for (increment = len / 2; increment > 0; increment /= 2) //按长度2折法分组，直到增量为1
    {
        for (i = 0; i < increment; i++) // 循环处理每一组
        {
            for (j = i + increment; j < len; j += increment)// 每组内部执行插入排序
            {
                insertKey = list[j];
                cursor = j - increment;

                while (cursor >= i && list[cursor] > insertKey)
                {
                    list[cursor + increment] = list[cursor];
                    cursor -= increment;
                }
                list[cursor + increment] = insertKey;
            }
        }
    }
}