久久国产成人av_抖音国产毛片_a片网站免费观看_A片无码播放手机在线观看,色五月在线观看,亚洲精品m在线观看,女人自慰的免费网址,悠悠在线观看精品视频,一级日本片免费的,亚洲精品久,国产精品成人久久久久久久

搜索
分享

希爾排序

 太極混元天尊 2018-05-18

本文作者：靜默虛空


要點(diǎn)

希爾(Shell)排序又稱為縮小增量排序,，它是一種插入排序,。它是直接插入排序算法的一種威力加強(qiáng)版。該方法因DL．Shell于1959年提出而得名,。


希爾排序的基本思想是：

把記錄按步長 gap 分組,，對(duì)每組記錄采用直接插入排序方法進(jìn)行排序。


隨著步長逐漸減小,，所分成的組包含的記錄越來越多,，當(dāng)步長的值減小到 1 時(shí)，整個(gè)數(shù)據(jù)合成為一組,，構(gòu)成一組有序記錄,，則完成排序。


我們來通過演示圖,，更深入的理解一下這個(gè)過程,。 


在上面這幅圖中：

初始時(shí)，有一個(gè)大小為 10 的無序序列,。


在第一趟排序中,，我們不妨設(shè) gap1 = N / 2 = 5，即相隔距離為 5 的元素組成一組,，可以分為 5 組,。接下來，按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序,。


在第二趟排序中,，我們把上次的 gap 縮小一半，即 gap2 = gap1 / 2 = 2 (取整數(shù)),。這樣每相隔距離為 2 的元素組成一組,，可以分為 2 組。按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序,。


在第三趟排序中,，再次把 gap 縮小一半，即gap3 = gap2 / 2 = 1,。 這樣相隔距離為 1 的元素組成一組,，即只有一組。按照直接插入排序的方法對(duì)每個(gè)組進(jìn)行排序,。此時(shí),，排序已經(jīng)結(jié)束。


需要注意一下的是,，圖中有兩個(gè)相等數(shù)值的元素 5 和 5 ,。我們可以清楚的看到,，在排序過程中，兩個(gè)元素位置交換了,。


所以,，希爾排序是不穩(wěn)定的算法。


核心代碼

public void shellSort(int[] list) {

   int gap = list.length / 2;
 
   while (1 <= gap)="">

       // 把距離為 gap 的元素編為一個(gè)組,，掃描所有組
       for (int i = gap; i <>list.length; i++) {
           int j = 0;
           int temp = list[i];

           // 對(duì)距離為 gap 的元素組進(jìn)行排序
           for (j = i - gap; j >= 0 && temp <>list[j]; j = j - gap) {
               list[j + gap] = list[j];
           }
           list[j + gap] = temp;
       }

       System.out.format('gap = %d:\t', gap);
       printAll(list);
       gap = gap / 2; // 減小增量
   }
}


算法分析

希爾排序的算法性能


時(shí)間復(fù)雜度

步長的選擇是希爾排序的重要部分,。只要最終步長為1任何步長序列都可以工作。


算法最開始以一定的步長進(jìn)行排序,。然后會(huì)繼續(xù)以一定步長進(jìn)行排序,，最終算法以步長為1進(jìn)行排序。當(dāng)步長為1時(shí),，算法變?yōu)椴迦肱判?，這就保證了數(shù)據(jù)一定會(huì)被排序。


Donald Shell 最初建議步長選擇為N/2并且對(duì)步長取半直到步長達(dá)到1,。雖然這樣取可以比O(N2)類的算法（插入排序）更好,，但這樣仍然有減少平均時(shí)間和最差時(shí)間的余地。


可能希爾排序最重要的地方在于當(dāng)用較小步長排序后,，以前用的較大步長仍然是有序的,。比如，如果一個(gè)數(shù)列以步長5進(jìn)行了排序然后再以步長3進(jìn)行排序,，那么該數(shù)列不僅是以步長3有序,，而且是以步長5有序。如果不是這樣,，那么算法在迭代過程中會(huì)打亂以前的順序,，那就


不會(huì)以如此短的時(shí)間完成排序了。

步長序列

最壞情況下復(fù)雜度


已知的最好步長序列是由Sedgewick提出的(1, 5, 19, 41, 109,...),，該序列的項(xiàng)來自這兩個(gè)算式,。


這項(xiàng)研究也表明“比較在希爾排序中是最主要的操作，而不是交換,?！庇眠@樣步長序列的希爾排序比插入排序和堆排序都要快，甚至在小數(shù)組中比快速排序還快,，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢,。


算法穩(wěn)定性

由上文的希爾排序算法演示圖即可知，希爾排序中相等數(shù)據(jù)可能會(huì)交換位置,，所以希爾排序是不穩(wěn)定的算法,。


直接插入排序和希爾排序的比較

  • 直接插入排序是穩(wěn)定的；而希爾排序是不穩(wěn)定的。

  • 直接插入排序更適合于原始記錄基本有序的集合,。

  • 希爾排序的比較次數(shù)和移動(dòng)次數(shù)都要比直接插入排序少,，當(dāng)N越大時(shí)，效果越明顯,。 

  • 在希爾排序中,，增量序列g(shù)ap的取法必須滿足：最后一個(gè)步長必須是 1 。 

  • 直接插入排序也適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),；希爾排序不適用于鏈?zhǔn)浇Y(jié)構(gòu),。


完整參考代碼

JAVA版本代碼實(shí)現(xiàn)(范例代碼中的初始序列和本文圖示中的序列完全一致)。

package notes.javase.algorithm.sort;

public class ShellSort {
   public void shellSort(int[] list) {
       int gap = list.length / 2;

       while (1 <= gap)="">
           // 把距離為 gap 的元素編為一個(gè)組,，掃描所有組
           for (int i = gap; i <>list.length; i++) {
               int j = 0;
               int temp = list[i];

               // 對(duì)距離為 gap 的元素組進(jìn)行排序
               for (j = i - gap; j >= 0 && temp <>list[j]; j = j - gap) {
                   list[j + gap] = list[j];
               }
               list[j + gap] = temp;
           }

           System.out.format('gap = %d:\t', gap);
           printAll(list);
           gap = gap / 2; // 減小增量
       }
   }

   // 打印完整序列
   public void printAll(int[] list) {
       for (int value : list) {
           System.out.print(value + '\t');
       }
       System.out.println();
   }

   public static void main(String[] args) {
       int[] array = {
               9, 1, 2, 5, 7, 4, 8, 6, 3, 5
       };

       // 調(diào)用希爾排序方法
       ShellSort shell = new ShellSort();
       System.out.print('排序前:\t\t');
       shell.printAll(array);
       shell.shellSort(array);
       System.out.print('排序后:\t\t');
       shell.printAll(array);
   }
}


運(yùn)行結(jié)果

排序前:     9    1    2    5    7    4    8    6    3    5    
gap = 5:    4    1    2    3    5    9    8    6    5    7    
gap = 2:    2    1    4    3    5    6    5    7    8    9    
gap = 1:    1    2    3    4    5    5    6    7    8    9    
排序后:      1    2    3    4    5    5    6    7    8    9


參考資料

  • 《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》（B級(jí)第3版）

  • 維基百科-希爾排序：http://zh./zh-cn/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F


排序系列文章


關(guān)注算法文摘，修煉開發(fā)內(nèi)功

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購買等信息,，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請(qǐng)點(diǎn)擊一鍵舉報(bào),。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多