# 经典排序算法-04-希尔排序

/**
 * 第一个超越O(N^2)的算法：希尔排序
 * 对插入排序的改进
 * 以其设计者的名字命名（Donald Shell） 1959年公布
 * 一般简单算法的时间复杂度都是O(N^2)
 */
function shellSort(arr) {

    var length = arr.length
    var gap = Math.floor(length/2)

    while(gap >= 1) {
        for (let i = 0; i < arr.length; i++) {
            const num = arr[i];
            let j = i + gap
            while(j < arr.length) {
                if(num > arr[j]){
                    arr[i] = arr[j]
                    arr[j] = num
                }
                j += gap
                console.log(i, gap, arr)
            }
        }

        gap = Math.floor(gap/2)
    }
    return arr
}

const nums = [3,5,9,7,4,2,10]
const ret = shellSort(nums)
console.log('Result: ', ret)