摘要：動(dòng)態(tài)定義間隔序列參考來(lái)源詳細(xì)介紹了十種算法大家可以去學(xué)習(xí)下以后大概會(huì)盡量每天更新一個(gè)算法學(xué)習(xí)吧溫故而知新
參考書(shū):
嚴(yán)蔚敏-數(shù)據(jù)結(jié)構(gòu)
希爾排序(Shell"s Sort)
希爾排序又稱"縮小增量排序",歸屬于插入排序一類(lèi),簡(jiǎn)單來(lái)說(shuō),和我們的插入排序比,它更快.
奇妙的記憶點(diǎn):
內(nèi)排序(內(nèi)存排序就夠了)
不穩(wěn)定(排序后原始順序無(wú)法保證)
希爾排序重點(diǎn)在于分割.
基本思想:
將整個(gè)待排序記錄序列分割為若干個(gè)子序列,然后對(duì)每一個(gè)子序列進(jìn)行直接插入排序.
直接插入排序:
不得不先講一下直接插入排序了,畢竟希爾排序要使用到直接插入排序.
直接插入算法重點(diǎn)在于分區(qū),有序區(qū)與無(wú)序區(qū).假設(shè)我們有一個(gè)數(shù)組arr
for(var i = 1;i0&&arr[j-1]>key){
arr[j] = arr[j-1];
j--;
}
arr[j]=key;
}
其中i=1,i~arr.len-1為我們的無(wú)序區(qū),而i=0為我們的有序區(qū).temp用于記錄無(wú)序區(qū)準(zhǔn)備進(jìn)入有序區(qū)的元素,j用于從右往左遍歷有序區(qū)并將元素往后推,找出相應(yīng)的插入位置,將temp插入對(duì)應(yīng)位置.
希爾排序:代碼
希爾排序關(guān)鍵在于增量的設(shè)置,根據(jù)增量分割數(shù)組并逐步進(jìn)行直接插入排序,增量逐趟減少,并最后使得整個(gè)數(shù)組基本有序,再對(duì)整體進(jìn)行直接插入排序.
記憶點(diǎn)
best condition: T(n) = O(n*log2 n)
baddest condition: T(n) = O(n*log2 n)
average condition: T(n) = O(n*log n)
基本的思路就是根據(jù)增量分割數(shù)組,如var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
我們?cè)隽繛?,則分割為
[3,15,46]
[44,36,4]
[38,26,19]
[5,27,50]
[47,2,48]
并對(duì)每一組進(jìn)行直接插入排序
再把增量變?yōu)?(減半),再進(jìn)行分割,直到增量為1,再對(duì)全體進(jìn)行一次直接插入排序就可以了.
簡(jiǎn)略的代碼如下:
var len =arr.length;
gap = Math.floor(len/2);
while(gap!==0){
for(var i = gap;i=0&&temp
簡(jiǎn)單說(shuō)一下,i從gap位開(kāi)始,那么每組的有序區(qū)已經(jīng)確定了一位,接下來(lái)將i-gap位的數(shù)根據(jù)組的不同插入有序區(qū),就完成了每組的直接插入排序了.
相關(guān)流程圖
動(dòng)態(tài)定義間隔序列
這是我在掘金看來(lái)的
希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列。動(dòng)態(tài)定義間隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。
while(gap < len/5) { //動(dòng)態(tài)定義間隔序列
gap =gap*5+1;
}
參考來(lái)源:http://gold.xitu.io/post/57dc...
詳細(xì)介紹了十種算法,大家可以去學(xué)習(xí)下.
以后大概會(huì)盡量每天更新一個(gè)算法學(xué)習(xí)吧,溫故而知新
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/80421.html
