分享
 
 
 

Java中的排序

王朝java/jsp·作者佚名  2008-05-31
窄屏简体版  字體: |||超大  

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())

}

public boolean

lessThanOrEqual(Object l, Object r) {

return ((String)l).toLowerCase().compareTo(

((String)r).toLowerCase())

}

}

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())

}

public boolean

lessThanOrEqual(Object l, Object r) {

return

((String)l).toLowerCase().compareTo(

((String)r).toLowerCase())

}

}

);

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中的类型检查会照旧进行;假如真的有什么错误,运行期间会简单地产生一个违例。事实上,我们在编译或运行期间能保

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有