在java中合併排序的問題

Question

我是全新的stackoverflow，我需要一些幫助，編寫一個程序mergesort可比數列表。我已經在這段代碼上工作了幾個小時，但無濟於事。該程序需要正確工作，因爲我正在爲計算機科學課程做這個工作，而下一個任務需要我們測試不同類型的效率。下面的代碼：

合併方法：

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){ 
    ArrayList <Comparable> b = new ArrayList(); 
    for(int k = first; k <= last; k++){ 
     b.add(a.get(k)); 
    } 

    System.out.println("b now contains " + b); 
    int middle =b.size() /2; 
    for(int i = first; i <= last; i++){ 
     //System.out.println("mid: " + b.size() /2); 
     //System.out.println("b: " + b); 
     //System.out.println("a: " + a); 
     //System.out.println("i: " + i); 
     if(middle == b.size()){ 
      a.set(i, b.remove(0)); 
      middle--; 
     }else if(middle == 0){ 
      a.set(0, b.remove(0)); 
     }else if(b.get(0).compareTo(b.get(middle)) < 0){ 
      System.out.println("moving " + b.get(0) + " from b[0] to a[" + 
       i + "] because " + b.get(0) + " is less than " + b.get(middle)); 
      a.set(i, b.remove(0)); 
      middle--; 
      System.out.println("b now contains " + b); 
     }else{ 
      System.out.println("moving " + b.get(middle) + " from b[" + 
       b.size() /2 + "] to a[" + i + "] because " + b.get(0) + 
        " is greater than " + b.get(middle)); 
      a.set(i, b.remove(middle)); 
      //middle--; 
      System.out.println("b now contains " + b); 
     } 
    } 

    System.out.println(); 
    System.out.println("Merge"); 
    System.out.println(a); 
    System.out.println(); 
} 

歸併方法：

public static void mergeSort(ArrayList <Comparable> a, int first, int last){ 
    if(first < last){ 
     int mid = first + (last - first) /2; 
     System.out.println("mergeSorting " + a.subList(first, last + 1)); 
     mergeSort(a, first, mid); 
     System.out.println("mergeSorting " + a.subList(first, mid + 1)); 
     mergeSort(a, mid + 1, last); 
     System.out.println("merging " + a.subList(first, mid + 1) + 
      " and " + a.subList(mid + 1, last + 1)); 
     merge(a, first, mid, last); 
    } 
    System.out.println(); 
    System.out.println("base case"); 
    System.out.println(); 
} 

我認爲有與merge方法的問題，但我不知道。

我的代碼似乎是不正確的排序名單，即：

Input: 
[7,1,9,9,5,4,8,9,10,4] 

Output: 
[4,8,9,4,10,10,5,9,9,7] 

Answer 1

歸併算法是確定的。我剛纔定義的ArrayList的類型，以避免該警告

public static void mergeSort(ArrayList <Comparable> a, int first, int last){ 
     if(first < last){ 
      int mid = first + (last - first) /2; 
     // System.out.println("mergeSorting " + a.subList(first, mid)); 
      System.out.println("First"+first); 
      System.out.println("Mid"+mid); 
      System.out.println("Last"+last); 
      System.out.println("MergeSortCall"); 
      System.out.println("firstVector " + a.subList(first, mid+1)); 
      System.out.println("secondVector " + a.subList(mid + 1,last+1));     
      mergeSort(a, first, mid); 
      mergeSort(a, mid + 1, last); 
      merge(a, first, mid, last); 
      System.out.println("mergeVector " + a.subList(first,last+1)); 
     } 

    } 

第二部分是真的很難確切地知道什麼是錯的，所以我基本上使用您的符號代替它的東西要簡單得多。請注意，第二部分只是一個「合併」算法。它應該是非常簡單的。無論如何，使用這個，你可以與你的結果進行比較（抱歉，很難理解第二部分的邏輯，這是你的功課，不是嗎？）。我使用兩個向量來提高可讀性，但只有一個是你需要的。

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){ 
      ArrayList <Comparable> vectorFirst = new ArrayList<Comparable>(); 
      ArrayList <Comparable> vectorSecond = new ArrayList<Comparable>(); 

      for(int k=first;k<=mid;k++){ 
       vectorFirst.add(a.get(k)); 
      } 
      for(int k=mid+1;k<=last;k++){ 
       vectorSecond.add(a.get(k)); 
      } 

      int i=first; 
      int j=mid+1; 
      int k=first-1; 
      while((i<=mid)&(j<=last)){ 
       if(vectorFirst.get(i-first).compareTo(vectorSecond.get(j-mid-1))==-1){ 
        k=k+1; 
        a.set(k,vectorFirst.get(i-first)); 
        i=i+1; 
       } 
       else{ 
        k=k+1; 
        a.set(k,vectorSecond.get(j-mid-1)); 
        j=j+1; 
       } 
      } 
      if(i==mid+1){ 
       while(j<=last){ 
        k=k+1; 
        a.set(k,vectorSecond.get(j-mid-1)); 
        j=j+1; 
       } 
      } 
      else{ 
       while(i<=mid){ 
        k=k+1; 
        a.set(k,vectorFirst.get(i-first)); 
        i=i+1; 
       } 
      } 


     }