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