<tfoot id="gccke"></tfoot>

<strike id="gccke"></strike>

<del id="gccke"></del>

JS實(shí)現(xiàn)希爾排序

chadLi 發(fā)布于2019-08-22 18:31 / 2783人閱讀

摘要：希爾排序本質(zhì)上是一種插入排序，但是對(duì)數(shù)列進(jìn)行了等間隔分組處理，在每一組中做插入排序，這一優(yōu)化使得時(shí)間復(fù)雜度降到了以下。

希爾排序本質(zhì)上是一種插入排序，但是對(duì)數(shù)列進(jìn)行了等間隔分組處理，在每一組中做插入排序，這一優(yōu)化使得時(shí)間復(fù)雜度降到了O(n^2)以下。

基本思想

希爾排序是按一定的間隔對(duì)數(shù)列進(jìn)行分組，然后在每一個(gè)分組中做插入排序；隨后逐次縮小間隔，在每一個(gè)分組中做插入排序...直到間隔等于1，做一次插入排序后結(jié)束。

那么問題來了，間隔應(yīng)該取多大，怎么縮小？通常我們?nèi)ト〕跏奸g隔為數(shù)列長度的一半：gap = length/2，以 gap = gap/2 的方式縮小，下面詳細(xì)圖解整個(gè)過程。

原始數(shù)組數(shù)組如下：

首先取間隔為 gap = length/2 = 4，將數(shù)組分為如下的4組，對(duì)每一組實(shí)施插入排序：

第一次排序，每一組較小的元素都移到了相對(duì)靠前的位置（這個(gè)狀態(tài)可以叫 n-sorted，即以n為gap分組有序），可以想象相對(duì)有序的數(shù)組可能更有利于后面的排序。接著繼續(xù)分組，gap = gap/2 = 2，對(duì)每一組實(shí)施插入排序：

繼續(xù)對(duì)數(shù)組分組，gap = gap/2 = 1，即所有元素組成一組，做插入排序完成算法：

代碼實(shí)現(xiàn)

內(nèi)層循環(huán)使用的插入排序與普通的插入排序基本一致，只是每次移動(dòng)的步長變?yōu)?gap 而不是 1：

// shellSort
function shellSort(arr) {
  for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
    // 內(nèi)層循環(huán)與插入排序的寫法基本一致，只是每次移動(dòng)的步長變?yōu)?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));