挑战:在一次关于数据结构和算法的讲座中,我遇到了merge-sort的一个版本,它使用了merge例程,使后半部分与拆分索引相反,并从中比较第一个和最后一个元素。我尝试用java实现,但总是以某种方式失败。
问题:正在对数组进行排序,以便输出 [1, 2, 4, 8, 6]
所以 6
未排序。似乎递归调用没有查看元素 6
在过去 merge
打电话。
我尝试的是:移动不同的索引并添加不同的打印语句进行检查。我试着 j = r
最后一次之前 for
内循环 merge
每次都会导致堆栈溢出。我试图改变数组大小的计算方式,因为我不确定伪代码是否将数组从1或0开始。我试着换衣服 if(p < r-1)
至 if(p <= r-1)
但是得到一个堆栈溢出。
我研究了java合并例程的不同实现,到目前为止,我发现的每个实现似乎都适用于两个数组。有没有一个严重的原因,为什么上述方法不能正常工作或任何想法如何解决这个问题?
给定以下伪代码:
void merge_sort(array<T>& A, int p, int r) {
if (p < r - 1) {
int q = Floor((p + r) / 2);
merge_sort(A, p, q);
merge_sort(A, q + 1, r);
merge(A, p, q, r);
}
}
void merge(array<T>& A, int p, int q, int r) {
array<T> B(p, r - 1);
int i, j;
for (i = p; i < q; i++)
B[i] = A[i];
// Now i=q
for (j = r; i < r; i++)
B[--j] = A[i];
i = p;
j = r - 1;
for (int k = p; k < r; k++)
A[k] = (B[i] < B[j]) ? B[i++] : B[j--];
}
我试着用java实现如下:
import java.util.Arrays;
public class Mergesort {
private static int[] A = new int[]{ 4, 2, 1, 8, 6 };
public static void main(String[] args) {
merge_sort(0, A.length - 1);
System.out.println(Arrays.toString(A));
}
public static void merge_sort(int p, int r) {
if (p < r - 1) {
int q = Math.floor((p + r) / 2);
merge_sort(p, q);
merge_sort(q + 1, r);
merge(p, q, r);
}
}
public static void merge(int p, int q, int r) {
int[] B = new int[r - p];
int i, j;
for (i = p; i < q; i++)
B[i] = A[i]
for (j = r; i < r; i++)
B[--j] = A[i];
i = p;
j = r - 1;
for (int k = p; k < r; k++)
A[k] = (B[i] < B[j])? B[i++] : B[j--];
}
}
1条答案
按热度按时间wvmv3b1j1#
代码中存在多个问题:
临时数组太短:因为
r
是最后一个元素的索引,大小应为r - p + 1
. 传递要简单得多r
索引超过要排序的切片的最后一个元素。第一个
for
循环不正确:应该使用不同的索引B
以及A
.第二个
for
循环复制到B[r - 1]
向下,但应该使用B[r - p]
相反。合并循环不正确:您应该测试
i
以及j
在进入前仍在各自的一半的边界内B[i]
和/或B[j]
.[次要]没有必要
int q = Math.floor((p + r) / 2);
在java中作为p
以及r
你有类型吗int
,因此除法将使用整数算法。以下是一个修改版本:
反转后半部分可以实现更简单的合并循环,而无需边界测试。但是请注意,有一种更简单的方法,它使用的内存更少,效率也可能更高: