我们这里主要以快速排序为例子具体说明（因为我个人现在兴趣在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()方法都是从父类继承过来的。
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;
}
}
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()方法，这样封装性更好一些。同时我们可以覆盖更多的原有的父类的方法，使之更适合我们的需要。
今天就先写到这里...希望能和大家多多交流。
