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

第C#實(shí)現(xiàn)希爾排序?qū)τ诖笠?guī)模亂序的數(shù)組，插入排序很慢，因?yàn)樗粫?huì)交換相鄰的元素，因此元素只能一點(diǎn)一點(diǎn)地從數(shù)組地一段移動(dòng)到另一端。希爾排序改進(jìn)了插入排序，交換不相鄰地元素以對(duì)數(shù)組地局部進(jìn)行排序，最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。

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

在進(jìn)行排序時(shí)，剛開始h很大，就能將元素移動(dòng)到很遠(yuǎn)的地方，為實(shí)現(xiàn)更小的h有序創(chuàng)造方便。h遞減到1時(shí)，相當(dāng)于插入排序。這就是希爾排序。下面的代碼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個(gè)有序數(shù)組）即（h0）,（h+11）,（h+22）,....

*如果右邊的值小于左邊的值時(shí)，交換；

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

*因?yàn)榻粨Q可能引起原有序的數(shù)組亂序，所以需要退回去重新比較

*當(dāng)h遞減到1時(shí)，相當(dāng)于插入排序一個(gè)部分有序數(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;

}

從另一個(gè)角度看希爾排序，插入排序是將每個(gè)比元素大的元素向右移動(dòng)一個(gè)，希爾排序是交換到比它大的元素之前，移動(dòng)距離從1改成h。

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

和選擇排序以及插入排序?qū)Ρ龋柵判蛞部梢杂糜诖笮蛿?shù)組，即使是隨機(jī)數(shù)字排序也快很多。數(shù)組規(guī)模越大，對(duì)比越明顯。希爾排序的性能分析比較困難。它的運(yùn)行時(shí)間達(dá)不到平方級(jí)別，在最壞情況下的比較次數(shù)和N^3/2成正比。如果中等大小的數(shù)組可以使用希爾排序，它代碼量少，且不需要額外的內(nèi)存空間。

百萬(wàn)級(jí)別的排序時(shí)間不超過(guò)十秒：

count:10000shelluseMilliseconds:6

count:100000shelluseMilliseconds:180

count:1000000