mergesort字符串方法java

Question

我需要使用合并排序与字符串数组有关的帮助。我已经看到了很多用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 +" "); 
} 

当我运行程序它按它的一些正确的，但在所有它不序。

Answer 1

你有一个错字和两个被遗忘的行。以下是固定功能。将它与你的相比较。

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]; 

    } 

Answer 2

我使用归并为字符串数组[]另一种解决方案：

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 
////////////////////////////////////////////////////////////////