排序算法(四)--希尔排序

希尔排序的思想：希尔排序又被称作为改进版的插入排序，插入排序是相领俩相的比较，然后互换位置。而那么他们的间隔是1，而希尔排序的间隔要大于1，但是最后要执行一次间隔为1的插入排序，这样效率就比较高。
取最优间隔值：h = 3h + 1 ==> 就是间隔去整个length的1/3是相对比较合理的。

var hillSort = (arr) => {
    let h = 1
    while(h <= arr.length/3) {
        h = h * 3 + 1
    }
    for(let gap = h;gap > 0;gap = (gap -1)/3) {
        for (let i = gap;i < arr.length;i++) {
            for(let j = i;j > gap - 1; j -= gap) {
                if (arr[j] < arr[j-gap]) {
                    let temp = arr[j]
                    arr[j] = arr[j-gap]
                    arr[j-gap] = temp
                }
            }
        }
    }
    return arr
}
hillSort([4,3,1,9,6,5,2,7,8])
//  [1, 2, 3, 4, 5, 6, 7, 8, 9]

希尔排序在实际的工作中应用应该比较少。
That’s all!