很多了学了各种排序算法比如 冒泡排序,快速排序,可书本上仅仅是介绍几个数字的排序,那么如何把它应用到真正的工作中呢。这事实上是一个算法的通用性设计问题。如果了解过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;
}
}
责任编辑:小草