Java中MergeSort实现中的错误反转和重复数字

Question

我正在创建一个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++; 
     } 
    } 
} 

的问题是，每一次执行该功能时，输入数组返回部分排序。我的意思是大多数元素都处于正确的位置，但有一两个是错误的，还有一些是其他元素的重复。由于我看不到真正的问题，谁能帮我吗？该实现是一个小课程，我不能使用int []（比方说）而不是Integer []，以便使用Arrays.copyOf（）方法复制数组A []的内容。预先感谢，请原谅我的语法/拼写错误。

请注意，输入数组总是2的幂（2,4,8,16等），所以每次我除以2找到中间元素的索引时，我总是得到一个偶数。

Answer 1

从我所知道的，问题是你的合并方法，在这里：

if (i == lIndex) { // If the left array is sorted ... 

i不一定等于lIndex当左数组进行排序。结果，合并的最后部分并不总是被执行。您所看到的重复元素在原始数组A中未被覆盖的位置上因此遗留下来。

正确的条件是：

if (lIndex == left.length) { // If the left array is sorted ... 

Answer 2

我觉得你的问题是在这里：

if(i == lIndex) 

的方法来检查，如果你已经用完了在列表中的元素是这样的：

if (lIndex == left.length) 

换句话说，如果你从左边和右边的一些元素，即使你用尽了左ar当你用尽了左边阵列时，i将不等于lIndex。它会更大。