文档章节

快排的最差情况以及快排平均复杂度的计算

Hosee
 Hosee
发布于 2018/03/20 20:18
字数 627
阅读 1.6W
收藏 3

最近突然讨论了这两个问题,有点忘记了,记录了一下网上的比较好的说法,参见Reference

快排的相关知识请参考排序总结

快排的最差情况以及如何避免

首先,快排的最差情况什么时候发生?

1. 已排序

2. 数值全部相等(1的特殊情况)

快排最好的情况是,每次正好中分,复杂度为O(nlogn)。最差情况,复杂度为O(n^2),退化成冒泡排序

为了尽量避免最差情况的发生,就要尽量使每次选择的pivot为中位数。

一般常用的方法是,对每一个数列都取一次中位数(O(n)),这样总体的快排时间复杂度仍为O(nlogn)。

更为简化的方法是,取头、中、尾的中位数(O(1))作为pivot

另一个问题:

如果有元素等于pivot,是换还是不换呢?

1. 如果换,那当遇到全是一样的数,每一次都要交换,但是有一个好处是,pivot会移动到中间的地方,正好中分,符合快排最好的情况,复杂度为O(nlogn)

2. 如果不换,同样是全是一样的数,的确不用交换,i指针一直移到最后遇到j指针,pivot被移动到最后一位。分治时,右边没有元素,左边n-1个元素,重复一下。符合快排最坏情况,复杂度为O(n^2)

综上,还是换吧。

对于最差情况的第2种数据,即数值全部相等,或者存在大量相等的数值时,Java的sort方法中使用三向切分快排来优化这个问题,详情请看Java中的排序

快排平时时间复杂度计算

计算方式来源于算法导论

主定理: T [n] = aT[n/b] + f (n)

其中 a >= 1 and b > 1 是常量 并且 f (n) 是一个渐近正函数, 为了使用这个主定理,您需要考虑下列三种情况:

快速排序的每一次划分把一个 问题分解成两个子问题,其中的关系可以用下式表示:

T[n] = 2T[n/2] + O(n) 其中O(n)为PARTITION()的时间复杂度,对比主定理,

 T [n] = aT[n/b] + f (n)

我们的快速排序中:a = 2, b = 2, f(n) = O(n)

Reference:

1. https://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/

2.《算法导论》

© 著作权归作者所有

Hosee
粉丝 621
博文 135
码字总数 209956
作品 0
杭州
程序员
私信 提问
加载中

评论(1)

程序猿小蔡
程序猿小蔡
排序总结(不断更新)

排序法 最好时间分析 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n)(改进的冒泡排序) O(n2) O(n2) 稳定 O(1) 快速排序 O(nlog2n) O(n2) O(nlog2n) 不稳定 O(log2n)~O(n) ...

Hosee
2015/10/23
2.7K
0
ZOJ 3499. Median

    地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4322     题意:寻找中位数。对于一个(浮点数)数组,如果含有奇数个元素,“中位数”就是排序后位于数组中...

hoodlum1980
2012/06/13
0
0
排序算法C语言实现——冒泡、快排、堆排对比

对冒泡、快排、堆排这3个算法做了验证,结果分析如下: 一、结果分析 时间消耗:快排 < 堆排 < 冒泡。 空间消耗:冒泡O(1) = 堆排O(1) < 快排O(logn)~O(n) 。 应用推荐:   1、速度最快、且...

Jo_ZSM
2018/10/14
0
0
JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

1. 前言 算法为王。 想学好前端,先练好内功,只有内功深厚者,前端之路才会走得更远。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便...

天明夜尽
2019/07/24
0
0
排序算法之快速排序

快速排序是一种基于分治技术的重要排序算法,顺便提一下什么是分治: 分治法是按照以下方案工作: 1.将一个问题划分为同一类型的若干子问题,子问题规模相同或相近 2.对这些子问题进行求解(...

卫莨
2017/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

006. 线程安全之 JAVA 锁相关

1. JAVA中锁的概念 自旋锁: 是指当一个线程在获取锁的时候,如果锁已经被其他线程获取,那么该线程将循环等待,然后不断地判断锁是否能够被成功获取,直到获取到锁才会退出循环。 乐观锁: 假...

紫穹
23分钟前
50
0
如何确定Python变量的类型? - How to determine a Python variable's type?

问题: How do I see the type of a variable whether it is unsigned 32 bit, signed 16 bit, etc.? 如何查看变量的类型,无论是无符号32位,带符号16位等等? How do I view it? 我该如何看...

javail
今天
109
0
略谈分布式系统中的容器设计模式

本文作者:zytan_cocoa 略谈分布式系统中的容器设计模式 谭中意 2020/3/5 前言:云原生(Cloud Native)不仅仅是趋势,更是现在进行时,它是构建现代的,可弹性伸缩的,快速迭代的计算网络服...

百度开发者中心
03/11
128
0
a small thing that made me a little bit depressed

It was just two hours ago,specificly speaking It was 11:48 almost coming close to midneight. I was pratising singing songs in my renting room which is a sharing apartment . I re......

lost_myself
今天
97
0
OSChina 周日乱弹 —— 这中间几个月的地震、核爆、外星人、高达... 去哪了

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《Elizabeth》- Ashram 手机党少年们想听歌,请使劲儿戳(这里) @巴拉迪维 :#共...

小小编辑
今天
218
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部