// 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无法成功地对数组进行排序。我做错什么了?
2条答案
按热度按时间pod7payv1#
代码中有3个错误:
合并循环不包括
a[middle]
因为你用leftCrawler < middle
而不是:第二个回路
while (leftCrawler < middle)
还必须更改为:要从中复制的循环
temp
回到a
将不正确的索引用于a
. 应该是:请注意,第一个错误源于此处使用的有害约定,其中
right
以及middle
包含在切片中而不是排除。排除正确的边界允许更简单的代码,而不会出现任何错误+1
/-1
调整。以下是一个修改版本:
vsmadaxz2#
问题可能出在您的副本上:
你可能想要的是(注意
left + i
):(您的测试没有检测到问题,因为
left
是0。)