C#實現(xiàn)希爾排序

第C#實現(xiàn)希爾排序對于大規(guī)模亂序的數(shù)組，插入排序很慢，因為它只會交換相鄰的元素，因此元素只能一點一點地從數(shù)組地一段移動到另一端。希爾排序改進了插入排序，交換不相鄰地元素以對數(shù)組地局部進行排序，最終用插入排序將局部有序的數(shù)組排序。

希爾排序的思想是使數(shù)組中任意間隔為h的元素都是有序的。這樣的數(shù)組成為h有序數(shù)組。換句話說，一個h有序數(shù)組就是h個相互獨立的有序數(shù)組組合在一起的一個數(shù)組。

在進行排序時，剛開始h很大，就能將元素移動到很遠的地方，為實現(xiàn)更小的h有序創(chuàng)造方便。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(hn/3)

h=h*3+1;

*每次循環(huán)生成h有序數(shù)組（h個有序數(shù)組）即（h0）,（h+11）,（h+22）,....

*如果右邊的值小于左邊的值時，交換；

*并退回到左邊的位置，重新排序，循環(huán)比較（j=h）。

*因為交換可能引起原有序的數(shù)組亂序，所以需要退回去重新比較

*當h遞減到1時，相當于插入排序一個部分有序數(shù)組

**/

while(h=1)

//Console.WriteLine(h);

for(inti=h;ii++)

//Console.WriteLine(i+","+(i-h));

for(intj=i;j=hLess(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。

希爾排序更高效的原因是它將數(shù)組變成多個部分有序的數(shù)組，減少倒置。排序之初，各個子數(shù)組都很短，排序之后子數(shù)組都是部分有序的，這很適合插入排序。子數(shù)組部分有序的程度取決于遞增序列的選擇。（如何選擇？？）

和選擇排序以及插入排序對比，希爾排序也可以用于大型數(shù)組，即使是隨機數(shù)字排序也快很多。數(shù)組規(guī)模越大，對比越明顯。希爾排序的性能分析比較困難。它的運行時間達不到平方級別，在最壞情況下的比較次數(shù)和N^3/2成正比。如果中等大小的數(shù)組可以使用希爾排序，它代碼量少，且不需要額外的內存空間。

百萬級別的排序時間不超過十秒：

count:10000shelluseMilliseconds:6

count:100000shelluseMilliseconds:180

count:1000000