排序算法系列：Shell 排序算法
概述
希爾排序（Shell Sort）是 D.L.Shell 于 1959 年提出來(lái)的一種排序算法，在這之前排序算法的時(shí)間復(fù)雜度基本都是 O(n2n^{2}n2) 的，希爾排序算法是突破這個(gè)時(shí)間復(fù)雜度的第一批算法之一。希爾排序是一種插入排序算法。
版權(quán)說(shuō)明
著作權(quán)歸作者所有。
商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
本文作者：Q-WHai
發(fā)表日期： 2016年4月12日
本文鏈接：https://qwhai.blog.csdn.net/article/details/51127533
來(lái)源：CSDN
更多內(nèi)容：分類 >> 算法與數(shù)學(xué)
目錄
文章目錄
- 概述
- 版權(quán)說(shuō)明
- 目錄
- @[toc]
- 算法簡(jiǎn)介
- 算法原理分析
- 算法步驟
- 邏輯實(shí)現(xiàn)
- 復(fù)雜度分析
- 問(wèn)題解答
- Ref
- Github源碼下載
- 征集
- @[toc]
算法簡(jiǎn)介
希爾排序（Shell Sort）是 D.L.Shell 于 1959 年提出來(lái)的一種排序算法，在這之前排序算法的時(shí)間復(fù)雜度基本都是 O(n2n^{2}n2) 的，希爾排序算法是突破這個(gè)時(shí)間復(fù)雜度的第一批算法之一。
– 《大話數(shù)據(jù)結(jié)構(gòu)》
算法原理分析
在上一篇《排序算法系列：插入排序算法》一文中，我們說(shuō)到了一種復(fù)雜度為 O(n2n^{2}n2) 的排序算法。而對(duì)于插入排序而言，如果我們的排序序列基本有序，或是數(shù)據(jù)量比較小，那么它的排序性能還是不錯(cuò)的。為什么？可能你會(huì)這樣問(wèn)。數(shù)據(jù)量小，這個(gè)不用多說(shuō)，對(duì)于多數(shù)排序算法這一點(diǎn)都適用；如果一個(gè)序列已經(jīng)基本有序（序列中小數(shù)普遍位于大數(shù)的前面），那么我們?cè)诓迦肱判虻臅r(shí)候，就可以在較少的比較操作之后使整體有序。如果，這一點(diǎn)你還不是很明白，可以先看看《排序算法系列：插入排序算法》一文中的解釋。
基于上面基本有序和小數(shù)據(jù)量的提示，這里就有了希爾排序的實(shí)現(xiàn)。希爾所做的就是分組，在每個(gè)分組中進(jìn)行插入排序。如下就是希爾排序中分組的示意圖：

在上圖中，我們將一個(gè)長(zhǎng)度為 10 的序列，分組成 3 組。除最后一組以外的分組都包含了 4 個(gè)元素?？墒?#xff0c;我們排序的時(shí)候并不是在這些分組內(nèi)部進(jìn)行的。而是我們要按照上面圓形的標(biāo)號(hào)來(lái)進(jìn)行插入排序，也就是排序中的 [4, 9, 7]。你可以先想一想這是為什么，在文章的最后，我再說(shuō)明這個(gè)問(wèn)題。
上面從詳細(xì)地說(shuō)明了希爾排序的由來(lái)及希爾排序的分組精髓。那么現(xiàn)在就要說(shuō)希爾排序中的插入排序，是的沒(méi)有錯(cuò)。畢竟希爾排序的核心就是分組+插入排序嘛。在這個(gè)示意圖中，我們可以很明顯地看出它想表達(dá)的東西。這里只是將[3, 9, 7]看成了一個(gè)整體，對(duì)于其它的元素，暫時(shí)與[3, 9, 7]無(wú)關(guān)。
通過(guò)上面的兩步操作，我們可以得到一個(gè)序列 T1 = [4, 0, 6, 1, 7, 2, 8, 5, 9, 3]。咦，這個(gè)序列還是無(wú)序的呀，怎么回事？我們說(shuō)希爾排序的核心是分組和獲得一個(gè)基本有序的數(shù)組。這里說(shuō)的是基本有序，并未做出承諾說(shuō)這個(gè)序列已經(jīng)有序。那么，現(xiàn)在要做的就是繼續(xù)分組+插入排序。當(dāng)然，對(duì)應(yīng)的 step 是要進(jìn)行修改的。詳細(xì)過(guò)程，參見(jiàn)下面的算法步驟。
算法步驟
通過(guò)上面的算法原理分析，這里可以總結(jié)出算法實(shí)現(xiàn)的步驟。如下：
邏輯實(shí)現(xiàn)
這是Shell 排序的核心模塊，也是分組的關(guān)鍵步驟
private void core(int[] array) {int arrayLength = array.length;int step = arrayLength;do {step = step / 3 + 1;for (int i = 0; i < step; i++) {insert(array, i, step);}System.err.println(Arrays.toString(array));} while (step > 1);}希爾排序的直接插入排序，注意這里不同的是它只是針對(duì)某一個(gè)分組子序列進(jìn)行插入排序
private void insert(int[] array, int offset, int step) {int arrayLength = array.length;int groupCount = arrayLength / step + (arrayLength % step > offset ? 1 : 0);for (int i = 1; i < groupCount; i++) {int nextIndex = offset + step * i;int waitInsert = array[nextIndex];while(nextIndex - step >= 0 && waitInsert < array[nextIndex - step]) {array[nextIndex] = array[nextIndex - step];nextIndex -= step;}array[nextIndex] = waitInsert;}}更多詳細(xì)邏輯實(shí)現(xiàn)，請(qǐng)參見(jiàn)文章結(jié)尾的源碼鏈接。
復(fù)雜度分析
| 排序方法 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 | 復(fù)雜性 | ||
| 平均情況 | 最壞情況 | 最好情況 | ||||
| Shell 排序 | O($n^{3/2}$) | O($n^{2}$) | O(n) | O(n) | 不穩(wěn)定 | 較復(fù)雜 |
問(wèn)題解答
答：這里我們分組的目的在于要完成的是對(duì)整個(gè)序列的基本序列處理，那么我們肯定想要讓這些分組的數(shù)據(jù)盡量地分散開(kāi)。如果要針對(duì)每個(gè)分組內(nèi)部進(jìn)行插入排序，那么之后的每次操作，都會(huì)是在內(nèi)部進(jìn)行的，這樣的結(jié)果就是每個(gè)分組內(nèi)部已經(jīng)有序，只是整體仍然是無(wú)序的。
答：這里的步長(zhǎng)計(jì)算很關(guān)鍵，可是究竟應(yīng)該選取什么樣的增量才是最好的，目前還尚未解決。不過(guò)大量的研究表明，當(dāng)增量序列為 dlta[k] = 2t?k+1{2^{t-k+1}}2t?k+1 - 1 (0 <= k <= t <= [log2log_{2}log2?(n+1)])時(shí)，可以獲得不錯(cuò)的效果，其時(shí)間復(fù)雜度為 O(n3/2n^{3/2}n3/2)。
Ref
- 《大話數(shù)據(jù)結(jié)構(gòu)》
Github源碼下載
- https://github.com/qwhai/algorithms-sort
征集
如果你也需要使用ProcessOn這款在線繪圖工具，可以使用如下邀請(qǐng)鏈接進(jìn)行注冊(cè)：
https://www.processon.com/i/56205c2ee4b0f6ed10838a6d
總結(jié)
以上是生活随笔為你收集整理的排序算法系列：Shell 排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 单例模式在多线程中的安全性研究
- 下一篇： 交互式数据包处理程序 Scapy 入门指