C#实现希尔排序

对于大规模乱序的数组，插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组地一段移动到另一端。希尔排序改进了插入排序，交换不相邻地元素以对数组地局部进行排序，最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组成为 h 有序数组。换句话说，一个 h 有序数组就是 h 个相互独立的有序数组组合在一起的一个数组。

在进行排序时，刚开始 h 很大，就能将元素移动到很远的地方，为实现更小的 h 有序创造方便。h 递减到 1 时，相当于插入排序。这就是希尔排序。下面的代码 h 从 N/3 开始递减，h = h * 3 + 1:

public class Shell: BaseSort
   {
       public static long usedTimes = 0;
       public Shell()
       {
       }

public static void Sort(IComparable[] a)
       {
           Stopwatch timer = new Stopwatch();
           timer.Start();
           int n = a.Length;
           int h = 1;
           while (h < n / 3)
               h = h * 3 + 1;

/*
            * 每次循环生成 h有序数组（h 个有序数组） 即 （h 0）, （h+1 1）, （h+2 2）, ....
            *      如果右边的值小于左边的值时，交换；
            *      并退回到左边的位置，重新排序，循环比较（j>=h）。
            *      因为交换可能引起原有序的数组乱序，所以需要退回去重新比较
            * 当 h 递减到 1时，相当于插入排序一个部分有序数组
            * */
           while (h >= 1)
           {
               //Console.WriteLine(h);
               for (int i = h; i < n; i++)
               {
                   //Console.WriteLine(i+","+(i - h));
                   for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
                   {
                       Exch(a,j,j-h);
                       //Console.WriteLine("J:" + (j- h));
                   }
               }
               h = h / 3;
           }

timer.Stop();
           usedTimes = timer.ElapsedMilliseconds;
       }
   }

从另一个角度看希尔排序，插入排序是将每个比元素大的元素向右移动一个，希尔排序是交换到比它大的元素之前，移动距离从 1 改成 h 。

希尔排序更高效的原因是它将数组变成多个部分有序的数组，减少倒置。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这很适合插入排序。子数组部分有序的程度取决于递增序列的选择。（如何选择？？）

• 和选择排序以及插入排序对比，希尔排序也可以用于大型数组，即使是随机数字排序也快很多。数组规模越大，对比越明显。

• 希尔排序的性能分析比较困难。它的运行时间达不到平方级别，在最坏情况下的比较次数和  N ^ 3/2 成正比。

• 如果中等大小的数组可以使用希尔排序，它代码量少，且不需要额外的内存空间。

百万级别的排序时间不超过十秒：

count:10000 shell use Milliseconds:6
count:100000 shell use Milliseconds:180
count:1000000 shell use Milliseconds:3226

来源：https://www.cnblogs.com/afei-24/p/13338901.html