希尔排序详解

希尔排序是插入排序的一种优化排序方法，希尔排序是对数组下标按照一定增量分组，对每组使用插入算法排序；循环执行该操作直到增量不小于0，排序完成。

1.算法步骤

• 选取希尔排序增量值（一般情况：数组长度除于2{len / 2, (len / 2) / 2, …… 1}，或者是数组长度除于3{len / 3, (len / 3) / 3, …… 1}，需要注意增量取整）。
• 对取出的元素分组，进行插入排序。
• 循环执行步骤1，步骤2，直到增为1，执行完毕

2.算法演示流程

3.算法代码

// 这个是 n/2   n/2/2 …… 1
function hillSort(arr){
    var len = arr.length;
    var gap = 1;

    while(gap < len / 2){
        gap = gap * 2 + 1;
    }

    // 循环分组
    for(var gap; gap > 0; gap = Math.floor(gap / 2)){

        // 插入排序
        for(var i = gap; i<len;i++){
            var temp = arr[i];
            for(var j = i - gap; j >= 0 && arr[j] > temp; j -= gap){
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }

    }

    return arr;

}