簡單合併排序Java

Question

我想在Java中創建一個簡單的合併排序程序。我覺得它應該工作，但是當我去運行它時，我得到一個堆棧溢出錯誤

Ex。堆棧溢出在MergeSort.mergeSort（MergeSort.java:24）

我已經看到其他幾個人在這裏有這樣的代碼類似的問題，但我正在努力修復我的。任何幫助，將不勝感激。

主要代碼：

import static java.lang.System.*; 
import java.util.Arrays;   

public class MergeSort{ 

private static int passCount; 

public static void mergeSort(Comparable[] list) 
{ 
    passCount=0; 
    mergeSort(list, 0, list.length); 
} 

private static void mergeSort(Comparable[] list, int front, int back) //O(Log N) 
{ 
    int mid = (front+back)/2; 
    if(mid==front) return; 
    mergeSort(list, front, mid); 
    mergeSort(list, front, back); 
    merge(list, front, back); 

} 

private static void merge(Comparable[] list, int front, int back) //O(N) 
{ 
    Comparable[] temp = new Comparable[back-front]; 

    int i=front; 
    int j=(front+back)/2; 
    int k=0; 
    int mid =j; 

    while(i<mid && j<back) 
    { 

     if(list[i].compareTo(list[j])<0) 
     { 
      temp[k]=list[i]; 
      k++; i++; 
     } 
     else 
     { 
      temp[k]=list[j]; 
      k++; i++; 
     } 


     while(i<mid) 
     { 
      temp[k++]=list[i++]; 
     } 

     while(j<back) 
     { 
      temp[k++]=list[j++]; 
     } 

     for(i = 0; i<back-front; ++i) 
     { 
      list[front+i]=temp[i]; 
     } 

    out.println("pass " + passCount++ + " " + Arrays.toString(list) + "\n"); 
    } 
} 
} 

我的亞軍：

public class MergeSortRunner 
{ 
    public static void main(String args[]) 
    { 
    MergeSort.mergeSort(new Comparable[]{9,5,3,2}); 
    System.out.println("\n"); 

    MergeSort.mergeSort(new Comparable[]{19,52,3,2,7,21}); 
    System.out.println("\n"); 

    MergeSort.mergeSort(new Comparable[]{68,66,11,2,42,31}); 
    System.out.println("\n"); 

} 
} 

Answer 1

試圖改變

if(mid==front) return; 

要

if(back-front<=1) return; 

Answer 2

儘量不要遞歸。由於mergeSort調用自己的事實，如果發生這種情況太多，就會發生堆棧溢出。

Answer 3

你需要改變：

mergeSort(list, front, back); 

要：

mergeSort(list, mid, back); 

這將導致對mergeSort無限通話，因爲你不改變任何調用之間的輸入參數。

你也可能會想要改變：

if(mid==front) return; 

到：

if(back - front <= 1) return; 

而且，這個算法的實現選擇很可能會導致非穩定的排序，因爲你正在修改列表。一個更好的選擇是讓mergeSort返回您正在排序的任何列表，然後實現merge以將兩個列表作爲參數，然後生成單個合併列表。