2.5 Sorting Application

Java的约定使得我们能够利用Java的回调机制将任意实现了Comparable的数据类型排序。
实现Comparable接口只需要定义一个compareTo()函数并在其中定义该类型数据的大小关系。

指针排序
我们使用的方法在经典的教材中被称为指针排序，因为我们只处理元素的引用而不移动数据本身。除了原始数据类型之外，我们操作的总是数据的引用。
多种排序方法
Java的Comparator方法允许我们在一个类中实现多种排序方法。用Comparator接口来代替Comparable接口能够更地将数据类型的定义和两个该类型的对象应该如何比较的定义区分开来。
稳定性：
如果一个排序算法能够用保留数组中重复元素的相对位置可以被称为稳定的。

统计a[]中不重复元素的个数：

Quick.sort(a);
int count = 0;//假设a.length > 0
for(int i=0; i < a.length; i++)
    if(a[i].compareTo(a[i+1]) != 0)
        count ++;

找出一组数中的第k小元素：

public static Comparable select(Comparable[] a, int k){
    StdRandom.shuffle(a);
    int lo = 0, hi = a.length - 1;
    while(hi > lo){
        int j = partition(a, lo, hi);
        if(j == k) return a[k];
        else if(j > k) hi = j - 1;
        else if(j < k) lo = j + 1;
    }
    return a[k];
}

partition()方法会将数组a[lo]至a[hi]重新排列并返回一个整数j使得a[lo..j-1]小于等于a[j]且a[j+1..hi]大于等于a[j]。

Exercise

Consider the following implementation of the compareTo() method for String. How does the third line help with efficiency?

public int compareTo(String t){
    String s = this;
    if(s == t) return 0;
    int n = Math.min(s.length(), t.length());
    for(int i=0; i < n; i++){
        if     (s.charAt(i) < t.charAt(i)) return -1;
        else if(s.charAt(i) > t.charAt(i)) return +1;
    }
    return s.length() - t.length();
}

Solution:it avoid directly comparing individual characters if s and t are references to the same string

Write a program Frequency.java that reads strings from standard input and prints the number of times each string occurs, in descending order of frequency.

Creative Problems

Scheduling. Write a program SPT.java that reads job names and processing times from standard input and prints a schedule that minimizes average completion time, as described in the text.
Load balancing. Write a program LPT.java that takes an integer M as a command-line argument, reads N job names and processing times from standard input and prints a scheduling assignment the jobs to M processors that approximately minimizes the time when the last job completes, as described in the text.
Sort by reverse domain. Write a data type Domain.java that represents domain names, including an appropriate compareTo() method where the natural order is in order of the reverse domain name. For example, the reverse domain of cs.princeton.edu is edu.princeton.cs. This is useful for web log analysis. Write a client that reads domain names from standard input and prints the reverse domains in sorted order.
Unbiased election. In order to thwart bias against candidates whose names appear toward the end of the alphabet, California sorted the candidates appearing on its 2003 gubernatorial ballot by using the following order:

R W Q O J M V A H B S G Z X N T C I E K U P D Y F L

Create a data type California.java where this is the natural order. Write a client that sorts strings according to this ordering. Assume that each string is comprised solely of uppercase letters.

Exercise

Creative Problems

Web exercise(N)