最快排序和搜索算法的最简代码实现 转 2009-04-21 13:17
前言
算法的核心问题是排序和搜索。这2个领域应用最广，研究也最透。本文我将讲解排序和搜索领域最高效的两个算法：快速排序算法和二分搜索算法。
教科书和很多实现库给出的这两个算法的代码非常复杂，很难理解，本文中我给出的代码是最简单的实现代码，易于理解，效率也很高。
缘起
刚才有人问我怎样实现快速排序，我在5分钟之内写了一个快速排序的Java代码出来，不知道他们有没有理解。
因此，我想到要写作这篇文章。介绍一下快速排序算法和二分搜索算法的最简实现。
我的二分搜索算法是在我用Flex开发工作流编辑器时实现的。当时的需求是在2个图形之间画出连接线，要求根据鼠标操作来绘制，并且线段的起点和终点都是在图形的外框上。
上面的描述可能比较抽象，这么说吧，原来我实现的GUI效果是，2个方框，使用鼠标把它们连接起来，我绘制的线是鼠标点下和释放这2个端点连接起来的线段。但是，这样的线段比较丑，客户要求线段的两头应该在2个方框的边框上。
怎么解决这个问题呢？我把线段看做是排序后的点的集合，然后就可以使用二分搜索算法搜索到线段和边框的交点，然后把它们绘制出来。 当时的二分搜索算法是用ActionScript3写的，现在我把它改成Java了。
快速排序算法和二分搜索算法
算法主要分为排序算法、搜索算法、图算法。图算法我用得不多，没有发言权，本文就不说了。
排序算法中最快的是快速排序算法，搜索算法中最快的是二分搜索算法。我也最喜欢这2个算法。
因为，它们是使用递归实现的，代码简洁清晰，效率又非常高。 根据我的理解，算法的本质就是数学。根据输入和设定的目标，采用有限的步骤实现输出。通常，使用计算机实现的算法，都会用到循环，这样才能发挥计算机高速运算的优势。
循环和递归是等效的，这已经被科学家所证明。数学上没有循环，只有递归的概念，因此使用递归代替循环表示算法有很多好处： 1， 递归的代码要比循环简洁很多，也优雅很多。
2， 递归的代码可以用数学方式建模，可以从数学角度验证其正确性。 很多函数式语言甚至没有循环的概念和关键字，强迫你使用递归来实现循环。如，ErLang。
递归也有一些缺点，递归使用栈来保存函数地址和参数、返回值，而栈是有一定大小的，过多的递归调用可能会造成栈溢出。
但是，递归算法会容易转变为循环。我更欣赏递归的简洁，除非真的出现栈溢出的问题，我是不会使用循环的。
二分搜索算法
理论：
二分搜索算法用于针对已排序的集合进行搜索。 它的原理是：
1， 找到排序数组的中间元素，如果它匹配目标值，那么就返回它在数组中的索引。
2， 如果没有找到，那么判断中间值比目标值大还是小，
如果中间值比目标值大，那么就对第一个元素到middle-1的元素递归这个过程。 如果中间值比目标值小，那么就对middle+1到最后一个元素。 3， 如果结束的索引小于开始的索引，返回-1，表示没有找到。
4， 如果子集合有2个元素，那么各自比较。因为Java的整数除法会舍弃小数，如果数组只有2个元素，那么middle值一直都是第一个元素。
经过上述的递归过程，最终将返回匹配元素的索引，或者是-1，表示找不到。 二分搜索算法之所以速度快，是因为它每次可以把数组切分成两半，每次递归调用都能去除一半数据，而不用匹配每一个数据。
代码：
下面是代码，逻辑清楚，代码简单。 /**
* by 沈东良/良少 http://blog.csdn.net/shendl/ * @param array * @param start
* @param end 这是最后一个元素的索引，第一次调用应该是array.length-1 * @param value * @return */
public static int binarySearch(int[] array,int start,int end,int value){
int middle=(start+end)/2; if(end if(end==(start+1)){ if(array[start]==value){ return start; }else if(array[end]==value){ return end; } }else if(array[middle]==value){ return middle; }else if(value>array[middle]){ return binarySearch(array,middle+1,end,value); }else if(value return binarySearch(array,start,middle-1,value); } return -1; } 上述代码稍加改变，就可以排序任意类型。如使用泛型，然后加上对Comparable接口的实现，即可。 快速排序算法 二分搜索算法确实非常快，但是它只能用于已排序数组。如果数组未排序呢，该怎么办呢？简单，先用快速排序算法进行排序，然后再用二分搜索进行搜索。 先排序再搜索，要比匹配每一个元素快得多。搜索引擎，数据库索引也都使用了对数据集合的排序技术，这样搜索数据才会快速。 理论： 最慢，也是最容易想到的排序算法是插入排序算法： 1， 遍历数组，找出最小的元素，把它放到第一个元素。
相关推荐：
loading