1

我需要帮助将合并排序与字符串数组一起使用。我已经看到了很多使用 int 数组的示例，但我需要使用字符串数组的帮助。我只能使用 .compareTo() 方法。这是我的主要方法：

public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);

    String[] nameList = {"John", "Mark", "Amber", "Tony", "Matt", "George", 
    "Will", "Bob", "Paul", "Mary Ellen", "Kate", "Joe", "Fred", "Joe", 
    "Anne", "Amber", "Kimberly", "Kelsey", "Matthew"};

    //print original
    System.out.println("Before sorting the names: ");
    for(String element: nameList)
    System.out.print(element + " ");
    System.out.println("\n");
    //Merge Sort
    System.out.println("After sorting the names: ");
    mergesort(nameList, 0, nameList.length);

}

这些是我的方法：

private static void merge(String[] data, int first, int n1, int n2) {
    String[] temp = new String[n1 + n2];
    int copied = 0;
    int copied1 = 0;
    int copied2 = 0;

    while((copied1 < n1) && (copied2 < n2)) {
        if(data[first + copied].compareTo(data[first + n1 + copied2]) < 0)
            temp[copied++] = data[first + (copied1++)];
        else
            temp[copied++] = data[first + n1 +(copied2++)];
    }

    while(copied1 < n1)
        temp[copied++] = data[first + (copied1++)];

    for(int i = 0; i < copied; i++)
        data[first +i] = temp[i];

}


public static void mergesort(String[] data, int first, int n) {
    int n1 = 0;
    int n2 = 0;

    if(n > 1) {
        n1 = n/2;
        n2 = n-n1;

        mergesort(data, first, n1);
        mergesort(data, first + n1, n2);
    }

    merge(data, first, n1, n2);

    for(String element: data)
        System.out.print(element +" ");
}

当我运行程序时，它会正确地对其中的一些进行排序，但总的来说它不是无序的。

4

2 回答 2

3

你有一个错字和两行被遗忘的行。下面是固定功能。把它和你的比较一下。

    private static void merge(String[] data, int first, int n1, int n2)
    {
        String[] temp = new String[n1 + n2];
        int copied = 0;
        int copied1 = 0;
        int copied2 = 0;

        while ((copied1 < n1) && (copied2 < n2))
        {
            if (data[first + copied1].compareTo(data[first + n1 + copied2]) < 0)
                temp[copied++] = data[first + (copied1++)];
            else
                temp[copied++] = data[first + n1 + (copied2++)];
        }

        while (copied1 < n1)
            temp[copied++] = data[first + (copied1++)];
        while (copied2 < n2)
            temp[copied++] = data[first + n1 + (copied2++)];

        for (int i = 0; i < copied; i++)
            data[first + i] = temp[i];

    }
于 2012-12-07T08:53:42.007 回答
0

我有另一个使用 Mergesort 的 String Array[] 解决方案：

public static void main(String[] args)
{
  int maxSize = 19;             // array size
  DArray arr;                    // reference to array
  arr = new DArray(maxSize);     // create the array
  String[] nameList = {"John", "Mark", "Amber", "Tony", "Matt", "George", 
            "Will", "Bob", "Paul", "Mary Ellen", "Kate", "Joe", "Fred", "Joe", 
            "Anne", "Amber", "Kimberly", "Kelsey", "Matthew"};

 for (int i=0; i<19; i++)
     {
   arr.insert(nameList[i]);
      }

  arr.display();                 // display items

  arr.mergeSort();               // merge sort the array
                              //search using binary search 
  arr.display();                 // display items again
  }  // end main()
}  // end class MergeSortApp

////////////////////////////////////////////////////////////////
public class DArray
{
private String[] theArray;          // ref to array theArray of strings
private int nElems;               // number of data items
//-----------------------------------------------------------
public DArray(int max)            // constructor
  {
  theArray = new String[max];      // create array
  nElems = 0;
  }
//-----------------------------------------------------------
public void insert(String st)    // put element into array
  {
  theArray[nElems] = st;      // insert it
  nElems++;                      // increment size
  }
//-----------------------------------------------------------
public void display()             // displays array contents
  {
     for(int j=0; j<nElems; j++)    // for each element,
     System.out.print(theArray[j] + " ");  // display it
     System.out.println("");
  }
//-----------------------------------------------------------
public void mergeSort()           // called by main()
  {                              // provides workspace
    String[] workSpace = new String[nElems];
    recMergeSort(workSpace, 0, nElems-1);
  }
//-----------------------------------------------------------
private void recMergeSort(String[] workSpace, int lowerBound,
                                           int upperBound)
  {
  if(lowerBound == upperBound)            // if range is 1,
     return;                              // no use sorting
 else
     {                                    // find midpoint
     int mid = (lowerBound+upperBound) / 2;
                                         // sort low half
    recMergeSort(workSpace, lowerBound, mid);
                                         // sort high half
     recMergeSort(workSpace, mid+1, upperBound);
                                         // merge them
     merge(workSpace, lowerBound, mid+1, upperBound);
     }  // end else
  }  // end recMergeSort()
//-----------------------------------------------------------
private void merge(String[] workSpace, int lowPtr,
                       int highPtr, int upperBound)
  {
    int j = 0;                             // workspace index
    int lowerBound = lowPtr;
    int mid = highPtr-1;
    int n = upperBound-lowerBound+1;       // # of items

    while(lowPtr <= mid && highPtr <= upperBound)
            if(  theArray[highPtr].compareTo(theArray[lowPtr])> 0)
           workSpace[j++] = theArray[lowPtr++];
     else
        workSpace[j++] = theArray[highPtr++];

   while(lowPtr <= mid)
     workSpace[j++] = theArray[lowPtr++];

   while(highPtr <= upperBound)
     workSpace[j++] = theArray[highPtr++];

  for(j=0; j<n; j++)
     theArray[lowerBound+j] = workSpace[j];
  }  // end merge()

}  // end class DArray
////////////////////////////////////////////////////////////////
于 2014-04-27T19:31:05.473 回答