调试: 归并排序

Question

调试: 归并排序

3

尝试在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];    
        }
     }

我认为问题可能出在我没有正确地将排序后的临时数组复制回原数组，但我不确定。我在代码中写了注释来解释我的逻辑。

- cris

你的调试尝试的结果是什么？ - MrSmith42

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yash Shah · Accepted Answer

请看以下更改：

Calculating mid

int mid = start + (end - start) / 2;
Assigning pointers i,j correctly.

int i = start; int j = mid+1;
Correct size of temp array.

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

Corrected while loops condition in the code.

 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);    
 }

 }