题解 | #排序# #希尔排序

希尔排序

/** 
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
export function MySort(arr: number[]): number[] {
    // write code here
    // 希尔排序
    let interval = 1
    const len = arr.length
     
    // 优化循环次数
    while(interval < len / 3){
        interval = 3 * interval + 1
    }
     
    // 先初次检查数组是否有序
    let hasExchanges = false
    for(let i = 0; i < len - 1; i++){
        if(arr[i] > arr[i+1]){
            [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
            hasExchanges = true
        }
    }
     
    // 有序则退出
    if(!hasExchanges) {return arr}
     
     
    while(interval >= 1){
        // 插入排序
        for(let i = interval; i < len; i++){
            let curr = arr[i]
            let prevIdx = i - interval
            while(prevIdx >= 0 && curr < arr[prevIdx]){
                arr[prevIdx + interval] = arr[prevIdx]
                prevIdx -= interval
            }
            arr[prevIdx + interval] = curr
        }
        interval = ((interval / 3) * 2) >> 1
    }
         
     
    return arr
}