javascript - 麻烦看下我的 希尔排序 是否正确？？

问题描述

问 题

// 希尔排序
function shellSort(arr , sortType){
    var sortTypeRange = ['asc' , 'desc'];
    var sortType      = !contain(sortType , sortTypeRange) ? 'asc' : sortType;
    // 交换的中间值
    var tempVal          = null;
    // 数组长度
    var arrLen          = arr.length; 
    // 基准值
    var divisor          = 3;
    // 间隔
    var interval      = 1;

    // 计算最大动态间隔序列
    while (interval < arrLen / divisor)
        {
            interval = interval * divisor + 1;
        }
    
    // 当间隔 = 1 的时候，等价于 插入排序
    while (interval >= 1)
        {
            // 分组排序（说成是分组合并排序也行）
            // 核心，实际就是，插入排序（只是间隔有可能不是 1 了）
            for (var i = interval; i < arrLen; ++i) 
                {
                    for (var n = i - interval; n >= 0; n -= interval)
                        {
                            if (sortType === 'asc' ? arr[n + interval] < arr[n] : arr[n + interval] > arr[n]) {
                                tempVal    = arr[n];
                                arr[n]     = arr[n + interval];
                                arr[n + interval] = tempVal;
                            } else {
                                break;
                            }
                        }
                }
            // 逐次缩小间隔
            // 用数组也可描述：将可能出现的间隔保存在数组中，然后每次循环 删掉数组中的头部单元
            // 直到为空数组为止
            interval = (interval - 1) / divisor;
        }
}

随机数组：一百万数量，测试结果如下：

麻烦精通算法的大神看下....

解决方案

基本思想是对的。貌似增量的递减有点奇怪，不过没问题。只要最后是1，都能排好序。

这篇关于javascript - 麻烦看下我的 希尔排序 是否正确？？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！