1

我在这样的应用程序中实现了 shell 排序算法：

shell: function() {
    var list = anada.vars.$list;
    for (i = 0; i < list.length; i++) {
        list[i] = parseInt(list[i], 10);
    }
    var n = list.length;
    var increment = Math.floor(n / 2);
    var i;        

    while (increment > 0) {
        for (i = increment; i < n; i++) {
            var temp = list[i];
            var j = i;
            var affectedOne = j;
            var affectedTwo;
            while (j >= increment && list[j - increment] > temp) {
                list[j] = list[j - increment];
                j -= increment;
            }
            list[j] = temp;
            var rows = '<tr>';
            for (counter = 0; counter < n; counter++) {
                if (counter > j - increment && counter < i + 1 && counter % increment == 0) {
                    rows += '<td class="affected">' + list[counter];
                } else {
                    rows += '<td>' + list[counter];
                }
            }
            anada.vars.$elements.push(rows);
        }
        increment = Math.floor(increment / 2);
        var row = '<tr>';
        $.each(list, function(n, val) {
            row += '<td class="iteration">' + val;
        });
        anada.vars.$elements.push(row);

    }
    $('.result-content').find('table').empty();
    $.each(anada.vars.$elements, function(n, val) {
        $('.result-content').find('table').append(val);
    });
    anada.vars.$elements = [];

},

问题是这样的：

  1. 排序的第一部分仅突出显示 '21'，它不能突出显示，因为 15 和 21 没有从条目中改变它的位置.. 列表条目是 15,14,0,34,2,44,21,6 ,7,12,5,34,20。

如果索引 0 大于索引 7，即列表总数的一半 + 1，它们将改变位置，

这是配对：

第一次迭代：15-21、14-6、0-7、34-12、2-5、44-34、6-20

我要强调的是那些只有位置发生变化的人。

排序的第一部分 经过一些迭代，结束部分就像一个插入排序

我的错误是什么。

4

1 回答 1

1

让我们试着计算一下。该值i表示您开始向后交换元素的索引。该值j是该元素最终结束的位置，并increment表示步长。

考虑一个位于 position 的元素counter。如果满足以下所有条件，则将其与移动的元素交换：

  • counterj是从. 的倍数向前迈出的一步increment。换句话说，counter >= j && counter - j % increment == 0.

  • counter没有超过起点。换句话说，counter <= i.

  • 至少移动了一个元素。换句话说，i != j.

把它放在一起会产生这种情况：

if (i != j && counter <= i && counter >= j && counter - j % increment == 0) {
    // Element was swapped
} else {
    // Element was not swapped
}

您正在检查的条件与此条件接近，但有一些错误，并且j在进行 mod 时忘记换档。试试这个，看看是否能解决问题。

于 2015-08-26T17:27:14.413 回答