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