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


     }