Skip to main content

希尔排序

概要​

希尔排序是一种插入排序的算法，它是对简单的插入排序进行改进后，更高效的版本。由希尔（Donald Shell）于1959年提出。
特点是利用增量，将数组分成一组组子序列，然后对子序列进行插入排序。
由于增量是从大到小，逐次递减，所以也称为缩小增量排序。

效果图​

解法​

caution

注意，插入排序时，并不是一个分组内的数字一次性用插入排序完成，而是每个分组交叉进行。

执行插入时，使用交换法​

function shellSort(arr){
    // 分组规则 gap/2 递减
    for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
        for(let i = gap; i < arr.length; i++){
            let j = i;
            // 分组内数字，执行插入排序，
            // 当下标大的数字，小于 下标小的数字，进行交互
            // 这里注意，分组内的数字，并不是一次性比较完，需要i逐步递增，囊括下个分组内数字
            while(j - gap >= 0 && arr[j] < arr[j - gap]){
                swap(j, j-gap);
                j = j - gap;
            }
        }
    }

    return arr;

    function swap(a, b){
        const tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

执行插入时，使用移动法​

function shellSort(arr){

    for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
        for(let i = gap; i < arr.length; i++){
            let j = i;
            const x = arr[j]; // 缓存数字，空出位置

            while(j - gap >= 0 && x < arr[j-gap]){
                arr[j] = arr[j - gap]; // 将符合条件的数字，填入空出的位置
                j = j - gap;
            }
            arr[j] = x; // 最后，将缓存的数字，填入空出的位置
        }
    }

    return arr;
}

参考​

Last updated on