Java合并排序实现

Question

我想实现合并排序Java。代码对我来说看起来很好，但是它将最初的未排序数组作为输出返回。我正在学习所有的基础知识，所以我很难找到错误。

import java.util.Scanner; 
class Hacker{ 
    int[] input=new int[]{2,4,1,6,8,5,3,7}; 
    int[] left; 
    int[] right; 
    //int size; 
    Scanner scan=new Scanner(System.in); 

    public void mergeSort(int[] input){ 
     if(input.length<2){ 
      return; 
     } 
     int mid=input.length/2; 
     left=new int[mid]; 
     right=new int[input.length-mid]; 
     System.arraycopy(input, 0, left, 0, left.length); 
     System.arraycopy(input, mid, right, 0, right.length); 
     mergeSort(left); 
     mergeSort(right); 
     merge(input,left,right); 
    } 

    public void merge(int[]input,int[]left,int[]right){ 
     int i=0,j=0,k=0; 
     while(i<left.length&&j<right.length){ 
      if(left[i]<right[j]){ 
       input[k++]=left[i++]; 
      } 
      else{ 
       input[k++]=right[j++]; 
      } 
     } 
     while(i<left.length){ 
      input[k++]=left[i++]; 
     } 
     while(j<right.length){ 
      input[k++]=right[j++]; 
     } 
    } 


    public static void main(String args[]){ 
     Hacker h=new Hacker(); 

     h.mergeSort(h.input);   
     for(int i=0;i<h.input.length;i++){ 
      System.out.print(h.input[i]); 
     } 
    } 
} 

输出：

24168537 

Answer 1

你的问题是，您使用的实例变量left，在递归方法right和input。这意味着所有的递归调用都会覆盖这些值。递归需要局部变量，这意味着返回方法的结果。这也意味着这些方法可以是静态的，并且会使你的代码更加清洁。

这是您的代码转换为使用局部变量并返回计算结果。我也简化了一些东西。

public class Sorter { 
    public static int[] mergeSort(int[] input) { 
     if (input.length < 2) { 
      return input; 
     } 
     int mid = input.length/2; 
     int[] left = Arrays.copyOfRange(input, 0, mid); 
     int[] right = Arrays.copyOfRange(input, mid, input.length); 
     return merge(mergeSort(left), mergeSort(right)); 
    } 

    public static int[] merge(int[] left, int[] right) { 
     int i = 0, j = 0, k = 0; 
     int[] output = new int[left.length + right.length]; 
     while (i < left.length && j < right.length) { 
      if (left[i] < right[j]) { 
       output[k++] = left[i++]; 
      } else { 
       output[k++] = right[j++]; 
      } 
     } 
     while (i < left.length) { 
      output[k++] = left[i++]; 
     } 
     while (j < right.length) { 
      output[k++] = right[j++]; 
     } 
     return output; 
    } 

    public static void main(String args[]) { 
     int[] input = new int[]{2, 4, 1, 6, 8, 5, 3, 7}; 
     System.out.println(Arrays.toString(Sorter.mergeSort(input))); 
    } 
} 

为了供您参考，以下是两种方法的组合和排序的简化版本，而不是创建新数组。

public void mergeSort(int[] input) { 
    if (input.length >= 2) { 
     int[] left = copyOfRange(input, 0, input.length/2); 
     int[] right = copyOfRange(input, input.length/2, input.length); 
     mergeSort(left); 
     mergeSort(right); 
     for (int i = 0, j = 0, k = 0; i < left.length || j < right.length; k++) { 
      if (i >= left.length || (j < right.length && left[i] > right[j])) 
       input[k] = right[j++]; 
      else 
       input[k] = left[i++]; 
     } 
    } 
} 

Answer 2

个人而言，我宁愿：

private static void mergeSort(double[] arr, int start, int end){ 
    if(start < end){ 
     int mid = (start + end)/2; 
     mergeSort(arr, start, mid); 
     mergeSort(arr, mid + 1, end); 
     Merge(arr, start, mid, end); 
    } 
} 


private static void Merge(double[] arr, int start, int mid, int end){ 

    double[] leftArray = new double[mid - start + 2]; 
    double[] rightArray = new double[end - mid + 1]; 
    for(int i = start; i <= mid; i++) 
     leftArray[i - start] = arr[i]; 
    for (int i = mid + 1; i <= end; i++) 
     rightArray[i - mid - 1] = arr[i]; 

    leftArray[mid - start + 1] = Double.POSITIVE_INFINITY; 
    rightArray[end - mid] = Double.POSITIVE_INFINITY; 

    int leftIndex = 0, rightIndex = 0; 

    for (int k = start; k <= end; k++){ 
     if(leftArray[leftIndex] <= rightArray[rightIndex]) 
      arr[k] = leftArray[leftIndex++]; 
     else 
      arr[k] = rightArray[rightIndex++]; 
    } 
}