快速排序Java实现

标签: 快速排序 java | 发表时间:2012-09-20 18:53 | 作者:Kaiwii
出处:http://blog.csdn.net

第一、算法原理

针对数组中的一个数(这个数叫做pivot),将这个数组划分成两个部分:左边的每个元素都比pivot小;右边的每个元素都比pivot大。然后,再分别在左右两个部分递归地进行这种划分的操作。

如此说比较笼统,在这个大方向上实际上是隐含着两个重要的地方:

1、如何确定pivot

2、如何划分

至于如何确定pivot这点先默认认为是取数组中的第一个元素,在下文将会针对取pivot,提出提高效率的方案。而至于如何划分,这点需要在这里马上说明。

在这里的划分,是基于两个元素的位置交换实现的。而需要互换的两个元素有这样的特点,就左边的元素的值比pivot的要大,而右边的元素的值比pivot要小。

代码实现+解释(解释使用英文,因为想进外企,努力训练英文中)

public class SortTest<E extends Comparable<E>> {

public ArrayList<E> quicksort(ArrayList<E> arraylist) {

ArrayList<E> ret = null;

if (arraylist == null || arraylist.size() == 0) {

throw new IllegalArgumentException();

}

subquicksort(0, arraylist.size() - 1, arraylist);

ret = arraylist;

return ret;

}

public void subquicksort(int begin, int end, ArrayList<E> arraylist) {

ArrayList<E> ret = null;

if (begin < end) {

// by default,use the first item of the array as the pivot

E pivotkey = arraylist.get(begin);

// i is the monitor of the current left-side item

int i = begin;

//j is the right-side monitor

//why set j as "end+1" not end?

//because in the coming snippet:

//while (j > begin && arraylist.get(--j).compareTo(pivotkey) >= 0)

//;

//If we do not do like that way,like,we use j++ instead,we will get

//the wrong index afterward.

int j = end + 1;

while (true) {

//We can look over the items that are smaller than pivot and 

//let the i come to item that is bigger than pivot.

while (i < end && arraylist.get(++i).compareTo(pivotkey) <= 0)

;

//It's just like the last sentence

while (j > begin && arraylist.get(--j).compareTo(pivotkey) >= 0)

;

if (i >= j) {// let the j be the position for the pivot

break;

} else {

swap(i, j, arraylist);

}

}

//the j th item still stores the value smaller than pivot. 

swap(begin, j, arraylist);

//recurse

subquicksort(begin, j - 1, arraylist);

subquicksort(j + 1, end, arraylist);

}

}

public void swap(int i, int j, ArrayList<E> arraylist) {

E temp;

temp = arraylist.get(j);

arraylist.set(j, arraylist.get(i));

arraylist.set(i, temp);

}

}

作者:Kaiwii 发表于2012-9-20 18:55:15 原文链接
阅读:0 评论:0 查看评论

相关 [快速排序 java] 推荐:

快速排序Java实现

- - CSDN博客推荐文章
针对数组中的一个数(这个数叫做pivot),将这个数组划分成两个部分:左边的每个元素都比pivot小;右边的每个元素都比pivot大. 然后,再分别在左右两个部分递归地进行这种划分的操作. 如此说比较笼统,在这个大方向上实际上是隐含着两个重要的地方:. 至于如何确定pivot这点先默认认为是取数组中的第一个元素,在下文将会针对取pivot,提出提高效率的方案.

Java中的锁(Locks in Java)

- - 并发编程网 - ifeve.com
原文链接 作者:Jakob Jenkov 译者:申章 校对:丁一. 锁像synchronized同步块一样,是一种线程同步机制,但比Java中的synchronized同步块更复杂. 因为锁(以及其它更高级的线程同步机制)是由synchronized同步块的方式实现的,所以我们还不能完全摆脱synchronized关键字( 译者注:这说的是Java 5之前的情况).

Java PaaS 对决

- 呆瓜 - IBM developerWorks 中国 : 文档库
本文为 Java 开发人员比较了三种主要的 Platform as a Service (PaaS) 产品:Google App Engine for Java、Amazon Elastic Beanstalk 和 CloudBees RUN@Cloud. 它分析了每种服务独特的技术方法、优点以及缺点,而且还讨论了常见的解决方法.

Java浮点数

- d0ngd0ng - 译言-电脑/网络/数码科技
Thomas Wang, 2000年3月. Java浮点数的定义大体上遵守了二进制浮点运算标准(即IEEE 754标准). IEEE 754标准提供了浮点数无穷,负无穷,负零和非数字(Not a number,简称NaN)的定义. 在Java开发方面,这些东西经常被多数程序员混淆. 在本文中,我们将讨论计算这些特殊的浮点数相关的结果.

Qt——转战Java?

- - 博客 - 伯乐在线
编者按:事实上,在跨平台开发方面,Qt仍是最好的工具之一,无可厚非,但Qt目前没有得到任何主流移动操作系统的正式支持. 诺基亚的未来计划,定位非常模糊,这也是令很多第三方开发者感到失望,因此将导致诺基亚屡遭失败的原因. Qt的主要开发者之一Mirko Boehm在博客上强烈讽刺Nokia裁了Qt部门的决定,称其为“绝望之举”,而非“策略变更”.

java 验证码

- - ITeye博客
// 创建字体,字体的大小应该根据图片的高度来定. // 随机产生160条干扰线,使图象中的认证码不易被其它程序探测到. // randomCode用于保存随机产生的验证码,以便用户登录后进行验证. // 随机产生codeCount数字的验证码. // 得到随机产生的验证码数字. // 产生随机的颜色分量来构造颜色值,这样输出的每位数字的颜色值都将不同.

Java异常

- - CSDN博客推荐文章
“好的程序设计语言能够帮助程序员写出好程序,但是无论哪种语言都避免不了程序员写出坏的程序.                                                                                                                          ----《Java编程思想》.

java面试题

- - Java - 编程语言 - ITeye博客
 抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面. 抽象并不打算了解全部问题,而只是选择其中的一部分,暂时不用部分细节. 抽象包括两个方面,一是过程抽象,二是数据抽象.  继承是一种联结类的层次模型,并且允许和鼓励类的重用,它提供了一种明确表述共性的方法. 对象的一个新类可以从现有的类中派生,这个过程称为类继承.

Java使用memcached

- - 互联网 - ITeye博客
首先到 http://danga.com/memcached下载memcached的windows版本和java客户端jar包,目前最新版本是memcached-1.2.1-win32.zip和java_memcached-release_1.6.zip,分别解压后即可. 然后是安装运行memcached服务器,我们将memcached-1.2.1-win32.zip解压后,进入其目录,然后运行如下命令:c:>;memcached.exe -d install
c:>memcached.exe -l 127.0.0.1 -m 32 -d start.

Java线程池

- - 企业架构 - ITeye博客
线程的使用在java中占有极其重要的地位,在jdk1.4极其之前的jdk版本中,关于线程池的使用是极其简陋的. 在jdk1.5之后这一情况有了很大的改观. Jdk1.5之后加入了java.util.concurrent包,这个包中主要介绍java中线程以及线程池的使用. 为我们在开发中处理线程的问题提供了非常大的帮助.