既然快速怕需算法我们回顾完了,那么我们学了这个该怎么用呢,比如 我进行排序的不一定是数字啊,可能是字母阿。而且,这些要被排序的不一定在数组里面阿,可能是在vector,Hashtable里面阿,更进步,可能是从数据库里面取出的不确定类型的数据进行排序,如前所述,这涉及到了算法的通用性设计。
我们来分析一下,我们无法通用快速排序算法是因为比较的数据类型不同,但是排序的算法的思想。
编写通用的排序代码时,面临的一个问题是必须根据对象的实际类型来执行比较运算,从而实现正确的排序,而解决方法是“将发生变化的东西同保持不变的东西分隔开”。在这里,保持不变的代码是通用的排序算法,而每次使用时都要变化的是对象的实际比较方法。
我们先来实现一个比较的接口(面向接口编程是被JAVA语言所提倡的,spring便是这种行为的有力证实着)。
interface Compare {
boolean lessThan(Object sou, Object des);
boolean lessThanOrEqual(Object sou, Object des);
}
这是一个比较类。
下面是我改写了前面的快速排序的类;
package com.hailin.www;
import java.util.Vector;
public class QuickSortVector extends Vector{
private Compare compare;
public QuickSortVector(Compare com){
this.compare=com;
}
public void sort(){
quickSort(0,size()-1);
}
public void quickSort(int left,int right){
if(right<=left)
return ;
else{
Object pivot=elementAt(right);
int leftPtr=partition(left,right,pivot);
quickSort(left,leftPtr-1);
quickSort(leftPtr+1,right);
}
}
public int partition(int left,int right,Object pivot){
int leftPtr=left-1;
int rightPtr=right;
while(true){
while(compare.lessThan(elementAt(++leftPtr), pivot)){}
while(rightPtr>0&&compare.lessThan(pivot, elementAt(--rightPtr))){}
if(leftPtr<rightPtr)
swap(leftPtr,rightPtr);
else break;
}
swap(leftPtr,right);
return leftPtr;
}
public void swap(int left,int right)
{
Object temp=elementAt(left);
setElementAt(elementAt(right), left);
setElementAt(temp, right);
}
}
事实上只要把原来int型的改称Object根类就行了。另外,虽然数组的效率比较高,但是不灵活 ,受长度限制,提供的方法少,所以这里我们继承了Vector类。所以里面的size(),elementAt(),setElementAt()方法都是从父类继承过来的。
现在我们可以清楚地看到,假设我们要比较的字符窜,我们只要实现字符窜类的Compare接口 就可以了。
下面我们来实现CompareString类。
public class CompareString implements Compare {
@Override
public boolean lessThan(Object sou, Object des) {
return ((String)sou).toLowerCase().compareTo(((String)des).toLowerCase())<0;
}
@Override
public boolean lessThanOrEqual(Object sou, Object des) {
return ((String)sou).toLowerCase().compareTo(((String)des).toLowerCase())<=0;
}
}
这里大家注意下compareTo()方法,比较此对象与指定对象的顺序,它返回的是一个整数。如果该对象小于、等于或大于指定对象,青年人网提示则分别返回负整数、零或正整数。所以我们必须判断然后返回布尔值。
下面我们给出测试程序:
import java.util.Enumeration;
public class TTest {
public static void main(String[] args) {
QuickSortVector qsv= new QuickSortVector(new CompareString());
qsv.addElement("a");
qsv.addElement("M");
qsv.addElement("b");
qsv.addElement("K");
qsv.addElement("z");
qsv.addElement("y");
qsv.sort();
Enumeration e = qsv.elements();
while(e.hasMoreElements())
System.out.println(e.nextElement());
}
}
程序结果:
a
b
K
M
y
z
在写这个程序的时候自己也犯了个小错误,用单步调试 调试了半天才闹出来希望大家能够注意以下:
从上面的程序可以看出,如果要比较其他类型的对象,你只要实现相应的Compare类就可以。
这里需要注意的一点。在测试的时候 我们还有一句 qsv.sort().其实我们可以在quickSortVector类中改写elments()方法,这样封装性更好一些。同时我们可以覆盖更多的原有的父类的方法,使之更适合我们的需要。
责任编辑:小草