我正在创建一个 Java 程序,在其中实现 MergeSort 算法。我的代码如下(到目前为止):
public void merge(Integer [] left, Integer[] right, Integer[] a) {
int i = 0; // a[] index (A)
int lIndex = 0; // left[] index (B)
int rIndex = 0; // right[] index (C)
// Begin main merge process
while((lIndex < left.length) && (rIndex < right.length)) {
if(left[lIndex] <= right[rIndex]) {
a[i] = left[lIndex]; // Store it
lIndex++; // Increase index of left[]
}
else {
a[i] = right[rIndex]; // Store it
rIndex++; // Increase index of right[]
}
i++; // Increase index of a[]
}
if(i == lIndex) { // If the left array is sorted
while(rIndex < right.length) { // Copy the contents of rhe right array to a[]
a[i] = right[rIndex];
i++;
rIndex++;
}
}
else { // If the right array is sorted
while(lIndex < left.length) { // Copy the contents of the left array to a[]
a[i] = left[lIndex];
i++;
lIndex++;
}
}
}
问题是每次执行该函数时,输入数组都会返回部分排序的结果。我的意思是,大多数元素都处于正确的位置,但有一两个元素放置错误,还有一些元素与其他元素重复!由于我看不出真正的问题是什么,有人可以帮助我吗?该实现是一个类(class)的小型项目,我不能使用 int[ ] (比方说)而不是 Integer[ ],以便使用 Arrays.copyOf() 方法复制数组 A[ ] 的内容。提前致谢,请原谅我的语法/拼写错误。
请注意,输入数组始终是 2 的幂(2、4、8、16 等),因此每次除以 2 来查找中间元素的索引时,我总是得到一个偶数。
最佳答案
我认为你的问题在这里:
if(i == lIndex)
检查列表中的元素是否已用完的方法如下:
if (lIndex == left.length)
换句话说,如果你从左边取一些元素,从右边取一些元素,即使你先耗尽左边的数组,i
也不会等于lIndex
当你用完左边的数组时。会更大。
关于java - Java 中 MergeSort 实现中的错误反转和重复数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15725404/