《程序员(初级)学习宝典大全》由会员分享，可在线阅读，更多相关《程序员(初级)学习宝典大全（146页珍藏版）》请在金锄头文库上搜索。
1、 最快排序和搜索算法的最简代码实现最快排序和搜索算法的最简代码实现算法的核心问题是排序和搜索。这 2 个领域应用最广，研究也最透。本文我将讲解排序和 搜索领域最高效的两个算法：快速排序算法和二分搜索算法。教科书和很多实现库给出的这两个算法的代码非常复杂，很难理解，本文中给出的代 码是最简单的实现代码，易于理解，效率也很高。缘起二分搜索算法是在我用 Flex 开发工作流编辑器时实现的。当时的需求是在 2 个图形之 间画出连接线，要求根据鼠标操作来绘制，并且线段的起点和终点都是在图形的外框上。上面的描述可能比较抽象，这么说吧，原来我实现的 GUI 效果是，2 个方框，使用鼠 标把它们连接起来，我绘
2、制的线是鼠标点下和释放这 2 个端点连接起来的线段。但是，这 样的线段比较丑，客户要求线段的两头应该在 2 个方框的边框上。怎么解决这个问题呢？我把线段看做是排序后的点的集合，然后就可以使用二分搜索 算法搜索到线段和边框的交点，然后把它们绘制出来。当时的二分搜索算法是用 ActionScript3 写的，现在我把它改成 Java 了。快速排序算法和二分搜索算法算法主要分为排序算法、搜索算法、图算法。图算法我用得不多，没有发言权，本文 就不说了。排序算法中最快的是快速排序算法，搜索算法中最快的是二分搜索算法。我也最喜欢 这 2 个算法。因为，它们是使用递归实现的，代码简洁清晰，效率又非常高。根据
3、我的理解，算法的本质就是数学。根据输入和设定的目标，采用有限的步骤实现 输出。通常，使用计算机实现的算法，都会用到循环，这样才能发挥计算机高速运算的优 势。循环和递归是等效的，这已经被科学家所证明。数学上没有循环，只有递归的概念， 因此使用递归代替循环表示算法有很多好处：1， 递归的代码要比循环简洁很多，也优雅很多。2， 递归的代码可以用数学方式建模，可以从数学角度验证其正确性。很多函数式语言甚至没有循环的概念和关键字，强迫你使用递归来实现循环。如， ErLang。递归也有一些缺点，递归使用栈来保存函数地址和参数、返回值，而栈是有一定大小的，过多的递归调用可能会造成栈溢出。但是，递归算法会容易
4、转变为循环。我更欣赏递归的简洁，除非真的出现栈溢出的问 题，我是不会使用循环的。二分搜索算法理论：二分搜索算法用于针对已排序的集合进行搜索。它的原理是：1， 找到排序数组的中间元素，如果它匹配目标值，那么就返回它在数组中的索引。2， 如果没有找到，那么判断中间值比目标值大还是小，如果中间值比目标值大，那么就对第一个元素到 middle-1 的元素递归这个过程。如果中间值比目标值小，那么就对 middle+1 到最后一个元素。3， 如果结束的索引小于开始的索引，返回-1，表示没有找到。4， 如果子集合有 2 个元素，那么各自比较。因为 Java 的整数除法会舍弃小数，如果 数组只有 2 个元素，
5、那么 middle 值一直都是第一个元素。经过上述的递归过程，最终将返回匹配元素的索引，或者是-1，表示找不到。二分搜索算法之所以速度快，是因为它每次可以把数组切分成两半，每次递归调用都 能去除一半数据，而不用匹配每一个数据。代码：下面是代码，逻辑清楚，代码简单。/* param array* param start* param end 这是最后一个元素的索引，第一次调用应该是 array.length-1* param value* return*/public static int binarySearch(int array,int start,int end,int value)in
6、t middle=(start+end)/2;if(endarraymiddle)return binarySearch(array,middle+1,end,value);else if(valueend 因为递归调用时 j+1，可能引起 j 比 end 还大 1。 另外如果 数组是空的，或者输入错误也会出现这种情况if(end=它的元素位置互换，这样数组就分成 2 个部分，一个部分比 中心值小，一个部分比中心值大。tmp=arrayj;arrayj=arrayend;arrayend=tmp;quickSort(array,start,j);quickSort(array,j+1,end)
7、;Java 的 Arrays 类也使用快速排序算法进行排序。但它的代码写得像天书一样。提高快速排序算法执行效率的主要方法是对中心点进行检测，希望选中的中心点有更 大的概率是整个数组的中值。我的实现中简单的选择数组中间的值作为中心点，一般来说这样的选择效率还是不错的。注意上面的一项实现技术，我们使用把中心数据元素移到数组最后的方式实现了数组 的就地比较。这是比较常用的技术，把数据移到数组的最前面或者最后面，方便比较数据。另外，我的 Java 快速排序代码使用了“副作用” ，而在纯函数式语言，如 Haskell,ErLang 中是没有“副作用”的，也就是说变量不可以重新赋值。此时就需要返回 值，每
8、次都创建新的子数组。但函数式语言的数组处理功能很强，也会做很多性能优化， 因此函数式语言实现快速排序代码更加简单，没有“副作用” ，也更加数学化。自己做的存储过程，使用了指针，并调用了外部了时间参数！自己做的存储过程，使用了指针，并调用了外部了时间参数！基本的功能是这样的：通过在程序中选择一个时间，根据这个时间来选择符合条件的数据， 并将它插入某个表。插入的时候，要进行一个判断，如果这个记录已经存在了，就不插入， 不存在的话就插入该数据，这个是用游标来实现的。CURSOR acc_c IS /* 定义游标,从表中选出记录 */select from where/*原语句 a.DATE= */t
9、o_date(+a.DATE,J)= to_date(ParaTime,YYYY-MM-DD) and/* 将时间参 数赋给选择语句*/acc_r acc_c%ROWTYPE;/* 变量 acc_r 与 acc_c 类型相同*/AmountToMove NUMBER;BEGINOPEN acc_c;LOOPFETCH acc_c INTO acc_r;EXIT WHEN acc_c%NOTFOUND; /*记录不存在时退出*/begininsert into /*记录存在时插入*/values EXCEPTION when others then null;end;END LOOP ;comm
10、it;CLOSE acc_c ; /*关闭指针*/*修改表*/ update (select from(select from where/*原语句 a.DATE= */to_date(+a.DATE,J)= to_date(ParaTime,YYYY-MM-DD) and/*将时间 参数赋给选择语句*/ where where EndDate=to_date(ParaTime,YYYY-MM-DD);/*原语句 where to_number(to_char(EndDate,J)=+;*/commit;END;自己打包自己打包 JDK 到到 J2EE 服务器中服务器中第一步： 需要把 jdk
11、 目录拷贝到 jboss 目录中比如起名叫 jdk1.5.0_06目录结构如下：jboss-4.0.3SP1-| .bin| .client| .jdk1.5.0_06| .lib| .server| .docs注意：这里是 jdk 而不是 jre 各位同仁注意了第二步：修改 run.bat 文件这里我说下自己的实现方式、一般开发自己都配置 JAVA_HOME 的但是希望给客户的 时候直接打包好。但是又不希望修改用户服务器的环境（或者服务器上存在别的 j2ee 服务 器以免冲突）这里实现是 判断用户机器是否存在 JAVA_HOME 环境变量，如果存在则直接使用客 户机上的环境（故本配置十分灵活
12、）修改 run.bat 地方： 大家找到 在 ：FOUND_RUN_JAR 和 ：ADD_TOOLS 之间的代码原来为如下：view plaincopy to clipboardprint?if not “%JAVA_HOME%“ = “ goto ADD_TOOLSset JAVA=javaecho JAVA_HOME is not set. Unexpected results may occur.echo Set JAVA_HOME to the directory of your local JDK to avoid this message.goto SKIP_TOOLSif not
13、 “%JAVA_HOME%“ = “ goto ADD_TOOLSset JAVA=javaecho JAVA_HOME is not set. Unexpected results may occur.echo Set JAVA_HOME to the directory of your local JDK to avoid this message.goto SKIP_TOOLS 说明：原来是判断机器是否存在%JAVA_HOME%变量 如果存在则执行 ADD_TOOLS 往下执行，如果不存在 则执行 SKIP_TOOLS 跳出命令行 打印出 echo JAVA_HOME is not se
14、t. Unexpected results may occur.echo Set JAVA_HOME to the directory of your local JDK to avoid this message. 信息，所以 大家看明白的话 继续。现修改为如下view plaincopy to clipboardprint?if “%JAVA_HOME%“ = “ goto CONTINUEgoto ADD_TOOLS:CONTINUEecho Could not locate %JAVA_HOME% and set %JAVA_HOME%=.jdk1.5.0.06set JAVA_HOM
15、E=.jdk1.5.0_06if “%JAVA_HOME%“ = “ goto CONTINUEgoto ADD_TOOLS:CONTINUEecho Could not locate %JAVA_HOME% and set %JAVA_HOME%=.jdk1.5.0.06set JAVA_HOME=.jdk1.5.0_06说明：现在改为先判断机器是否存在%JAVA_HOME%如果不存在则执行 CONTINUE 这 里本人把 JAVA_HOME 设置为针对当前 dir 的相对路径 即第一步中大家拷贝的 jdk 到 jboss 中的目录 set JAVA_HOME=jdk1.5.0_06如果存在
16、 java_home 的话 则继续执行 ADD_TOOLS 往下执行 goto ADD_TOOLS，所以 这里即使服务器没有配置环境变量照样可以使用 jboss 中自己拷贝的 jdk 了。Examda 提示小需求：如果碰到客户服务器装有别的 j2ee 服务程序，但是你自己的工 程和机器本身的环境不兼容。这里修改 run.bat 可固定设置为使用自己的 jdk.view plaincopy to clipboardprint?if “%JAVA_HOME%“ = “ goto CONTINUEset JAVA_HOME=.jdk1.5.0_06goto ADD_TOOLS:CONTINUEecho Could not locate %JAVA_HOME% and set %JAVA_HOME%=.jdk1.5.0.06set JAVA_H
