当前位置：天才代写 > tutorial > JAVA 教程 > java排序算法

java排序算法

2017-11-13 08:00 星期一 所属： JAVA 教程 浏览：356

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());
  }
} ///:~

#p#分页标题#e#

这样便可快速再生来自SortVector的代码，从而得到但愿的成果。然而，并不是来自SortVector和Vector的所有public要领都能在StrSortVector中呈现。若按这种形式再生代码，可在新类里为包括类内的每一个要领都生成一个界说。虽然，也可以在刚开始时只添加少数几个，今后按照需要再添加更多的。新类的设计最终会不变下来。
这种要领的长处在于它仍然只采取String工具，也只发生String工具。并且相应的查抄是在编译期间举办的，而非在运行期。虽然，只有addElement()和elementAt()才具备这一特性；elements()仍然会发生一个Enumeration（列举），它在编译期的范例是未定的。虽然，对Enumeration以及在StrSortVector中的范例查抄会还是举办；假如然的有什么错误，运行期间会简朴地发生一个违例。事实上，我们在编译或运行期间能担保一切都正确无误吗？（也就是说，“代码测试时也许不能担保”，以及“该措施的用户有大概做一些未经我们测试的工作”）。尽量存在其他选择和争论，利用担任都要容易得多，只是在造型时让人深感未便。同样地，一旦为Java插手参数化范例，就有望办理这个问题。
各人在这个类中可以看到有一个名为“sorted”的符号。每次挪用addElement()时，都可对Vector举办排序，并且将其持续保持在一个排好序的状态。但在开始读取之前，人们老是向一个Vector添加大量元素。所以与其在每个addElement()后排序，不如一直比及有人想读取Vector，再对其举办排序。后者的效率要高得多。这种除非绝对须要，不然就不采纳动作的要领叫作“懒惰求值”（尚有一种雷同的技能叫作“懒惰初始化”——除非真的需要一个字段值，不然不举办初始化）。

 

    关键字：

天才代写-代写联系方式