日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
經(jīng)典四講貫通C++排序之二希爾排序

　　我們都知道C++排序方法中，有四種常用方法插入排序、希爾排序、交換排序以及選擇排序。上一篇文章，我們介紹了插入排序，今天我們介紹另一種排序方法——希爾排序。（本系列文章統(tǒng)一 測試程序）　　

　　希爾排序

　　前面的算法的平均效率都不怎么好，但我們注意到直插排序在關(guān)鍵碼基本有序的情況下，效率是***的，并且，在關(guān)鍵碼的數(shù)量很少的時候，n和n2的差距也不是那么的明顯?；谝陨系氖聦?，D.L.Shell在1959年(老古董了)提出了縮小增量排序，基本思想是：取一個間隔(gap)，將序列分成若干的子序列，對每個子序列進行直插排序;然后逐漸縮小間隔，重復(fù)以上過程，直到間隔為1。在開始的時候，每個子序列里關(guān)鍵碼很少，直插的效率很高;隨著間隔的縮小，子序列的關(guān)鍵碼越來越多，但是在前面的排序基礎(chǔ)上，關(guān)鍵碼已經(jīng)基本有序，直插的效率依然很高。

　　希爾排序的時間復(fù)雜度不好估量，gap的選取也沒有定論，gap=[gap/2]的程序是***寫的，至于為什么，寫寫就知道了。

 
 
 
    
  
  
  
  1. template   
    2. 
  
  
  
  2. void ShellSort(T a[], int N, int& KCN, int& RMN)  
    3. 
  
  
  
  3. {  
    4. 
  
  
  
  4. KCN = 0; RMN = 0;  
    5. 
  
  
  
  5. for (int gap = N/2; gap; gap = gap/2)  
    6. 
  
  
  
  6. for (int i = gap; i < N; i++)  
    7. 
  
  
  
  7. {  
    8. 
  
  
  
  8. T temp = a[i]; RMN++;  
    9. 
  
  
  
  9. for (int j = i; j >= gap && ++KCN && temp < a[j - gap]; j -= gap)  
    10. 
  
  
  
  10. { a[j] = a[j - gap]; RMN++; }  
    11. 
  
  
  
  11. a[j] = temp; RMN++;  
    12. 
  
  
  
  12. }  
    13. 
  
  
  
  13. } 
    14.

　　測試結(jié)果：

 
 
 
    
  
  
  
  1. Sort ascending N=10000 TimeSpared: 0ms  
    2. 
  
  
  
  2. KCN=120005 KCN/N=12.0005 KCN/N^2=0.00120005 KCN/NlogN=0.903128  
    3. 
  
  
  
  3. RMN=240010 RMN/N=24.001 RMN/N^2=0.0024001 RMN/NlogN=1.80626  
    4. 
  
  
  
  4. Sort randomness N=10000 TimeSpared: 10ms  
    5. 
  
  
  
  5. KCN=258935 KCN/N=25.8935 KCN/N^2=0.00258935 KCN/NlogN=1.94868  
    6. 
  
  
  
  6. RMN=383849 RMN/N=38.3849 RMN/N^2=0.00383849 RMN/NlogN=2.88875  
    7. 
  
  
  
  7. Sort descending N=10000 TimeSpared: 10ms  
    8. 
  
  
  
  8. KCN=172578 KCN/N=17.2578 KCN/N^2=0.00172578 KCN/NlogN=1.29878  
    9. 
  
  
  
  9. RMN=302570 RMN/N=30.257 RMN/N^2=0.0030257 RMN/NlogN=2.27707 
    10.

　　注意到這時的測試結(jié)果很不準確了，10000個整數(shù)的排序已經(jīng)測試不出什么來了(估計新機器都是0ms，我這里也有個別的時候全是0)。因此，下面用100000個整數(shù)的排序重新測試了一次：

 
 
 
    
  
  
  
  1. Sort ascending N=100000 TimeSpared: 140ms  
    2. 
  
  
  
  2. KCN=1500006 KCN/N=15.0001 KCN/N^2=0.000150001KCN/NlogN=0.903094  
    3. 
  
  
  
  3. RMN=3000012 RMN/N=30.0001 RMN/N^2=0.000300001RMN/NlogN=1.80619  
    4. 
  
  
  
  4. Sort randomness N=100000 TimeSpared: 230ms  
    5. 
  
  
  
  5. KCN=4041917 KCN/N=40.4192 KCN/N^2=0.000404192KCN/NlogN=2.43348  
    6. 
  
  
  
  6. RMN=5598883 RMN/N=55.9888 RMN/N^2=0.000559888RMN/NlogN=3.37086  
    7. 
  
  
  
  7. Sort descending N=100000 TimeSpared: 151ms  
    8. 
  
  
  
  8. KCN=2244585 KCN/N=22.4459 KCN/N^2=0.000224459KCN/NlogN=1.35137  
    9. 
  
  
  
  9. RMN=3844572 RMN/N=38.4457 RMN/N^2=0.000384457RMN/NlogN=2.31466 
    10.

　　這個結(jié)果表明，希爾排序幾乎沒有最壞情況，無論是正序、逆序、亂序，所用時間都不是很多，附加儲存是O(1)，的確非常不錯。在沒搞清楚快速排序、堆排序之前，它的確是個很好的選擇，我當(dāng)年一直用它。


文章標題：經(jīng)典四講貫通C++排序之二希爾排序
URL地址：http://www.5511xx.com/article/dhpjhjj.html