java - 快速排序数字(字符串)

Question

仅供引用，我正在 BlueJ 中编程 Java。

我对这门语言还很陌生，并且在使用 QuickSort 时遇到了问题。

我必须修改我的代码，以便它通过电话号码(在本例中是一个字符串)对列表进行排序。

问题是我不确定必须具体修改什么才能使其通过电话号码排序。

我想我必须修改这部分，以便分区元素是第一个元素而不是中间:

partitionelement = data[middle];

但除此之外我不确定。

在当前状态下，它按姓氏对列表进行排序。

这是按姓氏排序时的输出:

Unsorted List:
Smith, John     610-555-7384
Barnes, Sarah   215-555-3827
Riley, Mark     733-555-2969
Getz, Laura     663-555-3984
Smith, Larry    464-555-3489
Phelps, Frank   322-555-2284
Grant, Marsha   243-555-2837

Sorted via QuickSort:
Barnes, Sarah   215-555-3827
Phelps, Frank   322-555-2284
Grant, Marsha   243-555-2837
Riley, Mark     733-555-2969
Smith, John     610-555-7384
Getz, Laura     663-555-3984
Smith, Larry    464-555-3489

这是我的类(class)排序:

public class Sorting{
    /**
     * Swaps to elements in an array. Used by various sorting algorithms.
     * 
     * @param data the array in which the elements are swapped
     * @param index1 the index of the first element to be swapped
     * @param index2 the index of the second element to be swapped
     */
    private static <T extends Comparable<? super T>> void swap(T[] data,
            int index1, int index2){

        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    /**
     * Sorts the specified array of objects using the quick sort algorithm.
     * @param data the array to be sorted
     */
    public static <T extends Comparable<? super T>> void quickSort(T[] data){
        quickSort(data, 0, data.length - 1);
    }

    /**
     * Recursively sorts a range of objects in the specified array using the
     * quick sort algorithm. The parameters min and max represent the range of
     * values on which the sort is performed.
     * 
     * @param data the array to be sorted
     * @param min the minimum index in the range to be sorted
     * @param max the maximum index in the range to be sorted
     */
    public static <T extends Comparable<? super T>> void quickSort(T[] data,
            int min, int max){

        if (min < max){
            // create partitions
            int indexofpartition = partition(data, min, max);

            // sort the left partition (lower values)
            quickSort(data, min, indexofpartition - 1);

            // sort the right partition (higher values)
            quickSort(data, indexofpartition + 1, max);
        }
    }

    /**
     * Used by the quick sort algorithm to find the partition.
     * 
     * @param data the array to be sorted
     * @param min the minimum index in the range to be sorted
     * @param max the maximum index in the range to be sorted
     */
    private static <T extends Comparable<? super T>> int partition(
            T[] data, int min, int max){
       T partitionelement;
       int left, right;
       int middle = (min + max) / 2;


       // use the middle data value as the partition element
       partitionelement = data[middle];
       // move it out of the way for now
       swap(data, middle, min);

       left = min;
       right = max;

       while (left < right){
          // search for an element that is > the partition element
          while (left < right && data[left].compareTo(partitionelement) <= 0)
             left++;

          // search for an element that is < the partition element
          while (data[right].compareTo(partitionelement) > 0)
             right--;

          // swap the elements
          if (left < right)
             swap(data, left, right);
        }

       // move the partition element into place
       swap(data, min, right);

       return right;
    }
}

作为引用，这是我的主类，这是正确的，SortPhoneListQuickSort:

public class SortPhoneListQuickSort{
   /**
    * Creates unsorted list and sorts said list with QuickSort.
    */
   public static void main (String[] args){
      Contact[] friendsArray;

      // List Being Sorted via QuickSort
      friendsArray = Contacts();
      System.out.println("Unsorted List:");
      showFriends(friendsArray);
      Sorting.quickSort(friendsArray);
      System.out.println("Sorted via QuickSort:");
      showFriends(friendsArray);
   }

   /**
    * Prints the friends list.
    */
   private static void showFriends(Contact[] friends){
      for (int i = 0; i < friends.length; i++) {
         System.out.println(friends[i]);
      }
      System.out.println();
   }

   /**
    * Creates unsorted contacts.
    */
  private static Contact[] Contacts(){
      Contact[] friends = new Contact[7];

      friends[0] = new Contact ("John", "Smith", "610-555-7384");
      friends[1] = new Contact ("Sarah", "Barnes", "215-555-3827");
      friends[2] = new Contact ("Mark", "Riley", "733-555-2969");
      friends[3] = new Contact ("Laura", "Getz", "663-555-3984");
      friends[4] = new Contact ("Larry", "Smith", "464-555-3489");
      friends[5] = new Contact ("Frank", "Phelps", "322-555-2284");
      friends[6] = new Contact ("Marsha", "Grant", "243-555-2837");

      return friends;
   }
}

编辑:看来我可能只需要编辑我的 contact 类即可。

联系人类:

public class Contact implements Comparable{
   private String firstName, lastName, phone;

   /**
    * Sets up this contact with the specified information.
    *
    * @param first      a string representation of a first name
    * @param last       a string representation of a last name
    * @param telephone  a string representation of a phone number
    */
   public Contact (String first, String last, String telephone)
   {
      firstName = first;
      lastName = last;
      phone = telephone;
   }

   /**
    * Returns a description of this contact as a string.
    *
    * @return  a string representation of this contact
    */
   public String toString ()
   {
      return lastName + ", " + firstName + "\t" + phone;
   }

   /**
    * Uses both last and first names to determine lexical ordering.
    *
    * @param other  the contact to be compared to this contact
    * @return       the integer result of the comparison
    */
   public int compareTo (Object other)
   {
      int result;

      if (lastName.equals(((Contact)other).lastName))
         result = firstName.compareTo(((Contact)other).firstName);
      else
         result = lastName.compareTo(((Contact)other).lastName);

      return result;
   }
}

Answer 1

如果您的排序类使用泛型，而仅仅为了适应特定的数据类型而修改排序算法的代码，那将是一个糟糕的主意。

您已经将数据包装在 Contact 中类，所以您需要做的就是实现 Comparable<Contact>界面。