資訊專欄INFORMATION COLUMN
摘要：希爾排序本質上是一種插入排序，但是對數列進行了等間隔分組處理，在每一組中做插入排序，這一優化使得時間復雜度降到了以下。
希爾排序本質上是一種插入排序，但是對數列進行了等間隔分組處理，在每一組中做插入排序，這一優化使得時間復雜度降到了O(n^2)以下。
基本思想希爾排序是按一定的間隔對數列進行分組，然后在每一個分組中做插入排序；隨后逐次縮小間隔，在每一個分組中做插入排序...直到間隔等于1，做一次插入排序后結束。
那么問題來了，間隔應該取多大，怎么縮小？通常我們去取初始間隔為數列長度的一半：gap = length/2，以 gap = gap/2 的方式縮小，下面詳細圖解整個過程。
原始數組數組如下：
首先取間隔為 gap = length/2 = 4，將數組分為如下的4組，對每一組實施插入排序：
第一次排序，每一組較小的元素都移到了相對靠前的位置（這個狀態可以叫 n-sorted，即以n為gap分組有序），可以想象相對有序的數組可能更有利于后面的排序。接著繼續分組，gap = gap/2 = 2，對每一組實施插入排序：
繼續對數組分組，gap = gap/2 = 1，即所有元素組成一組，做插入排序完成算法：
代碼實現內層循環使用的插入排序與普通的插入排序基本一致，只是每次移動的步長變為 gap 而不是 1：
// shellSort
function shellSort(arr) {
for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
// 內層循環與插入排序的寫法基本一致，只是每次移動的步長變為 gap
for(let i = gap; i < arr.length; i++) {
let j = i;
let temp = arr[j];
for(; j> 0; j -= gap) {
if(temp >= arr[j-gap]) {
break;
}
arr[j] = arr[j-gap];
}
arr[j] = temp;
}
}
return arr;
}
// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/95943.html
本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現，如果喜歡請點贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導讀 排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道...
摘要：動態定義間隔序列參考來源詳細介紹了十種算法大家可以去學習下以后大概會盡量每天更新一個算法學習吧溫故而知新 參考書:嚴蔚敏-數據結構 希爾排序(Shells Sort) 希爾排序又稱縮小增量排序,歸屬于插入排序一類,簡單來說,和我們的插入排序比,它更快. 奇妙的記憶點: 內排序(內存排序就夠了) 不穩定(排序后原始順序無法保證) 希爾排序重點在于分割. 基本思想: 將整個待排序記錄序...
摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學好前端，先練好內功，只有內功深厚者，前端之路才...
閱讀 1775·2021-10-19 13:30
閱讀 1348·2021-10-14 09:48
閱讀 1541·2021-09-22 15:17
閱讀 2012·2019-08-30 15:52
閱讀 3281·2019-08-30 11:23
閱讀 1992·2019-08-29 15:27
閱讀 897·2019-08-29 13:55
閱讀 758·2019-08-26 14:05
