8.5 排序

8.5 排序

Java 1.0 和 1.1 库都缺少的一样东西是算术运算,甚至没有最简单的排序运算方法。因此,我们最好创建一个 Vector,利用经典的 Quicksort(快速排序)方法对其自身进行排序。

编写通用的排序代码时,面临的一个问题是必须根据对象的实际类型来执行比较运算,从而实现正确的排序。当然,一个办法是为每种不同的类型都写一个不同的排序方法。然而,应认识到假若这样做,以后增加新类型时便不易实现代码的重复利用。

程序设计一个主要的目标就是“将发生变化的东西同保持不变的东西分隔开”。在这里,保持不变的代码是通用的排序算法,而每次使用时都要变化的是对象的实际比较方法。因此,我们不可将比较代码“硬编码”到多个不同的排序例程内,而是采用“回调”技术。利用回调,经常发生变化的那部分代码会封装到它自己的类内,而总是保持相同的代码则“回调”发生变化的代码。这样一来,不同的对象就可以表达不同的比较方式,同时向它们传递相同的排序代码。

下面这个“接口”(Interface)展示了如何比较两个对象,它将那些“要发生变化的东西”封装在内:

//: Compare.java
// Interface for sorting callback:
package c08;

interface Compare {
  boolean lessThan(Object lhs, Object rhs);
  boolean lessThanOrEqual(Object lhs, Object rhs);
} ///:~

对这两种方法来说,lhs 代表本次比较中的“左手”对象,而 rhs 代表“右手”对象。

可创建 Vector 的一个子类,通过 Compare 实现“快速排序”。对于这种算法,包括它的速度以及原理等等,在此不具体说明。欲知详情,可参考 Binstock 和 Rex 编著的《Practical Algorithms for Programmers》,由 Addison-Wesley 于 1995 年出版。

//: SortVector.java
// A generic sorting vector
package c08;
import java.util.*;

public class SortVector extends Vector {
  private Compare compare; // To hold the callback
  public SortVector(Compare comp) {
    compare = comp;
  }
  public void sort() {
    quickSort(0, size() - 1);
  }
  private void quickSort(int left, int right) {
    if(right > left) {
      Object o1 = elementAt(right);
      int i = left - 1;
      int j = right;
      while(true) {
        while(compare.lessThan(
              elementAt(++i), o1))
          ;
        while(j > 0)
          if(compare.lessThanOrEqual(
             elementAt(--j), o1))
            break; // out of while
        if(i >= j) break;
        swap(i, j);
      }
      swap(i , right);
      quickSort(left, i-1);
      quickSort(i+1, right);
    }
  }
  private void swap(int loc1, int loc2) {
    Object tmp = elementAt(loc1);
    setElementAt(elementAt(loc2), loc1);
    setElementAt(tmp, loc2);
  }
} ///:~

现在,大家可以明白“回调”一词的来历,这是由于 quickSort()方法“往回调用”了 Compare 中的方法。从中亦可理解这种技术如何生成通用的、可重复利用(再生)的代码。

为使用 SortVector,必须创建一个类,令其为我们准备排序的对象实现 Compare。此时内部类并不显得特别重要,但对于代码的组织却是有益的。下面是针对 String 对象的一个例子:

//: StringSortTest.java
// Testing the generic sorting Vector
package c08;
import java.util.*;

public class StringSortTest {
  static class StringCompare implements Compare {
    public boolean lessThan(Object l, Object r) {
      return ((String)l).toLowerCase().compareTo(
        ((String)r).toLowerCase()) < 0;
    }
    public boolean
    lessThanOrEqual(Object l, Object r) {
      return ((String)l).toLowerCase().compareTo(
        ((String)r).toLowerCase()) <= 0;
    }
  }
  public static void main(String[] args) {
    SortVector sv =
      new SortVector(new StringCompare());
    sv.addElement("d");
    sv.addElement("A");
    sv.addElement("C");
    sv.addElement("c");
    sv.addElement("b");
    sv.addElement("B");
    sv.addElement("D");
    sv.addElement("a");
    sv.sort();
    Enumeration e = sv.elements();
    while(e.hasMoreElements())
      System.out.println(e.nextElement());
  }
} ///:~

内部类是“静态”(Static)的,因为它毋需连接一个外部类即可工作。

大家可以看到,一旦设置好框架,就可以非常方便地重复使用象这样的一个设计——只需简单地写一个类,将“需要发生变化”的东西封装进去,然后将一个对象传给 SortVector 即可。

比较时将字串强制为小写形式,所以大写 A 会排列于小写 a 的旁边,而不会移动一个完全不同的地方。然而,该例也显示了这种方法的一个不足,因为上述测试代码按照出现顺序排列同一个字母的大写和小写形式:A a b B c C d D。但这通常不是一个大问题,因为经常处理的都是更长的字串,所以上述效果不会显露出来(Java 1.2 的集合提供了排序功能,已解决了这个问题)。

继承(extends)在这儿用于创建一种新类型的 Vector——也就是说,SortVector 属于一种 Vector,并带有一些附加的功能。继承在这里可发挥很大的作用,但了带来了问题。它使一些方法具有了 final 属性(已在第 7 章讲述),所以不能覆盖它们。如果想创建一个排好序的 Vector,令其只接收和生成 String 对象,就会遇到麻烦。因为 addElement()和 elementAt()都具有 final 属性,而且它们都是我们必须覆盖的方法,否则便无法实现只能接收和产生 String 对象。

但在另一方面,请考虑采用“合成”方法:将一个对象置入一个新类的内部。此时,不是改写上述代码来达到这个目的,而是在新类里简单地使用一个 SortVector。在这种情况下,用于实现 Compare 接口的内部类就可以“匿名”地创建。如下所示:

//: StrSortVector.java
// Automatically sorted Vector that
// accepts and produces only Strings
package c08;
import java.util.*;

public class StrSortVector {
  private SortVector v = new SortVector(
    // Anonymous inner class:
    new Compare() {
      public boolean
      lessThan(Object l, Object r) {
        return
          ((String)l).toLowerCase().compareTo(
          ((String)r).toLowerCase()) < 0;
      }
      public boolean
      lessThanOrEqual(Object l, Object r) {
        return
          ((String)l).toLowerCase().compareTo(
          ((String)r).toLowerCase()) <= 0;
      }
    }
  );
  private boolean sorted = false;
  public void addElement(String s) {
    v.addElement(s);
    sorted = false;
  }
  public String elementAt(int index) {
    if(!sorted) {
      v.sort();
      sorted = true;
    }
    return (String)v.elementAt(index);
  }
  public Enumeration elements() {
    if(!sorted) {
      v.sort();
      sorted = true;
    }
    return v.elements();
  }
  // Test it:
  public static void main(String[] args) {
    StrSortVector sv = new StrSortVector();
    sv.addElement("d");
    sv.addElement("A");
    sv.addElement("C");
    sv.addElement("c");
    sv.addElement("b");
    sv.addElement("B");
    sv.addElement("D");
    sv.addElement("a");
    Enumeration e = sv.elements();
    while(e.hasMoreElements())
      System.out.println(e.nextElement());
  }
} ///:~

这样便可快速再生来自 SortVector 的代码,从而获得希望的功能。然而,并不是来自 SortVector 和 Vector 的所有 public 方法都能在 StrSortVector 中出现。若按这种形式再生代码,可在新类里为包含类内的每一个方法都生成一个定义。当然,也可以在刚开始时只添加少数几个,以后根据需要再添加更多的。新类的设计最终会稳定下来。

这种方法的好处在于它仍然只接纳 String 对象,也只产生 String 对象。而且相应的检查是在编译期间进行的,而非在运行期。当然,只有 addElement()和 elementAt()才具备这一特性;elements()仍然会产生一个 Enumeration(枚举),它在编译期的类型是未定的。当然,对 Enumeration 以及在 StrSortVector 中的类型检查会照旧进行;如果真的有什么错误,运行期间会简单地产生一个异常。事实上,我们在编译或运行期间能保证一切都正确无误吗?(也就是说,“代码测试时也许不能保证”,以及“该程序的用户有可能做一些未经我们测试的事情”)。尽管存在其他选择和争论,使用继承都要容易得多,只是在造型时让人深感不便。同样地,一旦为 Java 加入参数化类型,就有望解决这个问题。

大家在这个类中可以看到有一个名为“sorted”的标志。每次调用 addElement()时,都可对 Vector 进行排序,而且将其连续保持在一个排好序的状态。但在开始读取之前,人们总是向一个 Vector 添加大量元素。所以与其在每个 addElement()后排序,不如一直等到有人想读取 Vector,再对其进行排序。后者的效率要高得多。这种除非绝对必要,否则就不采取行动的方法叫作“懒惰求值”(还有一种类似的技术叫作“懒惰初始化”——除非真的需要一个字段值,否则不进行初始化)。

上一页
下一页