遞歸合併排序Java程序

Question

我一直在努力合併排序遞歸代碼，我碰到了一個減速帶。我已經通過互聯網和我的算法本身在紙上多次，我似乎無法弄清楚這個問題。

public static int[] mergesort(int[] data, int low, int high) 
    { 
     int middle = (high+low)/2; 
     if (middle==low) 
     { 
      int[] data2 = new int [1]; 
      data2[0]=data[middle]; 
      return data2; 
     } 
     else 
     { 
      int[] firstHalfSorted = mergesort(data, low, middle); 
      int[] secondHalfSorted = mergesort(data, middle+1, high); 
      return (merge(firstHalfSorted, secondHalfSorted)); 
     } 
    } 

    public static int[] merge(int[] firstHalfSorted, int[] secondHalfSorted) 
    { 
     int[] SortedArray = new int[firstHalfSorted.length+secondHalfSorted.length]; 
     int m = 0; 
     int n = 0; 
     int count = 0; 
     while (m<firstHalfSorted.length && n<secondHalfSorted.length) 
     { 
      if (firstHalfSorted[m]>secondHalfSorted[n]) 
      { 
       SortedArray[count]=secondHalfSorted[n]; 
       count++; 
       n++; 
      } 
      else if (firstHalfSorted[m]<secondHalfSorted[n]) 
      { 
       SortedArray[count]=firstHalfSorted[m]; 
       count++; 
       m++; 
      } 
     } 
     if (m!=firstHalfSorted.length) 
     { 
      while(m<firstHalfSorted.length){ 
       SortedArray[count]=firstHalfSorted[m]; 
       count++; 
       m++; 
      } 
     } 
     if (n!=secondHalfSorted.length) 
     { 
      while(n<secondHalfSorted.length){ 
       SortedArray[count]=secondHalfSorted[n]; 
       count++; 
       n++; 
      } 
     } 
     return SortedArray; 
    } 

有代碼。問題出在一個文本輸入文件中，數字爲3,9,7,2,10,5,1,8，代碼只對每個其他數字排序，分別是3,7和10,1，然後是3， 7,1,10。

按我所有的想法，它應該排序3,9然後7,2等，然後，3,9,7,2和10,5,1,8等等，但它不！你們能幫我出去嗎？

Answer 1

據我所知，有問題的代碼是：

if (middle==low) 
{ 
    int[] data2 = new int [1]; 
    data2[0]=data[middle]; 
    return data2; 
} 

該代碼將返回一個元件陣列時high-low<=1。因此，對於low = 0, high=1方法，當它期望返回排序的兩元素數組時，將返回第零個元素。你可以把它改成：

if(low==high) //one element passed 
//same here 

Answer 2

對於合併排序，您只需要將數據分爲兩部分，在這兩部分遞歸，然後合併。與其試圖通過查找中間數據或您嘗試執行的任何操作來劃分數據，而不是將整個列表分成兩半。

例如：

private int[] mergesort(int[] data) { 
    int[] half1 = new int[data.length/2]; 
    int[] half2 = new int[(data.length % 2 == 0)? data.length/2 : data.length/2 + 1]; 
    for (int i = 0; 2 * i < data.length; i++) { 
     half2[i] = data[2 * i]; 
     if (2 * i + 1 < data.length) half1[i] = data[2 * i + 1]; 
    } 
    int[] firstHalfSorted = mergesort(half1); 
    int[] secondHalfSorted = mergesort(half2); 
    return merge(firstHalfSorted, secondHalfSorted); 
} 

如果你想保持當前的方法（這實際上看起來像它應該工作），你只需要通過改變if (middle == low)到if (high == low)修復整數除法錯誤。

Answer 3

你必須在這裏更改以下兩件事情：

1）改變if (middle==low)到if (high==low)在以前的帖子指出。

2）將else if (firstHalfSorted[m] **<** secondHalfSorted[n])更改爲else if (firstHalfSorted[m] **<=** secondHalfSorted[n])或簡單地else。

第二點很重要，因爲目前您的代碼不支持重複的數字。換句話說，你的if-else不是窮盡的，因爲他們不認爲firstHalfSorted[m]和secondHalfSorted[n]都是相等的情況。

Answer 4

這是一個簡單的合併排序代碼與遞歸。

public class solution { 

public static void merge(int[] input, int s, int e){ 

    int m = (s + e)/2; 

    int temp[] = new int[e - s + 1]; 

    int s1 = s; 
    int s2 = m + 1; 

    int i = s1; 
    int j = s2; 
    int p = 0; 
    while(i <= m && j <= e){ 
     if(input[i] > input[j]){ 
      temp[p] = input[j]; 
      j++; 
      p++; 
     }else{ 
      temp[p] = input[i]; 
      i++; 
      p++; 
     } 
    }//end of while loop 

    while(i <= m){ 
      temp[p] = input[i]; 
      p++; 
      i++; 
    } 
    while(j <= e){ 
      temp[p] = input[j]; 
      p++; 
      j++; 
    } 

    for(int k = 0; k < temp.length; k++){ 
     input[s + k] = temp[k]; 
    } 
} 

public static void callsort(int[] input, int s, int e){ 

    if(s >= e){ 
     return ; 
    } 

    int m = (s + e)/2; 

    callsort(input, s, m); 
    callsort(input, m + 1, e); 
    merge(input, s, e); 

} 

public static void mergeSort(int[] input){ 
    callsort(input , 0 , input.length - 1); 
} 
} 

輸入：5 6 3 2 1 4 輸出：1 2 3 4 5 6