快速排序算法思路分析和C++源代码(递归和非递归)

  快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试喜欢考这个。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

***********************************

分治法的基本思想:

  1.先从数列中取出一个数作为基准数。

  2.分区过程:将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

  3.再对左右区间重复 (不含基准数),直到各区间只有一个数。

***********************************

效率分析:

  快速排序的时间主要耗费在划分操作上,对长度为k的区间进行划分,共需k-1次关键字的比较。

  最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)

  在最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:O(nlgn)

  尽管快速排序的最坏时间为O(n*n),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快者,快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。

  快排空间复杂度:在通常情况下为O(log2n),需要使用深O(log2n)的栈实现递归,如果是最坏情况的话,很显然就要O(n)的空间了。

***********************************

应用场景:

  快排算法一般应用在排序中,但是分治法的思想应用广泛,比如在《剑指Offer》中, 题40:最小的k个数和题39:数组中出现次数超过一半的数字均用到了分治法的思想。

**********************************

C++实现代码:

https://github.com/wylloong/TinyPrograms/blob/master/Coding%20Interviews/QuickSortDemo.cpp (代码同步更新)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之打印1到最大的N位数(九度OJ1515)

题目描述: 给定一个数字N,打印从1到最大的N位数。 输入: 每个输入文件仅包含一组测试样例。 对于每个测试案例,输入一个数字N(1<=N<=5)。 输出: 对...

1807
来自专栏数据结构与算法

agc016C - +/- Rectangle(构造 智商题)

我的思路:直接按样例一的方法构造,若$h \times w$完全被$N \times M$包含显然无解

811
来自专栏ACM算法日常

前m大的数(堆)- HDU 1280

还记得Gardon给小希布置的那个作业么?(上次比赛的1005)其实小希已经找回了原来的那张数表,现在她想确认一下她的答案是否正确,但是整个的答案是很庞大的表,...

712
来自专栏决胜机器学习

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十一)——希尔排序 (原创内容,转载请注明来源,谢谢) 一、概述 希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面...

3257
来自专栏Petrichor的专栏

leetcode: 36. Valid Sudoku

1053
来自专栏杂七杂八

python中元素序列的频数

从一个随机序列中,找到出现次数最高的3个元素,它们出现次数是多少? 字典解决 from random import randint d = dict.fr...

3396
来自专栏移动开发面面观

快速排序法及优化

1274
来自专栏编程理解

排序算法(六):希尔排序

希尔排序是对插入排序的一种改进,也叫递减增量排序,算法过程中通过对增量值的递减调整,形成每一个增量值对应的一个或多个待排序分组,分别对分组执行插入排序,最后调整...

1301
来自专栏云霄雨霁

排序----希尔排序

1310
来自专栏五分钟学算法

十大经典排序算法动画,看我就够了!

Tip 为了演示更加清楚,本文中所有的动画都放慢了速度,因此GIF大小对比之前会有所增大,图片加载速度会变慢,如果你想获取所有的超清动画,在公众号回复 腾讯 可...

824

扫码关注云+社区