快速排序可能是应用最广泛的排序算法了。流行的原因是因为它实现简单、适用于各种不同的输入数据且在一般的应用中比其他算法都要快得多。快速排序属于原地排序,不需要额外的空间(相对于归并排序)。快速排序算法的时间复杂度为NlogN。
快速排序和归并排序类似,也是分治思想是应用。归并排序每次将数组一分为二,将两边都排序之后再合并。快速排序算法是每次将数组进行切分,保证切分点在相对于两边的子数组是有序的。左边的子数组都不大于切分点,右边的字数组都不小于切分点。
public class QuickSort extends AbstractSort implements Sort {
@Override
public void sort(Comparable[] a) {
sort(a,0,a.length - 1);
}
public void sort(Comparable[] a,int lo,int hi){
if(hi<=lo) return;//递归结束条件
int j = partition(a,lo,hi);
//递归对子数组进行排序
sort(a,lo,j-1);
sort(a,j+1,hi);
}
/**
* 切分
* 使a[lo]左边元素不大于本身,右边元素不小于本身
*/
private int partition(Comparable[] a, int lo, int hi) {
int i = lo,j = hi + 1;
Comparable v = a[lo];
while(true){
while(less(a[++i],v)){//从左往右直到遇到一个比v大的元素
if(i==hi) break;
}
while(less(v,a[--j])){//从右往左直到遇到一个比v小的元素
if(j==lo) break;
}
if(i>=j){
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
public static void main(String[] args) {
QuickSort sort = new QuickSort();
Integer[] data = RandomFactory.randomInt(3000000, 40000);
//sort.show(data);
long t = System.currentTimeMillis();
sort.sort(data);
t = System.currentTimeMillis() - t;
//sort.show(data);
System.out.println("quick sort");
System.out.println("is sorted:"+sort.isSorted(data));
System.out.println("time consumed:" + t);
}
}
运行结果比归并算法还稍快一点:
quick sort
is sorted:true
time consumed:1373
从排序算法代码中可以看出,算法中的切分操作发生在下一层递归之前。而归并算法的合并操作是在下一层递归之后进行的。这一点上看,快速排序有一点自上而下的味道,归并算法更类似于撒网搜网的感觉。
分享到:
相关推荐
C++排序算法之快速排序源码
C++排序算法之快速排序
数据结构排序算法之快速排序,可以再 vc6.0平台上直接运行,按照提示要求操作即可,希望对大家有所帮组……
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
1. 算法思想 选取一个基准值,将待排序数据分为左(小于基准值)右(大于基准值)两个区间,然后对两个分区的数据进行同样的循环操作,最后便可得到一组有序数据。...因此快速排序的平均时间复杂度为$O(n^
快速排序算法的基本思想是:随机选取数组中的一个值,将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直到...
舞动的排序算法 快速排序 通过动画演示快速排序,很好的学习,课程资源。
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
快速排序算法C语言实现,快排序算法QuickSort.cpp
用分治算法的思想,加上递归 实现快速排序
c语言版本的数据结构的快速排序算法,适用于新手学习
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
一个简单的算法效率对比,实验证明,快速排序的效率比冒泡的效率高出很多啊!
自己编写的基于java的快速排序和归并算法
详细解释了快速排序的java实现.里面有代码,还有注释说明