我的合并排序实现有什么问题?

bqucvtff  于 2021-07-04  发布在  Java
关注(0)|答案(2)|浏览(408)
// 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无法成功地对数组进行排序。我做错什么了?

pod7payv

pod7payv1#

代码中有3个错误:
合并循环不包括 a[middle] 因为你用 leftCrawler < middle 而不是:

while (leftCrawler <= middle && rightCrawler <= right)

第二个回路 while (leftCrawler < middle) 还必须更改为:

while (leftCrawler <= middle)

要从中复制的循环 temp 回到 a 将不正确的索引用于 a . 应该是:

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

请注意,第一个错误源于此处使用的有害约定,其中 right 以及 middle 包含在切片中而不是排除。排除正确的边界允许更简单的代码,而不会出现任何错误 +1 / -1 调整。
以下是一个修改版本:

// merge operation for merge sort
private static void merge(int[] a, int left, int middle, int right) {
    int[] temp = new int[right - left];        
    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[left + i] = temp[i];
}

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

public static void mergeSort(int[] a) {
    mergeSort(a, 0, a.length);
}
vsmadaxz

vsmadaxz2#

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

// 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。)

相关问题