class ShellSort
{
    public bool Sort(int[] datas)
    {
        if (datas.Length < 1) return false;

        for (int gap = datas.Length / 2; gap > 0; gap /= 2)
        {
            for (int i = gap; i < datas.Length; i++)
            {
                //gap将集合分成几个小集合，跨着对比交换，最后gap=1时，减轻大集合的负担
                int j = i;
                while (j - gap >= 0 && datas[j] < datas[j - gap])
                {
                    //当前集合的对比，让每个跨越式的小集合都是有序的
                    swap(datas, j, j - gap);//交换两个数的值
                    j -= gap;
                }
            }
        }


        return true;
    }

    private void swap(int[] data, int a, int b)
    {
        data[a] = data[a] + data[b];
        data[b] = data[a] - data[b];
        data[a] = data[a] - data[b];
    }
}

希尔排序是在插值排序中升级的，将数组改成几个大间距的不同集合，对这些集合进行交换的排序。交换大范围的数据，当在gap缩小到1的时候，就是插值排序了，这时候序列在前面大范围的比较交换后已经有了一定的顺序了，所以只需要交换少量数据就可以完成排序了。

测试代码：

static void TestShellSort()
{
    int[] datas = { 5, 6, 9, 1, 100, 3, 7, 0, 2 };
    ShellSort shellSort = new ShellSort();
    shellSort.Sort(datas);
    foreach (var data in datas)
    {
        Console.Write(data + " ");//0 1 2 3 5 6 7 9 100
    }
}