C#實現(xiàn)希爾排序
對于大規(guī)模亂序的數組，插入排序很慢，因為它只會交換相鄰的元素，因此元素只能一點一點地從數組地一段移動到另一端。希爾排序改進了插入排序，交換不相鄰地元素以對數組地局部進行排序，最終用插入排序將局部有序的數組排序。
希爾排序的思想是使數組中任意間隔為 h 的元素都是有序的。這樣的數組成為 h 有序數組。換句話說，一個 h 有序數組就是 h 個相互獨立的有序數組組合在一起的一個數組。
在進行排序時，剛開始 h 很大，就能將元素移動到很遠的地方，為實現(xiàn)更小的 h 有序創(chuàng)造方便。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;
/*
* 每次循環(huán)生成 h有序數組（h 個有序數組） 即 （h 0）, （h+1 1）, （h+2 2）, ....
* 如果右邊的值小于左邊的值時，交換；
* 并退回到左邊的位置，重新排序，循環(huán)比較（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 。
希爾排序更高效的原因是它將數組變成多個部分有序的數組，減少倒置。排序之初，各個子數組都很短，排序之后子數組都是部分有序的，這很適合插入排序。子數組部分有序的程度取決于遞增序列的選擇。（如何選擇？？）
- 和選擇排序以及插入排序對比，希爾排序也可以用于大型數組，即使是隨機數字排序也快很多。數組規(guī)模越大，對比越明顯。
- 希爾排序的性能分析比較困難。它的運行時間達不到平方級別，在最壞情況下的比較次數和 N ^ 3/2 成正比。
- 如果中等大小的數組可以使用希爾排序，它代碼量少，且不需要額外的內存空間。
百萬級別的排序時間不超過十秒：
count:10000 shell use Milliseconds:6
count:100000 shell use Milliseconds:180
count:1000000 shell use Milliseconds:3226
到此這篇關于C#實現(xiàn)希爾排序的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
C#實現(xiàn)壓縮和解壓縮的方法示例【Gzip和Zip方式】
這篇文章主要介紹了C#實現(xiàn)壓縮和解壓縮的方法,結合具體實例形式分析了Gzip和Zip兩種壓縮操作實現(xiàn)方法,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了C#中跨線程訪問控件問題解決方案，有需要的朋友可以參考一下2013-11-11
如何使用C#將Tensorflow訓練的.pb文件用在生產環(huán)境詳解
這篇文章主要給大家介紹了關于如何使用C#將Tensorflow訓練的.pb文件用在生產環(huán)境的相關資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考借鑒，下面隨著小編來一起學習學習吧2018-11-11
C#使用System.Net.Mail類實現(xiàn)郵件發(fā)送
這篇文章介紹了C#使用System.Net.Mail類實現(xiàn)郵件發(fā)送的方法，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-07-07
這篇文章主要介紹了C#實現(xiàn)簡單獲取及設置Session類,涉及C#針對session的設置及獲取的技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-03-03
Unity3D 計時器的實現(xiàn)代碼(三種寫法總結)
這篇文章主要介紹了Unity3D 計時器的實現(xiàn)代碼，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
在WPF應用程序中，RadioButton控件是一種常用的用戶界面元素，本文主要介紹了C#?WPF中RadioButton控件的用法及應用場景，具有一定的參考價值，感興趣的可以了解一下2024-03-03
C#中使用IrisSkin2.dll美化WinForm程序界面的方法
這篇文章主要介紹了c#中使用IrisSkin2.dll美化WinForm程序界面的實現(xiàn)方法，需要的朋友可以參考下2013-05-05
這篇文章主要介紹了使用windows控制臺調試服務的方法,需要的朋友可以參考下2014-02-02
c#?理解csredis庫實現(xiàn)分布式鎖的詳細流程
這篇文章主要介紹了c#?理解csredis實現(xiàn)分布式鎖,該庫本身已經足夠完善，這里我畫蛇添足一下，為了方便自己的使用，本文通過實例代碼給大家詳細介紹，需要的朋友可以參考下2022-02-02