合併排序Java算法

Question

嘿我一直有我的合併排序問題，我知道有很多信息在線，這已經出現了多次，但我不知道發生了什麼事，無論我做什麼，這將無法工作，一些幫助，將不勝感激感謝

我的主要方法是這樣的：

for (int i = 0; i < trials; i++) { 
     data = generateRandomArray(arraySize); 

     // You can use following line to print out data for debugging 
     System.out.println("The array is: " + getString(data)); 

     // ADD YOUR CODE HERE TO SORT DATA AND CALCULATE EXECUTION TIME 

     // System.out.println("first index:" + data[0]); 
     // System.out.println("first index:" + data[arraySize-1]); 

     //System.out.println("hello " + SortArray.basicPartition(data,0,data.length-1)); 
     SortArray.mergeSort(data, 0, data.length-1); 

     if (isSorted(data)) 
      System.out.println(" passes - array is sorted"); 
     else 
      System.out.println(" failed - array is not sorted"); 

---

public static <T extends Comparable<? super T>> 
void mergeSort(T[] a, T[] tempArray, int first, int last){ 
    if(first < last)  // We have some work to do 
    { 
     int mid = first+(last-first)/2; 
     mergeSort(a, tempArray, first, mid); 
     mergeSort(a, tempArray, mid+1, last); 
     merge(a, tempArray, first, mid, last); 
    } 
} // end mergeSort 

/** Merge the entries in two contiguous sorted sublists 
* @param a An array of Comparable objects. 
* @param tempArray A temporary array used in the merge. 
* @param first An integer >= 0 and < mid. 
* @param mid An integer <= last. 
* @param last An integer < a.length. 
*/ 
public static <T extends Comparable<? super T>> 
void merge(T[] a, T[] tempArray, int first, int mid, int last){ 

    int firstIndex = first; 
    int FirstHalfEnd = mid -1; 


    while ((first <= FirstHalfEnd) && (mid <= last)) { 

     if (a[first].compareTo(a[mid]) <= 0) { 

      tempArray[firstIndex] = a[first]; // last to first 
      firstIndex++; 
      first++; 
     } 
     else { 
      tempArray[firstIndex] = a[mid]; 
      FirstHalfEnd++; 
      mid++; 
      //System.out.println("out of bounds"); 
     } 
    } 

    while (first <= FirstHalfEnd) { 
     tempArray[firstIndex] = a[first]; 
     firstIndex++; 
     first++; 

    } 
    while(mid <= last){ 
     tempArray[firstIndex] = a[mid]; 
     firstIndex++; 
     mid++; 
    } 
    for(int i=0;i<(last-first+1);i++){ 
     a[last] = tempArray[last]; 
     last--; 
     //System.out.println(a[i]); 
    } 

} // end merge 

---

OUTPU牛逼

The array is: [ 1 5 3 5 1 6 9 7 1 4 ] 
    failed - array is not sorted 
The array is: [ 1 8 3 4 3 1 6 8 0 9 ] 
    failed - array is not sorted 
The array is: [ 0 1 5 5 5 0 0 3 0 4 ] 
    failed - array is not sorted 
The array is: [ 0 0 6 2 7 4 6 2 2 2 ] 
    failed - array is not sorted 
The array is: [ 4 9 2 3 3 4 4 0 3 5 ] 
    failed - array is not sorted 

Answer 1

我還沒有遇到你的代碼 - 有缺件 - ，但我發現在merge()函數的第一個while環2個問題 - 看到添加評論：

while ((first <= FirstHalfEnd) && (mid <= last)) { 

    // compareTo return a negative value if (a[first] < a[mid]) 
    // Then I think your comment is wrong: the values are put in the 
    // temporary array in increasing order. It means you have to review 
    // the for loop that copies the values 
    // at the end. 
    if (a[first].compareTo(a[mid]) <= 0) { 

     tempArray[firstIndex] = a[first]; // last to first (No!) 
     firstIndex++; 
     first++; 
    } 
    else { 
     tempArray[firstIndex] = a[mid]; 
     FirstHalfEnd++; // <= this a bug, should be firstIndex++ 
     mid++; 
     //System.out.println("out of bounds"); 
    } 
} 

編輯
由於值是在tempArray遞增的順序，複製for循環應該是沿着：

for(int i = first; i <= last; ++){ 
    a[i] = tempArray[i]; 
} 

哪個可被簡化（？）或通過

System.arraycopy(tempArray, first, a, first, (last-first+1)); 

Answer 2

優化這裏是一個替換實現。它降序排序：

public class MergeSort { 
public static void merge(int[]a,int[] aux, int f, int m, int l) { 

    for (int k = f; k <= l; k++) { 
     aux[k] = a[k]; 
    } 

    int i = f, j = m+1; 
    for (int k = f; k <= l; k++) { 
     if(i>m) a[k]=aux[j++]; 
     else if (j>l) a[k]=aux[i++]; 
     else if(aux[j] > aux[i]) a[k]=aux[j++]; 
     else a[k]=aux[i++]; 
    }  
} 
public static void sort(int[]a,int[] aux, int f, int l) { 
    if (l<=f) return; 
    int m = f + (l-f)/2; 
    sort(a, aux, f, m); 
    sort(a, aux, m+1, l); 
    merge(a, aux, f, m, l); 
} 
public static int[] sort(int[]a) { 
    int[] aux = new int[a.length]; 
    sort(a, aux, 0, a.length-1); 
    return a; 
} 

}