0

我有下面的合并排序迭代实现，但不知何故，它不起作用。我调试了它，但找不到原因。

合并函数将与递归情况相同，如果我是正确的，只有数组划分逻辑会有所不同。

请纠正，如果我走错了方向。

4

2 回答 2

2

我认为当您尝试使用相同的对象来表示不同的间隔时会遇到问题：在 MergeSort_Iterative 循环中，当您向 list1 添加新元素时，您使用“info”对象作为时间变量，然后将其添加到 list1 集合。

在 Java 中，所有对象变量都是引用，因此当您将对象添加到集合中时，您不是添加它的副本，而是添加一个正在修改并再次插入的引用。

info.left = left;
info.right = mid;
list1.add(info);

info.left = mid + 1;
info.right = right;
list1.add(info);

要解决这个问题，您应该创建两个对象以便两个执行插入：

info = new MergePosInfo();
info.left = left;
info.right = mid;
list1.add(info);

info = new MergePosInfo();
info.left = mid + 1;
info.right = right;
list1.add(info);

另一方面，一旦解决了上述问题，您应该从更短的间隔到更宽的间隔以及从左到右的位置迭代 list2，并且您的算法不会按该顺序生成 list2。

您需要修改 MergeSort_Iterative：

public static void MergeSort_Iterative(int[] numbers, int left, int right) {
    int mid;
    if (right <= left)
        return;

    LinkedList<MergePosInfo> list1 = new LinkedList<MergePosInfo>();
    LinkedList<MergePosInfo> list2 = new LinkedList<MergePosInfo>();

    for(int i = left; i <= right; i+=2)
    {
        MergePosInfo info = new MergePosInfo();
        info.left = i;
        info.right = (i+1<=right)?(i+1):i;
        info.mid = -1;
        list1.add(info);
        list2.add(info);
    }

    int l = right-left+1;
    for(int partsSize = 2; partsSize <= l/2; partsSize*=2)
    {
        int ll1 =    list1.size();
        for(int i = 0; i < ll1; i+=2)
        {
            MergePosInfo info2 = new MergePosInfo();
            info2.left = list1.get(0).left;
            info2.right = list1.get(1).right;
            info2.mid = (info2.left+info2.right)/2;

            list1.remove(0);
            list1.remove(0);

            list1.add(info2);
            list2.addLast(info2);
        }
    }


    for (int i = 0; i < list2.size(); i++) {
        System.out.println("Merge [" + Integer.toString(list2.get(i).left) + " , "  + Integer.toString(list2.get(i).right) + "]" );
        DoMerge(numbers, list2.get(i).left, list2.get(i).mid+1,
                list2.get(i).right);
    }

}

以及向 DoMerge 添加一些行：

public static void DoMerge(int[] numbers, int left, int mid, int right) {
       int[] temp = new int[25];
       int i, left_end, num_elements, tmp_pos;

       left_end = (mid - 1);
       tmp_pos = left;
       num_elements = (right - left + 1);

       if(num_elements == 2)
       {
           if(numbers[left]>numbers[right])
           {
               int buffer = numbers[left];
               numbers[left] = numbers[right];
               numbers[right] = buffer;
           }
           return;
        }
       ...

如您所见，我提供的解决方案仅在“数字”长度为 2^k 时有效。你可以尝试自己修复它，如果你不能，我会给你最后的改变。

我离开了 System.out.println("Merge [" + Integer.toString(list2.get(i).left) + " , " + Integer.toString(list2.get(i).right) + "]" );

行，以便您了解合并排序的工作原理。

于 2013-07-01T10:29:16.890 回答
1 
            info.left = left;
            info.right = mid;
            list1.add(info);

            info.left = mid + 1;
            info.right = right;
            list1.add(info);

您正在对同一个对象进行操作。每次迭代使用不同的对象，与您使用的方式相同info2

于 2013-07-01T10:34:04.043 回答