时间戳

首页 > 解决方案 > 我的合并排序实现有什么问题？

java - 我的合并排序实现有什么问题？

问题描述

// merge operation for merge sort
private static void merge(int[] a, int left, int middle, int right) {
    int[] temp = new int[right - left + 1];        
    int leftCrawler = left, rightCrawler = middle;
    int currentIndex = 0;

    while (leftCrawler < middle && rightCrawler <= right) {
        if (a[leftCrawler] < a[rightCrawler])
            temp[currentIndex++] = a[leftCrawler++];
        else
            temp[currentIndex++] = a[rightCrawler++];
    }

    while (leftCrawler < middle)
        temp[currentIndex++] = a[leftCrawler++];

    while (rightCrawler <= right)
        temp[currentIndex++] = a[rightCrawler++];

    // copy temp into a
    for (int i = 0; i < temp.length; i++)
        a[i] = temp[i];
}

private static void mergeSort(int[] a, int left, int right) {
    if (right > left) {
        int middle = left + (right - left) / 2;
        mergeSort(a, left, middle);
        mergeSort(a, middle + 1, right);
        merge(a, left, middle, right);
    }
}

public static void mergeSort(int[] a) {
    int left = 0, right = a.length - 1;
    mergeSort(a, left, right);
}

所以，我认为问题可能出在我的合并操作上，但是我在下面的数组上测试了它 int[] a = {2, 5, 7, 15, 8, 9, 10}，left = 0并且middle = 4合并right = a.length - 1操作成功地完成了它需要的操作。

我已经将我的 mergeSort 实现与各种网站上的实现进行了比较，但我看不出有什么不同。我的 mergeSort 不会成功地对数组进行排序。我究竟做错了什么？

标签： javaalgorithmsortingmergesort

解决方案

问题可能出在您的副本上：

    // copy temp into a
    for(int i = 0; i < temp.length; i++)
        a[i] = temp[i];

您可能想要的是（注意left + i）：

    // copy temp into a
    for(int i = 0; i < temp.length; i++)
        a[left + i] = temp[i];

（您的测试没有检测到问题，因为left是 0。）

推荐阅读