Java 字符串合并排序

Question

我的老师这周出去了，她给了我们这个合并排序代码供我们使用。它是为 int[] 数组编写的，我们应该为 String[] 数组制作一个。

这是她的代码：

public static void mergeSort(int[ ] a, int from, int to)
{  if (from == to) return;
  int mid = (from + to) / 2;
   // sort the first and the second half
  mergeSort(a, from, mid);
  mergeSort(a, mid + 1, to);
  merge(a, from, mid, to);     }// end mergeSort

public static void merge(int[ ] a, int from, int mid, int to)
{  int n = to - from + 1;         // size of the range to be merged
  int[ ] b = new int[n]; // merge both halves into a temporary array b 
  int i1 = from;         // next element to consider in the first range
  int i2 = mid + 1;      // next element to consider in the second range
  int j = 0;             // next open position in b

  // as long as neither i1 nor i2 past the end, move the smaller into b
  while (i1 <= mid && i2 <= to)
  {  if (a[i1] < a[i2])
     {  b[j] = a[i1];
        i1++;          }
     else
     {  b[j] = a[i2];
        i2++;           }
     j++;
  }

  // note that only one of the two while loops below is executed

  // copy any remaining entries of the first half
  while (i1 <= mid)
  {  b[j] = a[i1];
     i1++;
     j++;        }

  // copy any remaining entries of the second half
  while (i2 <= to)
  {  b[j] = a[i2];
     i2++;
     j++;      }

  // copy back from the temporary array
  for (j = 0; j < n; j++)
     a[from + j] = b[j];
}// end merge

现在这是我的尝试：

//merge sort
public static void mergeSort(String[] a, int from, int to)
{  
    if (from == to)
        return;
    int mid = (from + to) / 2;
    // sort the first and the second half
    mergeSort(a, from, mid);
    mergeSort(a, mid + 1, to);
    merge(a, from, mid, to);
}// end mergeSort
//work
public static void merge(String[] a, int from, int mid, int to)
{  
    int n = to - from + 1;       // size of the range to be merged
    String[]b = new String[n];   // merge both halves into a temporary array b 
    int i1 = from;               // next element to consider in the first range
    int i2 = mid + 1;            // next element to consider in the second range
    int j = 0;                   // next open position in b

    // as long as neither i1 nor i2 past the end, move the smaller into b
    while (i1 <= mid && i2 <= to)
    {  
        if (a[i1].compareTo(a[i2]) > 0)
        {  
            b[j] = a[i1];
            i1++;          
        }
        else
        {  
            b[j] = a[i2];
            i2++;           
        }
        j++;
    }

    // note that only one of the two while loops below is executed

    // copy any remaining entries of the first half
    while (i1 <= mid)
    {  
        b[j] = a[i1];
        i1++;
        j++;
    }

    // copy any remaining entries of the second half
    while (i2 <= to)
    {  
        b[j] = a[i2];
        i2++;
        j++;
    }

    // copy back from the temporary array
    for (j = 0; j < n; j++)
        a[from + j] = b[j];
}//end merge

我觉得她给我们的代码缺少一些她通常会在课堂上向我们解释的东西，但由于她出去了，我不知道该怎么做。任何帮助表示赞赏。谢谢！

Answer 1

发现一切正常 - 只有

compareTo

中的

merge

方向错误。这是一个工作示例

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        String[] values = {"foo", "bar", "alice", "bob", "celine", "david"};
        mergeSort(values, 0, values.length - 1);
        System.out.println("Result " + Arrays.toString(values));
    }

    public static void mergeSort(String[] a, int from, int to) {
        if (from == to) {
            return;
        }
        int mid = (from + to) / 2;
        // sort the first and the second half
        mergeSort(a, from, mid);
        mergeSort(a, mid + 1, to);
        merge(a, from, mid, to);
    }// end mergeSort
//work

    public static void merge(String[] a, int from, int mid, int to) {
        int n = to - from + 1;       // size of the range to be merged
        String[] b = new String[n];   // merge both halves into a temporary array b
        int i1 = from;               // next element to consider in the first range
        int i2 = mid + 1;            // next element to consider in the second range
        int j = 0;                   // next open position in b

        // as long as neither i1 nor i2 past the end, move the smaller into b
        while (i1 <= mid && i2 <= to) {
            if (a[i1].compareTo(a[i2]) < 0) {
                b[j] = a[i1];
                i1++;
            } else {
                b[j] = a[i2];
                i2++;
            }
            j++;
        }

        // note that only one of the two while loops below is executed
        // copy any remaining entries of the first half
        while (i1 <= mid) {
            b[j] = a[i1];
            i1++;
            j++;
        }

        // copy any remaining entries of the second half
        while (i2 <= to) {
            b[j] = a[i2];
            i2++;
            j++;
        }

        // copy back from the temporary array
        for (j = 0; j < n; j++) {
            a[from + j] = b[j];
        }
    }//end merge

}