C#算法(四)希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法.同时该算法是冲破 $O(n^2)$ 的第一批算法之一

基本思想

1. 选择一个增量序列(直到增量序列为1时)，对这些序列进行插入排序。
2. 继续缩小增量重复上述方法，直到序列变为有序为止。

希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，但其实这个增量序列不是最优的。

比较流行的增量序列: $gap=length/2$或 $gap=length/3+1$。

时间复杂度

1. 希尔排序的时间复杂度是：$O(nlogn)$～$O(n^2)$ 。
2. 希尔排序的效率是取决于它的增量序列。
3. 分析希尔排序的时间复杂度很困难，在特定情况下可以估算排序的比较和元素的移动次数，但要想弄清楚希尔排序的比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。

示例代码

using System;
namespace ShellSorter
{
    public class ShellSorter
    {
        public void Sort(int[] list)
        {
            int inc;
            for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
            for (; inc > 0; inc /= 3)
            {
                for (int i = inc + 1; i <= list.Length; i += inc)
                {
                    int t = list[i - 1];
                    int j = i;
                    while ((j > inc) && (list[j - inc - 1] > t))
                    {
                        list[j - 1] = list[j - inc - 1];
                        j -= inc;
                    }
                    list[j - 1] = t;
                }
            }
        }
    }
    public class MainClass
    {
        public static void Main()
        {
            int[] iArrary = new int[] { 1, 5, 13, 6, 10, 55, 99, 2, 87, 12, 34, 75, 33, 47 };
            ShellSorter sh = new ShellSorter();
            sh.Sort(iArrary);
            for (int m = 0; m < iArrary.Length; m++)
                Console.Write("{0} ", iArrary[m]);
            Console.WriteLine();
        }
    }
}