C#如何实现希尔排序

魁首哥

作者

C#如何实现希尔排序

本篇内容主要讲解“C#如何实现希尔排序”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C#如何实现希尔排序”吧!

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

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

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

publicclassShell:BaseSort{publicstaticlongusedTimes=0;publicShell(){}publicstaticvoidSort(IComparable[]a){Stopwatchtimer=newStopwatch();timer.Start();intn=a.Length;inth=1;while(h<n/3)h=h*3+1;/**每次循环生成h有序数组（h个有序数组）即（h0）,（h+11）,（h+22）,....*如果右边的值小于左边的值时，交换；*并退回到左边的位置，重新排序，循环比较（j>=h）。*因为交换可能引起原有序的数组乱序，所以需要退回去重新比较*当h递减到1时，相当于插入排序一个部分有序数组**/while(h>=1){//Console.WriteLine(h);for(inti=h;i<n;i++){//Console.WriteLine(i+","+(i-h));for(intj=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 。

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