/** 快速排序方法 */
public static void quickSort(int[] a, int lo0, int hi0) {
int lo = lo0;
int hi = hi0;
if (lo >= hi)
return;
// 确定指针方向的逻辑变量
boolean transfer = true;
while (lo != hi) {
if (a[lo] > a[hi]) {
// 交换数字
int temp = a[lo];
a[lo] = a[hi];
a[hi] = temp;
// 决定下标移动,还是上标移动
transfer = (transfer == true) ? false : true;
}
// 将指针向前或者向后移动
if (transfer)
hi--;
else
lo++;
// 显示每一次指针移动的数组数字的变化
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + ",");
}
System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
System.out.println("");
}
// 将数组分开两半,确定每个数字的正确位置
lo--;
hi++;
System.out.println("一趟。。区间:["+lo0+","+lo+"]["+hi+","+hi0+"]");
quickSort(a, lo0, lo);
quickSort(a, hi, hi0);
}
网上关于快速排序算法一大推,但仔细看了确发现都不是那么一回事,或许是我没找到对的吧!
还好在博客园找到了一篇http://www.cnblogs.com/yanzi629/archive/2010/11/20/1882863.html#commentform
对于快速排序我个人的理解是首先找出一个参照点设为p,排在p左边的都比p要小,右边的都比p要大,然后参照上面的方法把左右两边的数再一次进行排列一直到不能排了。
这是一种分治算法+递归的,容易理解,速度也很快,但是直观的用算法去描述没在网上找到好的描述算法,不过找到了一个基于此思想的更耳目一新的方法,该方法就是上面的代码,不过它是会设置参照点,而是基于机会相等的方法来缩小区间,这样减少了每个数字和其他数字比较的次数,代码中的指针transfer指示头索引和尾索引谁有机会向中间移动,当然这个机会是相等的,不相等要比相等理论上耗时。个人认为这个方法比设置基准点的描述算法好一些。
===============================================================================
2011-10-09 下午 编辑
java.util.Arrays.sort 的源码中对基本数据类型的排序实现是基于快排的
if (len < 7) {
for (int i=off; i<len+off; i++)
for (int j=i; j>off && x[j-1]>x[j]; j--)
swap(x, j, j-1);
return;
}
因为当数据量小的情况下快排就没有必要了,递归太浪费资源,一个递归就要入栈出栈,即便该方法什么也不做很浪费资源的,所以排序的数据小于7就用冒泡。
这里有个技巧,内部那个for循环是j--,也就是从高到低的循环,之所以这样写是因为如果你前面都进行了swap那么只用将条件x[j-1]>x[j]写到for的条件里面判断即可。
/**
* Returns the index of the median of the three indexed integers.
*/
private static int med3(int x[], int a, int b, int c) {
return (x[a] < x[b] ?
(x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
(x[b] > x[c] ? b : x[a] > x[c] ? c : a));
}
这个方法目的是寻找a,b,c的中间的那个数,a,b,c可以看成是数组的头、中间、尾三个地方。
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。
于是就产生了几种变种,分别是:随机化快速排序、平衡快排、外部快排、三路基数快排。
jdk的源码选择的是平衡快排。
平衡快排:每次尽可能地选择一个能够代表中值的元素作为关键数据,然后遵循普通快排的原则进行比较、替换和递归。通常来说,选择这个数据的方法是取开头、结尾、中间3个数据,通过比较选出其中的中值。取这3个值的好处是在实际问题(例如信息学竞赛……)中,出现近似顺序数据或逆序数据的概率较大,此时中间数据必然成为中值,而也是事实上的近似中值。万一遇到正好中间大两边小(或反之)的数据,取的值都接近最值,那么由于至少能将两部分分开,实际效率也会有2倍左右的增加,而且利于将数据略微打乱,破坏退化的结构。
分享到:
相关推荐
一个非常简单的快速排序算法!!!站长你好,我现在大四,需要下载一个tsplib的数据来跑蚁群算法的实验,由与查重的原因暂时不能把程序上传上来,可以先给我过吗,等答辩完我再上传程序,谢谢~
本程序实现各种排序算法并分析与比较 直接插入排序, SHELL排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序
C++实现快读排序,代码清晰友好,简单易懂
六种排序算法的比较 冒泡排序,快速排序,堆排序, 直接插入排序,简单选择排序, 希尔排序
用python写的简单的快排算法,对了解快排有点帮助
采用java语言实现的排序排序,通俗易懂。
快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。
用模板类实现的一个简易的c++程序,实现了快速排序。
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
数据结构--快速排序C++源代码,自己编写调试,代码简单易懂,不长
1、常见排序算法实现(1-6选择几个算法练习) ... (4)实现快速排序算法。 (5)实现堆排序算法。 (6)合并排序算法。 2) 实现提示: 数据输入后,每选择一种算法,把数据拷贝后再排序,保证原始数据不破坏.
vb.net 语言 开发的简单快速排序,里面附带工程文件,打开便可以运行,附带截图!用Visual Studio 2010 以上版本打开
冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
直接插入排序,折半插入排序,起泡排序 ,快速排序,简单选择排序,堆排序 ,基数排序 七种排序方法的实现和速度对比