希尔排序是插入排序的一种，时间性能优于直接插入排序，是一种不稳定的排序，时间复杂度为 O(nlogn)。
 
基本思想
将整个无序列分割成若干小的子序列分别进行直接插入排序。
先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组。所有距离为 dl 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量 d2 < d1 重复上述的分组和排序，直至所取的增量 dt = 1 (dt < dt-l < … <d2 < d1)，即所有记录放在同一组中进行直接插入排序为止。
最后一个增量必须为 1。
当第一个增量为 1 时，就等于直接插入排序。

如下：
增量：2，分为 2 组
30 20 40 15 35 25
30 -- 40 ---35    <- 第一组
   20 -- 15 -- 25 <- 第二组
每组进行直接插入排序。
40 和 30 比较，顺序正确(第一组的有序段：30 40)
15 和 20 比较，顺序错误，20 后移，已经是最前面了，15 插入原 20 的位置(第二组的有序段：15 20)
35 和 40 比较，顺序错误，40 后移，40 前面还有数，所以还要继续比较
35 和 30 比较，顺序正确，35 找到了插入点(第一组的有序段：30 35 40)
25 和 20 比较，顺序正确(第二组的有序段：15 20 25)
到这里，第一趟结束。
第一组：30 35 40
第二组：15 20 25
30 15 35 20 40 25

例子

using System;


namespace System
{
    public class Test
    {
        public static void Main()
        {
            int[] array = new int[6] { 30, 20, 40, 15, 35, 25 };

            PrintArray(array);
            Console.WriteLine("-----------------");

            ShellSort.Sort(array);

            PrintArray(array);

            Console.ReadKey();
        }

        public static void PrintArray(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                if (i > 0) Console.Write(" ");
                Console.Write(array[i].ToString());
            }
            Console.WriteLine();
        }
    }

    public class ShellSort
    {
        public static void Sort(int[] array)
        {
            int increment = array.Length;
            do
            {
                increment = increment / 3 + 1; // 设置增量
                Sort(array, increment);
            } while (increment > 1);
        }

        public static void Sort(int[] array, int increment)
        {
            // 进行直接插入排序
            for (int i = increment; i < array.Length; i++) // 从第二个开始
            {
                if (array[i] < array[i - increment]) // 前面有大的数，需要后移
                {
                    int j = i - increment; // j 表示前面数的指针
                    int temp = array[i];
                    do
                    {
                        array[j + increment] = array[j]; // 后移元素
                        j = j - increment;
                    } while (j >= 0 && array[j] > temp); // 前面的数还是大的时，继续循环后移

                    array[j + increment] = temp; // array[i] 插入正确的位置上
                }
            }
        }
    }
}