不得不知的排序四：希爾排序

滄瀟雨浪 2018-07-25

展開(kāi)全文

每日英文
I once heard that，the only thing you can do when you no longer have something is not to forget.
我曾經(jīng)聽(tīng)人說(shuō)過(guò)，當(dāng)你不能再擁有的時(shí)候，唯一可以做的就是令自己不要忘記。
樂(lè)樂(lè)有話說(shuō)
不做金錢的奴隸，非要以毒攻毒，擁有許多錢才行。不為名利支配，也得有若干名利才能說(shuō)這樣的話。

來(lái)自：靜默虛空

鏈接：cnblogs.com/jingmoxukong/p/4303279.html

圖片來(lái)自網(wǎng)絡(luò)

排序算法系列

不得不知的排序一：冒泡排序
不得不知的排序二：快速排序
不得不知的排序三：直接插入排序

要點(diǎn)

希爾(Shell)排序又稱為縮小增量排序，它是一種插入排序。它是直接插入排序算法的一種威力加強(qiáng)版。

該方法因DL．Shell于1959年提出而得名。

希爾排序的基本思想是：

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

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

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

在上面這幅圖中：

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

在第一趟排序中，我們不妨設(shè) gap1 = N / 2 = 5，即相隔距離為 5 的元素組成一組，可以分為 5 組。

接下來(lái)，按照直接插入排序的方法對(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 。我們可以清楚的看到，在排序過(guò)程中，兩個(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ù)雜度

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

算法最開(kāi)始以一定的步長(zhǎng)進(jìn)行排序。然后會(huì)繼續(xù)以一定步長(zhǎng)進(jìn)行排序，最終算法以步長(zhǎng)為1進(jìn)行排序。當(dāng)步長(zhǎng)為1時(shí)，算法變?yōu)椴迦肱判?，這就保證了數(shù)據(jù)一定會(huì)被排序。
Donald Shell 最初建議步長(zhǎng)選擇為N/2并且對(duì)步長(zhǎng)取半直到步長(zhǎng)達(dá)到1。雖然這樣取可以比O(N2)類的算法（插入排序）更好，但這樣仍然有減少平均時(shí)間和最差時(shí)間的余地?？赡芟柵判蜃钪匾牡胤皆谟诋?dāng)用較小步長(zhǎng)排序后，以前用的較大步長(zhǎng)仍然是有序的。比如，如果一個(gè)數(shù)列以步長(zhǎng)5進(jìn)行了排序然后再以步長(zhǎng)3進(jìn)行排序，那么該數(shù)列不僅是以步長(zhǎng)3有序，而且是以步長(zhǎng)5有序。如果不是這樣，那么算法在迭代過(guò)程中會(huì)打亂以前的順序，那就

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

已知的最好步長(zhǎng)序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)，該序列的項(xiàng)來(lái)自

這兩個(gè)算式。

這項(xiàng)研究也表明“比較在希爾排序中是最主要的操作，而不是交換?！庇眠@樣步長(zhǎ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è)步長(zhǎng)必須是 1。

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

完整參考代碼

JAVA版本

代碼實(shí)現(xiàn)

范例代碼中的初始序列和本文圖示中的序列完全一致。

 1 package notes.javase.algorithm.sort;
 2  
 3 public class ShellSort {
 4     public void shellSort(int[] list) {
 5         int gap = list.length / 2;
 6  
 7         while (1 <= gap) {
 8             // 把距離為 gap 的元素編為一個(gè)組，掃描所有組
 9             for (int i = gap; i < list.length; i  ) {
10                 int j = 0;
11                 int temp = list[i];
12  
13                 // 對(duì)距離為 gap 的元素組進(jìn)行排序
14                 for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
15                     list[j   gap] = list[j];
16                 }
17                 list[j   gap] = temp;
18             }
19  
20             System.out.format('gap = %d:\t', gap);
21             printAll(list);
22             gap = gap / 2; // 減小增量
23         }
24     }
25  
26     // 打印完整序列
27     public void printAll(int[] list) {
28         for (int value : list) {
29             System.out.print(value   '\t');
30         }
31         System.out.println();
32     }
33  
34     public static void main(String[] args) {
35         int[] array = {
36                 9, 1, 2, 5, 7, 4, 8, 6, 3, 5
37         };
38  
39         // 調(diào)用希爾排序方法
40         ShellSort shell = new ShellSort();
41         System.out.print('排序前:\t\t');
42         shell.printAll(array);
43         shell.shellSort(array);
44         System.out.print('排序后:\t\t');
45         shell.printAll(array);
46     }
47 }

運(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

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

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自：滄瀟雨浪 > 《DataStructure》

舉報(bào)/認(rèn)領(lǐng)