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