JS實現希爾排序

這篇文章主要介紹了關於JS實現希爾排序，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

希爾排序本質上是一種插入排序，但是對數列進行了等間隔分組處理，在每一組中做插入排序，這一優化使得原本O(n^2)  的時間複雜度一下降為O(nlogn)。

基本思想

希爾排序是將數列依照一定的間隔分組，然後在每一個分組中做插入排序；隨後逐次縮小間隔，在每一個分組中做插入排序……直到間隔等於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  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));

以上就是本文的全部內容，希望對大家的學習有所幫助，更多相關內容請關注PHP中文網！

相關推薦：

Jquery新增loading過渡遮罩

vue 實作數字捲動增加效果

以上是JS實現希爾排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！