資訊專欄INFORMATION COLUMN
摘要：這時就用簡單插入排序?qū)?shù)列直至已序從直觀上看希爾排序就是把數(shù)列進(jìn)行分組不停使用插入排序，直至從宏觀上看起來有序，最后插入排序起來就容易了無須多次移位或交換。
一、希爾排序介紹
來源百度百科：
希爾排序(Shell"s Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因D.L.Shell于1959年提出而得名。
從上面我們很容易看出來，它是插入排序的高級版
回顧一下插入排序：
將數(shù)據(jù)插入到已有序的數(shù)列中
排序前：將每個元素看成有序的數(shù)列
第一趟排序后：得到一個有序數(shù)列，其大小為2
第二趟排序后：得到一個有序數(shù)列，其大小為3
第三趟排序后：得到一個有序數(shù)列，其大小為4
........每一趟插入排序，都可以將一個無序值插入一個有序數(shù)列，直至全部值有序
如果給出的數(shù)組足夠亂的話，那么插入排序所耗費(fèi)的時間是O(n^2)
既然希爾排序是插入排序的高級版，那它做了哪些優(yōu)化呢？？讓我們來看看：
希爾排序在排序前：將一個序列分成了好幾個序列
在第一趟排序時：將這幾個序列做插入排序。排序后，部分較大的數(shù)字往后靠，部分較小的數(shù)字往前靠
在第二趟排序時：將這個序列又分了好幾個序列做插入排序(但比第一次分的數(shù)要少,ps:如果第一次分5個，第二次可能就2個了)。排序后，部分較大的數(shù)字往后靠，部分較小的數(shù)字往前靠
................
在第n趟排序時：將這個序列又分了好幾個序列(直到剩下一個序列)，從宏觀上看，此序列就基本是有序的了。這時就用簡單插入排序?qū)?shù)列直至已序
從直觀上看希爾排序：
就是把數(shù)列進(jìn)行分組(不停使用插入排序)，直至從宏觀上看起來有序，最后插入排序起來就容易了(無須多次移位或交換)。
那么，上面那里說了將一個序列分成好幾個序列，那么到底怎么分呢？比如有10個元素的序列，分成幾個才合適？每次縮減又是多少呢？
從專業(yè)的角度上講，將一個序列分成好幾個序列，用一個數(shù)來表示：那個數(shù)稱為增量。顯然的是，增量是不斷遞減的(直到增量為1)
往往的：如果一個數(shù)列有10個元素，我們第一趟的增量是5，第二趟的增量是2，第三趟的增量是1。如果一個數(shù)列有18個嚴(yán)肅，我們第一趟的增量是9，第二趟的增量是4，第三趟的增量是2，第四趟的增量是1
很明顯我們可以用一個序列來表示增量：{n/2,(n/2)/2...1}，每次增量都/2
二、希爾排序體驗(yàn)現(xiàn)在我們有一個數(shù)組，該數(shù)組有6個元素
int[] arrays = {2, 5, 1, 3, 4, 6};
排序前：
將該數(shù)組看成三個（arrays.length/2)數(shù)組，分別是:{2,3},{5,4},{1,6}
第一趟排序：
對三個數(shù)組分別進(jìn)行插入排序，因此我們?nèi)齻€數(shù)組得到的結(jié)果為{2,3},{4,5},{1,6}
此時數(shù)組是這樣子的：{2, 4, 1, 3, 5, 6}
第二趟排序：
增量減少了，上面增量是3，此時增量應(yīng)該為1了，因此把{2, 4, 1, 3, 5, 6}看成一個數(shù)組(從宏觀上是有序的了)，對其進(jìn)行插入排序，直至有序
可能我舉的例子不夠好(沒看到很好的效果)，我們來看看網(wǎng)上的圖片，加深一下希爾排序的過程：
PS:圖片來源網(wǎng)上(侵刪)
三、希爾排序代碼實(shí)現(xiàn)
public static void shellSort(int[] arrays) {
//增量每次都/2
for (int step = arrays.length / 2; step > 0; step /= 2) {
//從增量那組開始進(jìn)行插入排序，直至完畢
for (int i = step; i < arrays.length; i++) {
int j = i;
int temp = arrays[j];
// j - step 就是代表與它同組隔壁的元素
while (j - step >= 0 && arrays[j - step] > temp) {
arrays[j] = arrays[j - step];
j = j - step;
}
arrays[j] = temp;
}
}
}
我們發(fā)現(xiàn)希爾排序代碼其實(shí)非常簡單(相比對堆排序)，理解起來也不難，就用增量來將數(shù)組進(jìn)行分隔，直到增量為1。底層干的還是插入排序干的活～
四、最后參考資料：
http://blog.csdn.net/jianfpeng241241/article/details/51707618
http://blog.csdn.net/robomaster/article/details/50953265
https://www.cnblogs.com/chengxiao/p/6104371.html
如果文章有錯的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號:Java3y
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/76359.html
摘要：不斷執(zhí)行這個操作代碼實(shí)現(xiàn)快速排序用遞歸比較好寫如果不太熟悉遞歸的同學(xué)可到遞歸就這么簡單。 前言 大概花了一周的時間把八大基礎(chǔ)排序過了一遍，這篇博文主要是用來回顧一下八大基礎(chǔ)排序的要點(diǎn)和一些總結(jié)～ 回顧： 冒泡排序就這么簡單 選擇排序就這么簡單 插入排序就這么簡單 快速排序就這么簡單 歸并排序就這么簡單 堆排序就這么簡單 希爾排序就這么簡單 基數(shù)排序就這么簡單 總的來說：快速排序是用...
本篇有7k+字, 系統(tǒng)梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復(fù)雜的排序?qū)崿F(xiàn)，如果喜歡請點(diǎn)贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導(dǎo)讀 排序算法可以稱得上是我的盲點(diǎn), 曾幾何時當(dāng)我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內(nèi)心是奔潰的(啥是快排, 我只知道...
摘要：動態(tài)定義間隔序列參考來源詳細(xì)介紹了十種算法大家可以去學(xué)習(xí)下以后大概會盡量每天更新一個算法學(xué)習(xí)吧溫故而知新 參考書:嚴(yán)蔚敏-數(shù)據(jù)結(jié)構(gòu) 希爾排序(Shells Sort) 希爾排序又稱縮小增量排序,歸屬于插入排序一類,簡單來說,和我們的插入排序比,它更快. 奇妙的記憶點(diǎn): 內(nèi)排序(內(nèi)存排序就夠了) 不穩(wěn)定(排序后原始順序無法保證) 希爾排序重點(diǎn)在于分割. 基本思想: 將整個待排序記錄序...
摘要：今天再來看看另外三種時間復(fù)雜度都是的排序算法，分別是希爾排序歸并排序和快速排序。三數(shù)取中法求將放到數(shù)組的末尾總結(jié)這三種排序算法的平均時間復(fù)雜度都是，歸并排序和快速排序的應(yīng)用更廣泛。 1. 回顧 前面說完了三種較為簡單的排序算法，分別是冒泡排序，選擇排序和插入排序，它們的平均情況時間復(fù)雜度都是 O(n2)，比較的高，適合小規(guī)模的數(shù)據(jù)排序，其中插入排序的效率稍高，所以更推薦使用插入排序。今...
閱讀 2546·2021-11-18 10:02
閱讀 2028·2021-10-13 09:40
閱讀 3069·2021-09-07 10:07
閱讀 2191·2021-09-04 16:48
閱讀 1078·2019-08-30 13:18
閱讀 2513·2019-08-29 14:03
閱讀 2995·2019-08-29 12:54
閱讀 3215·2019-08-26 11:41
