调试：合并排序

Question

尝试在 Java 中实现归并排序。我在脑海中仔细检查了我的代码，我觉得它应该可以工作，但显然我做错了什么。这是代码

    public static void mergeSort(int[] input, int start, int end) {
        if (end - start < 2)
            return;
        
        int mid = (start + end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid + 1, end);
        merge(input, start, mid, end);
    }

    public static void merge(int[] input, int start, int mid, int end) {
        if (input[mid - 1] <= input[mid])
            return;
         
        int i = start;
        int j = mid;
        int tempIndex = 0;
        int[] temp = new int[end - start]; //combined size of both arrays being merged
        
        /*if i is >= mid, then that means the left portion of the array is done being sorted
          and vice versa if j >= end. Once this happens, we should be able to
          just copy the remaining elements into the temp array 
        */
        while (i < mid && j < end) {
            temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
        }
        
        //Copying left over elements in left portion
        while (i < mid)
            temp[tempIndex++] = input[i++];
        
        //Copying left over elements in right portion
        while (j < end)
            temp[tempIndex++] = input[j++];
        
        //Copy the sorted temp array into the original array
        //This is where I think I must be messing up
        for (int k = 0; k < temp.length; k++) {
            input[start + k] = temp[k];    
        }
     }

我想一定是我没有正确地将带有排序元素的临时数组复制回原始数组，但我不确定。我在我的代码上写了评论来解释我的逻辑。

Answer 1

看看以下变化：

计算中值

int mid = start + (end - start) / 2;
正确分配指针 i,j。

int i = start; int j = mid+1;
正确的临时数组大小。

int [] temp = new int[end-start+1];

更正了代码中的 while 循环条件。

 class Solution{

 public static void mergeSort(int[] input, int start, int end) 
 {
     if (end == start ) return;

     int mid = start + (end - start) / 2;
     mergeSort(input, start, mid);
     mergeSort(input, mid+1, end);
     merge(input, start, mid, end);
 }

  public static void merge(int[] input, int start, int mid, int end) {
     // No Need of the under mentioned instruction
     // if(input[mid-1] <= input[mid]) return;

     int i = start;
     int j = mid+1;
     int tempIndex = 0;
     int [] temp = new int[end-start+1]; //combined size of both arrays being merged

     /*if i is >= mid, then that means the left portion of the array is done being sorted and vice versa if j >= end. Once this happens, we should be able to just copy the remaining elements into the temp array */

     while(i <= mid && j <= end){
         temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
     }

     //Copying left over elements in left portion
     while(i <= mid)
         temp[tempIndex++] = input[i++];

     //Copying left over elements in right portion
     while(j <= end)
         temp[tempIndex++] = input[j++];

     //Copy the sorted temp array into the original array
     //This is where I think I must be messing up
     for(int k = 0; k < temp.length; k++){
         input[start+k] = temp[k];    
     }
  }

 public static void main(String[] args){
     int[] input = {9,4,6,8,5,7,0,2};
     mergeSort(input,0,7);

     for(int i : input)
         System.out.println(i);    
 }

 }

调试：合并排序

Debugging : Mergesort

java

algorithm

mergesort

data-structures