希尔排序详解

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

1.算法步骤

1. 选取希尔排序增量值（一般情况：数组长度除于2{len / 2, (len / 2) / 2, …… 1}，或者是数组长度除于3{len / 3, (len / 3) / 3, …… 1}，需要注意增量取整）。
2. 对取出的元素分组，进行插入排序。
3. 循环执行步骤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;

                }