排序----快速排序

上一篇:归并排序

  • 将长度为N的无重复数组排序,快速排序平均需要~2*NlgN次比较(以及1/6的交换)。
  • 快速排序最多需要N^2/2次比较,但随机打乱数组能预防这种情况。

归并排序和希尔排序一般都比快速排序慢,其原因就在它们还在内循环中移动数据;快速排序的另一个速度优势在于它的比较次数很少。

快速排序的特点:

  • 原地排序(只需要一个很小的辅助栈)
  • 将长度为N的数组排序所系时间和NlgN成正比。
  • 快排的内循环比大多数排序算法都要短小,这意味着无论在理论上还是实际中都要更快。
  • 归并排序和希尔排序一般都比快排慢,其原因就是它们还在内循环中移动数据。
  • 主要缺点是非常脆弱,实现时要非常小心才能避免低劣的性能。

快速排序的切分:

切分满足下面三个条件:

  • 对于某个j,a[j]已经排定
  • a[lo]到a[j-1]中的所有元素都不大于a[j]
  • a[j+1]到a[hi]中的所有元素都不小于a[j]
private static 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))	if(i==hi)	break;    //从左到右找到第一个大于切分元素的元素
			while(less(v,a[--j]))	if(j==lo)	break;    //从右至左找到第一个小于切分元素的元素
			if(i>=j)break; 
			exch(a,i,j);    //交换找到的两个元素
		}
		exch(a,lo,j);    //最后将切分元素交换到正确的位置
		return j;
}

快速排序特点:

快速排序的实现需要注意几个细节:

  • 原地切分。避免使用辅助数组,减小数组复制之间的开销。
  • 别越界。如果切分元素是数组中最大或最小的元素,要特别小心别让扫描指针跑出数组边界。
  • 保持随机性。
  • 处理切分元素值有重复的情况。糟糕的处理可能会使算法运行时间变为平方级别。
  • 终止递归。
public static void sort(Comparable[] a){
	StdRandom.shuffle(a);
	sort(a,0,a.length-1);
}
private static 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);    //递归右半部分排序
}

算法改进

  • 切换到插入排序
  • 三取样切分
  • 熵最优排序

含有大量重复元素的数组,快速排序还有巨大的改进空间。一个经典的算法是Dijkstra的“三向切分的快速排序”。它从左到右遍历数组,设有三个指针lt,i,gt。使a[lo...lt-1]中的元素都小于v,a[gt+1...hi]中的元素都大于v,a[lt...i-1]元素都等于v,a[i...gt]元素未定。

  1. a[i]小于v, 将a[lt]和a[i]交换,将lt和i加一;
  2. a[i]大于v, 将a[gt]和a[i]交换,将gt减一;
  3. a[i]等于v, 将i加一。

对于包含大量相同元素的数组,它将排序时间线性对数级别降到了线性级别。

private static void sort(Comparable[] a,int lo,int hi){
	if(hi<=lo)return;
	int lt=lo,i=lo+1,gt=hi;
	Comparable v = a[lo];
	while(i<=gt){
		int cmp = a[i].compareTo(v);
		if(cmp<0)	exch(a,lt++,i++);    //小于,放左边
		else if(cmp>0)	exch(a,i,gt--);    //大于,放右边
		else i++;    //等于,放中间
	}
    //只递归左右小于和大于V的部分,中间等于V的部分不需要递归
	sort(a,lo,lt-1);
	sort(a,gt+1,hi);
}

算法改进:

  • 哨兵:可以通过设置哨兵来去掉while中的边界检查。由于切分元素本身就是一个哨兵,左侧边界检查是多余的;可以将数组中的最大元素放置在a[length-1]中来去掉右部检查。注意:在处理内部数组中,右子数组最左侧元素可以成为左子数组的哨兵。
  • 非递归的快速排序:可以使用一个循环来将弹出栈的切分并将结果子数组重新压栈来实现非递归快排。注意:先将较大子数组压栈可以保证栈中最多只会有lgN个元素。
  • 快速三向切分:可以讲相等的元素放在数组两边而不是中间实现快速三向切分。

下一篇:堆排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

检查Python对象

编程环境中的对象很象现实世界中的对象。实际的对象有一定的形状、大小、重量和其它特征。实际的对象还能够对其环境进行响应、与其它对象交互或执行任务。计算机中的对象试...

19610
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java案例】九九乘法表

案例描述 输出九九乘法口诀表,如图1.4所示。 ? 图1.4 九九乘法口诀表 案例分析 观察九九乘法口诀表,可以得出图表的规律:总共有9行,第几行就有几个表达...

3879
来自专栏Golang语言社区

go语言的匿名函数

1-声明一个匿名函数 func(参数列表) 返回值列表 { 函数体… } 2-匿名函数的调用

852
来自专栏Phoenix的Android之旅

Java的克隆

说到克隆,本质都是使用一个已经实例化完成的对象的副本。 对于基本类型比较简单。比方说我们想复制一个变量,

972
来自专栏互联网杂技

28个JavaScript 编程黑科技:还有这种操作!

从来不需要声明一个变量的值是undefined,因为JavaScript会自动把一个未赋值的变量置为undefined。所有如果你在代码里这么写,会被鄙视的

1243
来自专栏猿人谷

浅谈C/C++中的指针和数组(一)

                                                       浅谈C/C++中的指针和数组(一)       指...

2185
来自专栏维C果糖

Guava 指南 之「使用和避免 null」

使用和避免null “null,糟糕透啦!” —— Doug Lea. “我称null为百亿美金的错误!” —— C. A. R. Hoare. 轻...

2117
来自专栏Java Web

Java 面试知识点解析(一)——基础知识篇

在遨游了一番 Java Web 的世界之后,发现了自己的一些缺失,所以就着一篇深度好文:知名互联网公司校招 Java 开发岗面试知识点解析 ,来好好的对 Jav...

4825
来自专栏喵了个咪的博客空间

zephir-(5)类型

#zephir-类型# ? ##前言## 先在这里感谢各位zephir开源技术提供者 Zephir既可以使用动态类型也可以使用静态类型,这是zephir独特的一...

3709
来自专栏GreenLeaves

Javascript深拷贝

var oOriginal = { memNum: 1, // number ...

2016

扫码关注云+社区

领取腾讯云代金券