java排序算法[Java编程]

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,再对其举行排序.后者的效率要高得多.这种除非绝对必要,不然就不采纳行动的办法叫作“怠惰求值”（还有一种近似的技术叫作“怠惰初始化”——除非真的需求一个字段值,不然不举行初始化）.