Wednesday 23 July 2008

排序算法 通用化设计

很多了学了各种排序算法比如 冒泡排序,快速排序,可书本上仅仅是介绍几个数字的排序,那么如何把它应用到真正的工作中呢。这事实上是一个算法的通用性设计问题。如果了解过C++ STL的人就知道这种设计思想与原理。

我们这里主要以快速排序为例子具体说明(因为我个人现在兴趣在java,所以实现都用java实现,有时间的话我会分别用C与C++实现)。

知识准备:java 语言,快速排序的实现思想

开发环境:eclipse, jdk1.6

我们先简单的回顾一下快速排序的思想(事实上这个算法并不好讲解,总之,我尽力,有不明白的可以留言或者发邮件联系我(allwefantasy@gmail.com)):

给定一个数组,int[] array={42,8,63,15,94,23,69,75,3,61,37}

这个数组便是我们需要排序的数组。

首先我们选择其中的一个数字,比方说最右边的,37,我们称之为 枢纽(为什么叫枢纽,因为英文pivot翻译过来的)。然后我们想办法把数组中比37小的放在37的左边,比它大的放在右边(我们先不管如何实现这个放置的算法,待会我们再来讨论&&注意,最后的结果是比三十七小的我们都放 在它的左边,大的都在右边,并且37的左边和右边都是无序的),于是便有这么一个数组:3,8,23,15,37,63,69,75,42,61,94(这个结果是通过一定的算法实现的,我们后面会讲,它符合我们上面的 要求。)好了,到了这一部,我们知道 ,接着我们只要排序枢纽(也就是37)左边的和又变得就可以了,37肯定已经在正确的位置,因此我们不用理会它了(原因是什么呢,用脚趾头想下)。我们用前面相同的方法,对3,8,23,15 进行排序,也就是选择15为枢纽,重复上面的步骤,肯定又能确定一个数字的真确位置,比如15的真确位置应该是3,8,15,23。接着我们再对3,8进行排序(你也许会说,这还要排序吗,一眼就能看出来已经是有序的了,但识别忘了,计算机可使很笨的,它不知道),选择8位枢纽,所以排序结果是3,8 。在对3排序(其实已经到了终止条件了,也就是只剩下一个元素)也就是最终37左边的排序结果出来了 是 3,8,15,23。同理可以推出 右边的。

好了,现在可以讲下如何将枢纽放到正确位置上的算法了

42,8,63,15,94,23,69,75,3,61,37

上面11一个数,我们随机选择一个枢纽,前面我们选择37 主要是为了编程序的方便,不然你也可以用 (int) Math.random()*11来随机选择一个。

第1步:left=0,也就是left指向数组第一个元素,也就是42

同理,right=10,指向37

第2步:left递增,如果遇到比37小的就一直递增。如果遇到比37 大的,比如第一个数字,42,那么此时left=0,停止,执行步骤3

第3步:right-1递减,如果遇到比37大的就一直 递减,如果遇到比37小的,停止,比如这里停止在3,也就是right=8,执行第4步

第4步:交换42和3 。继续执行第1步。

终止条件:如果right-left<0,那么就终止

不知道我这么讲大家时候民白了。也许有人更喜欢通过程序来弄明白算法的思想。

下面给出实现的程序:
public int partition(int left,int right,int pivot){

int leftPtr=left-1;
int rightPtr=right;
while(true){

while(pivot>array[++left]){}
while(rightPtr>0&&pivot<array[--right]){}
if(leftPtr<rightPtr)
swap(leftPtr,rightPtr);
else break;
}
swap(leftPtr,right);
return leftPtr;
}
public void swap(int left,int right)
{
int temp=array[left];
array[left]=array[right];
array[right]=temp;

}
}
好了,上面很好解决了一个枢纽放置的问题。下面该如何实现递归循环,将所有的枢纽都排列好呢

其实根据前面的分析,已经有了清晰的思路。下面我们直接用代码说明;
int size=20;
int[] array=new int[size];
public void quickSort(int left,int right){
if(right<=left)
return ;
else{
int pivot=array[right];
int leftPtr=partition(left,right,pivot);
quickSort(left,leftPtr-1);
quickSort(leftPtr+1,right);
}
}
注意前面partition函数返回的是枢纽的位置,应为枢纽已经排好序,所以不需要再排序,所以在quickSort的递归里面不包含他。
整个程序如下:

public class QuickSort {
int size=20;
int[] array=new int[size];
public void quickSort(int left,int right){
if(right<=left)
return ;
else{
int pivot=array[right];
int leftPtr=partition(left,right,pivot);
quickSort(left,leftPtr-1);
quickSort(leftPtr+1,right);
}
}
public int partition(int left,int right,int pivot){

int leftPtr=left-1;
int rightPtr=right;
while(true){

while(pivot>array[++left]){}
while(--right>0&&pivot<array[--right]){}
if(leftPtr<=rightPtr)
swap(leftPtr,rightPtr);
else break;
}
swap(leftPtr,right);
return leftPtr;
}
public void swap(int left,int right)
{
int temp=array[left];
array[left]=array[right];
array[right]=temp;

}
}

既然快速怕需算法我们回顾完了,那么我们学了这个该怎么用呢,比如 我进行排序的不一定是数字啊,可能是字母阿。而且,这些要被排序的不一定在数组里面阿,可能是在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
在写这个程序的时候自己也犯了个小错误,用单步调试 调试了半天才闹出来希望大家能够注意以下:
if(leftPtr
从上面的程序可以看出,如果要比较其他类型的对象,你只要实现相应的Compare类就可以。
这里需要注意的一点。在测试的时候 我们还有一句 qsv.sort().其实我们可以在quickSortVector类中改写elments()方法,这样封装性更好一些。同时我们可以覆盖更多的原有的父类的方法,使之更适合我们的需要。
今天就先写到这里...希望能和大家多多交流。

No comments: