java - 为什么我在 Java 中的合并排序实现出错？

Question

我正在同时学习Java和算法。我在这个类中实现了归并排序。

public class Sorter {
    private void merge(int [] numbers, int low, int mid, int high) {
            // create a new array that will contain the merged integers
            int[] arrIntMerged = new int[high - low + 1];

            // set indices
            int i = low, j = mid + 1, k = 0;

            // add the lesser integer into merged array
            while (i <= mid && j <= high) {
                if (numbers[i] < numbers[j]) {
                    arrIntMerged[k] = numbers[i];
                    i++;
                } else {
                    arrIntMerged[k] = numbers[j];
                    j++;
                }
                k++;
            }

            // add anything left in the left side of the array
            while (i <= mid) {
                arrIntMerged[k] = numbers[i];
                i++;
                k++;
            }

            // add anything left in the right side of the array
            while (j <= high) {
                arrIntMerged[k] = numbers[j];
                j++;
                k++;
            }

            // write this newly created array into the positions in the original array
            for (int l = 0; l < arrIntMerged.length; l++) {
                numbers[l + low] = arrIntMerged[l];
            }
        }

        // recursive implementation
        private void _mergeSort(int[] numbers, int low, int high) {
            if (low == high)
                return;
            else {
                // find midpoint while preventing overflow
                int mid = low + (high - low) / 2;
                // sort left and right side
                _mergeSort(numbers, low, mid);
                _mergeSort(numbers, mid + 1, high);
                // merge both sides
                merge(numbers, low, mid + 1, high);
            }
        }

        // friendly interface to begin merge sort
        public void mergeSort(int[] numbers) {
            _mergeSort(numbers, 0, numbers.length - 1);
        }
}

然后我在 Eclipse 的剪贴簿中检查了这段代码。

Sorter sorter = new Sorter();
int[] nums = {5, 6, 7, 8, 1, 2, 3, 4};
sorter.mergeSort(nums);
System.out.println(Arrays.toString(nums));

不幸的是，标准输出显示为 [2, 3, 4, 5, 6, 7, 8, 1]，这是乱序的。为什么我的合并排序出错了？我非常确定 _mergeSort 中的边界条件，所以我怀疑我的 merge 函数有问题。

Answer 1

您的问题来自 merge 中的以下分配:

j = mid + 1

mid 已经是合并右侧第一个数字的索引，此增量使合并逻辑的其余部分从错误的数组位置开始。

因为看起来您正在学习，所以我不会通过发布所需的实际代码更改来破坏您的体验，但这里有一个提示:检查您将事物与 mid 值进行比较的所有地方.