`
豌豆苗
  • 浏览: 5444 次
  • 性别: Icon_minigender_1
  • 来自: 上海
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

java完美实现快速排序

阅读更多
java开发者是不需要考虑排序问题的,因为jdk已经提供了现成的排序功能供你调用。但这并不妨碍我们试图用java代码自己实现一个快速排序功能。
public class QuickSort {
public void sort(int a[],int left,int right){
if(left>=right) return;
int i=left, j=right, key=a[i]; //开始时key在i位置
while(i<j){
for(; i<j; j--){
if(a[j]<key) { a[i]=a[j]; a[j]=key; break; } //key交换到了j位置
}
for(; i<j ;i++){
if(a[i]>key) { a[j]=a[i]; a[i]=key; break; } //key交换到了i位置
}
} //while循环结束后,i=j,并且key就被交换到了这个正确的位置
sort(a,left,i-1); //i位置左边排序
sort(a,i+1,right); //i位置右边排序
}
public static void main(String[] stra){
int a[]={3,4,5,8,7,6,1,2,9,5};
QuickSort qs = new QuickSort();
qs.sort(a,0,a.length-1);
for (int i=0;i<a.length;i++) {System.out.println(a[i]);}
}
}

  设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。   
一趟快速排序的算法是:   
1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;   
2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];   
3)从J开始向前搜索,即由后开始向前搜索(J=J-1即J--),找到第一个小于key的值A[j],A[j]与A[i]交换;   
4)从I开始向后搜索,即由前开始向后搜索(I=I+1即I++),找到第一个大于key的A[i],A[i]与A[j]交换;   
5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。)
0
0
分享到:
评论

相关推荐

    经典算法(C&JAVA实现)

    快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 循序搜尋法(使用衛兵) 二分搜尋法(搜尋原則的代表) 插補搜尋法 費氏搜尋法 稀疏矩陣 多維矩陣轉一維矩陣 上三角、下...

    基于Java的论坛系统,前端Html+CSS+JS实现,后端Java实现,Eclipse完美运行!

    基于Java的论坛系统,前端使用Html+CSS+JS实现,后端使用Java语言开发,技术栈包括但不...4、排行榜:排行榜是通过Redis的有序集合来实现的,可以快速实现topK排序。 5、关注和共同关注:通过Redis的集合数据结构实现。

    经典常用算法(含代码)

    经典常用算法解析与实现,通过Java C语言分别实现各种算法,图文并茂,描述很详细! 主要包括如下算法,很全面! 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 八个...

    JAVA上百实例源码以及开源项目

    百度云盘分享 ... Java实现的FTP连接与数据浏览程序,实现实例化可操作的窗口。  部分源代码摘录:  ftpClient = new FtpClient(); //实例化FtpClient对象  String serverAddr=jtfServer.getText();...

    Java和C语言实现各种经典算法(含代码图例)

    Java和C语言实现各种经典算法(含代码图例) 老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包...

    JAVA上百实例源码以及开源项目源代码

     Java实现的FTP连接与数据浏览程序,实现实例化可操作的窗口。  部分源代码摘录:  ftpClient = new FtpClient(); //实例化FtpClient对象  String serverAddr=jtfServer.getText(); //得到服务器地址  ...

    java 面试题 总结

    Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 10、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap...

    leetcode2-Algorithms:算法导论

    阅读过程中实现的部分算法(Java版)。 已实现的算法(后续持续更新。。。) chapter 2 插入排序 归并排序 chapter 3 最大子数组问题 chapter 6 堆 数据结构 堆排序 chapter 7 快速排序 快速排序(随机增强版) ...

    java笔试题算法-big-data-made-easy:大数据变得容易

    内存的快速且稳定的排序算法。 公共区域 。 - C++/Python 中的近似最近邻优化内存使用和加载/保存到磁盘。 - 一个带有简洁存储的 ngram 工具包。 - 近似集合成员查询的布隆过滤器替换。 - 动态布谷鸟过滤器。 - 紧密...

    asp.net知识库

    一完美的关于请求的目录不存在而需要url重写的解决方案! 在C#中实现MSN消息框的功能 XmlHttp实现无刷新三联动ListBox 鼠标放在一个连接上,会显示图片(类似tooltip) 使用microsoft.web.ui.webcontrols的TabStrip与...

    算法导论(part1)

    书中的算法以英语加伪代码的形式给出,只要有一点程序设计经验的人都能读懂,并可以用任何计算机语言(如C/C++和Java等)方便地实现。在书中,作者将算法的讨论集中在一些比较现代的例子上,它们来自分子生物学(如...

    算法导论(part2)

    书中的算法以英语加伪代码的形式给出,只要有一点程序设计经验的人都能读懂,并可以用任何计算机语言(如C/C++和Java等)方便地实现。在书中,作者将算法的讨论集中在一些比较现代的例子上,它们来自分子生物学(如...

    贞龙jsp版本CMS(BIZOSSCMS)高性能内容管理系统正式版

    BIZOSS-CMS采用JAVA+MySQL技术开发,内置了贞龙公司的SOA框架,在我们的支持下可以实现和贞龙系列产品和其他第三方企业内部应用无缝连接。BIZOSS-CMS的静态化机制和全文检索机制支持数十万、上百万的数据量快速查找...

    Toad 使用快速入门

    Toad还可以外挂一些别的产品,比如PL/Formatter, RevealNet Knowledge Base , SQL Impact等,这些都能够和Toad紧密集成,共同提供了一个完美的集成开发环境。新版本还新增加了DBA模块,更加拓广了Toad这个产品的适用...

    编程新手真言......

    6.19 快速排序思想 130 6.20 数据结构之数组 131 6.21 数据结构的抽象名字 132 6.22 真正的ADT 133 6.23 Vector的观点 135 6.24 真正的数据结构 136 6.25 堆栈与队列 138 6.26 真正的递归 140 6.27 树与单链表,图 ...

    高效算法:竞赛、应试与提高必修128例.[法] Christoph Dürr Jill-Jênn Vie(带书签文字版).pdf

    本书旨在探讨如何优化算法效率,详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证过程,内容由浅入深,能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧,是参加ACM ICPC、Google...

    XML轻松学习手册--XML肯定是未来的发展趋势,不论是网页设计师还是网络程序员,都应该及时学习和了解

    分别是XML快速入门,XML的概念,XML的术语,XML的实现,XML的实例分析。最后附录介绍了XML的相关资源。作者站在普通网页设计人员的角度,用平实生动的语言,向您讲述XML的方方面面,帮助你拨开XML的神秘面纱,快速...

    C#微软培训资料

    15.4 接口的实现 .182 15.5 抽象类与接口 .195 15.6 小 结 .196 第十六章 组织应用程序 .198 16.1 基 本 概 念 .198 16.2 使用名字空间 .200 16.3 使用指示符 .203 16.4 程 序 示 例 .206 16.5 小 ...

Global site tag (gtag.js) - Google Analytics