SOURCE

// //核心代码---开始
// public static void sort(Comparable[] arr) {
//     int j;
//     for (int gap = arr.length / 2; gap >  0; gap /= 2) {
//         for (int i = gap; i < arr.length; i++) {
//             Comparable tmp = arr[i];
//             for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
//                 arr[j] = arr[j - gap];
//             }
//             arr[j] = tmp;
//         }
//     }
// }
// //核心代码---结束
// https://static-e84a4d0d-5a02-41cc-9485-9a5329e996c3.bspapp.com/cdn/three.min.js
// 增涨量
function sort(arr){
    let first=0;
    // return arr;
    for(let gap = Math.floor(arr.length/2);gap>0;gap=Math.floor(gap/2)){
        // console.log(gap,'gap');
        for(let last=gap;last<arr.length;last++){
            // 后面那层 被比较数
            let tmp=arr[last];
            // 前面那层 比较数
            // arr[j-gap]
            // 每层比较
            for(first=last;first>=gap&&tmp-arr[first-gap]<0;first-=gap){
                console.log(arr[first],first,gap)
                arr[first]=arr[first-gap];
            }
            arr[first]=tmp;
        }
    }
    return arr; 
}

function hillSort(arr){
    
    for(let gap=Math.floor(arr.length/2);gap>0;gap=Math.floor(gap/2)){
        for(let last=gap;last<arr.length;last++){
            let tmp=arr[last];
            // 后面那层 被比较数
            // 前面那层 比较数
            // 每层比较
            // 最后一个减间隔
            let first=0;
            for(first=last;first>=gap&&tmp-arr[first-gap]<0;first-=gap){
                arr[first]=arr[first-gap];
            }
            arr[first]=tmp;
        }
    }
    return arr;
}
// 2 
// 2 5
// 2 


// 6
// 3
const arr=[31,23,44,52,12];
// console.log(sort(arr))
console.log(hillSort(arr))