介紹
今天介紹第二種插入排序——希爾排序彩匕，該方法因D.L.Shell于1959年提出而得名，是第一個時間復(fù)雜度突破O(n^2)的排序算法，又叫縮小增量排序痴脾，在待排序數(shù)據(jù)量越大，希爾排序較直接插入排序的優(yōu)勢就越加明顯梳星，但也是前面介紹幾種算法中較難理解的一種赞赖。算法邏輯（升序為例）：
初始時，有一個大小為 10 的無序序列:
1.在第一趟排序中冤灾，我們不妨設(shè) gap1 = N / 2 = 5前域，即相隔距離為 5 的元素組成一組，可以分為 5 組韵吨。
2.接下來匿垄，按照直接插入排序的方法對每個組進行排序。
在第二趟排序中归粉，我們把上次的 gap 縮小一半椿疗，即 gap2 = gap1 / 2 = 2 (取整數(shù))。這樣每相隔距離為 2 的元素組成一組糠悼，可以分為 2 組届榄。
3.按照直接插入排序的方法對每個組進行排序。
4.在第三趟排序中倔喂，再次把 gap 縮小一半痒蓬，即gap3 = gap2 / 2 = 1。 這樣相隔距離為 1 的元素組成一組滴劲，即只有一組攻晒。
5.按照直接插入排序的方法對每個組進行排序。此時班挖，排序已經(jīng)結(jié)束鲁捏。
希爾排序
例子
假設(shè)有一個待排序數(shù)組[77, 6, 37, 96, 34, 6, 14], js實現(xiàn)如下(升序)：
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/5) { //動態(tài)定義間隔序列
gap =gap*5+1;
}
for (gap; gap > 0; gap = Math.floor(gap/5)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]
時間復(fù)雜度
時間復(fù)雜度為O(n^1.3)。
感謝閱讀！歡迎關(guān)注给梅！持續(xù)更新中...
