iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 6
0

希爾排序法其實是優化版的插入排序法,插入排序法只能跟左方一個數值比對,而希爾排序法則是先取一個Gap值作為選取左方數值的間隔值,然後進行比對排序,而Gap在每一輪比對完都會減半,最終Gap會是1,相當於插入排序法的間隔值,但整個過程因為是先大間隔的取值比較排序,比原始的插入排序法效率要好些。

先看這段有趣的影片

程式碼如下:

function shellSort(arr){
  //Calculate the gap size first.
  let gapSize =  Math.floor(arr.length/2);
  while(gapSize > 0){
    //Loop every value.
    for(let i = gapSize; i < arr.length; i++) {
      let j = i;
      //Compare the two value and change their position if the left value is bigger than right value.
      while(j >= gapSize && arr[j - gapSize] > arr[j]) {
        [arr[j],arr[j - gapSize]]=[arr[j - gapSize],arr[j]]
        //Continune comparing th the left side.
        j =j- gapSize;
      }
    }
    gapSize = Math.floor(gapSize/2);
  }
  return arr;
}

const arr=[7,5,1,20,8];
console.log(shellSort(arr));

完整程式碼


上一篇
插入排序(Insertion Sort)
下一篇
合併排序法(Merge Sort)
系列文
透過JavaScript學習演算法與資料結構30

1 則留言

0
心原一馬
iT邦新手 3 級 ‧ 2019-09-07 16:06:34

感謝分享。天啊~ 這影片也太炫了吧
以前小馬在書上看過Shell Sort都看不懂,
看了這個瞬間秒懂Shell Sort,
可是影片中取的gapSize真的沒問題嗎?

第一輪陣列長度是10,所以程式碼中的gapSize應為10/2=5沒問題。
到第二輪排序時,gapSize = Math.floor(gapSize/2)
所以gapSize應該是floor(5/2)=2?
在影片中0:51開始,卻是a[3]嘗試與a[0]做交換,
感覺上影片中演示的gapSize是3?
若小馬理解有誤還請告知。
總之感謝分享啦。

Michael iT邦新手 5 級‧ 2019-09-07 16:16:13 檢舉

感謝提醒~
我當初沒注意到影片的gap不是按照/2的規律去算,一般是/2,但實際的最佳gap是由其他方式去求得,gap會影響整體效率。

好的,謝謝回覆~

我要留言

立即登入留言