0

我之前问过这个问题，但是我的帖子里堆满了一大堆其他代码并且没有清楚地呈现出来，所以我要再试一次。对不起，我是新来的

壳牌排序，我是怎么写的，只在某些时候有效。Arraya是一个包含 100 个未排序整数inc的数组，是一个由 4 个整数组成的数组，其值是 shell 排序应该使用的间隔（它们下降并且最终值始终为 1），count是一个存储不同运行 shell 排序的计数的数组,cnt表示应该为此运行的 shell 排序更新的计数值。

当我以不同的 4 个间隔多次运行 shell 排序时，只有有时排序才能完全工作。一半时间数组完全排序，另一半时间数组部分排序。

任何人都可以帮忙吗？提前致谢！

public static void shellSort(int[] a, int[] inc, int[] count, int cnt) {
    for (int k = 0; k < inc.length; k++) {
        for (int i = inc[k], j; i < a.length; i += inc[k]) {
            int tmp = a[i];
            count[cnt] += 1;
            for (j = i - inc[k]; j >= 0; j -= inc[k]) {
                if (a[j] <= tmp)
                    break;
                a[j + inc[k]] = a[j];
                count[cnt] += 1;
            }
            a[j + inc[k]] = tmp;
            count[cnt] += 1;
        }
    }
}
4

2 回答 2

1

一个问题是您只inc[k]为每个 排序一个步骤序列k，而您应该对它们全部排序（您只是排序{a[0], a[s], a[2*s], ... , a[m*s]}、遗漏{a[1], a[s+1], ... , a[m*s+1]}等）。但是，这应该只影响性能（操作数），而不是结果，因为最后一遍是经典的插入排序 ( inc[inc.length-1] == 1)，因此无论之前发生什么都应该对数组进行排序。

我在代码中看不到任何会导致失败的内容。也许inc数组不包含它应该包含的内容？如果你inc[k]在外循环的每次迭代中打印出来，你会得到预期的输出吗？

于 2011-12-09T18:55:46.897 回答
0

i您的循环控制中有一个错误：

for (int i = inc[k], j; i < a.length; i += inc[k]) {

应该：

for (int i = inc[k], j; i < a.length; i++) {

内部循环处理分开j的元素的比较。inc[k]外i循环应该简单地增加 1，与标准插入排序的外循环相同。

实际上，增量为 1 的 Shellsort 的最后一遍与标准的插入排序相同。

于 2011-12-09T19:15:13.977 回答