快速排序算法思路分析和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 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

快速排序

今天介绍快速排序,这也是在实际中最常用的一种排序算法,速度快,效率高。就像名字一样,快速排序是最优秀的一种排序算法。 思想 快速排序采用的思想是分治思想。 快速...

17810
来自专栏有趣的Python

算法与数据结构(四)堆排序:优先队列实现

堆排序 排序次要的,接触新的数据结构;堆 堆和优先队列 Heap and Priority Queue 什么是优先队列? 普通队列:先进先出;后进后出 优先队...

3225
来自专栏琯琯博客

排序算法-快速排序

排序算法-快速排序 <?php /** * 快速排序. * * @param array $value 待排序数组 * @param array $...

3198
来自专栏小樱的经验随笔

【Java学习笔记之十一】Java中常用的8大排序算法详解总结

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

2806
来自专栏女程序员的日常

快慢指针

一、快慢指针说明   快慢是指移动步数的长短,也就是每次向前移动速度的快慢。如,指定快指针每次沿着链表向前移动2步,指定慢指针每次沿着链表向前移动1步。 二、快...

2541
来自专栏用户画像

6.2.3 分块查找

分块查找,又称为索引顺序查找,吸收了顺序查找和折半查找各自的优先,既有动态结构,又适于快速查找。

513
来自专栏一英里广度一英寸深度的学习

线性排序算法-堆排序 (2)

在学数据结构的时候,链表、堆栈、树三种数据结构印象最深刻。当时理解有误区,堆栈被当成一种结构,可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。

643
来自专栏云霄雨霁

排序----快速排序

1000
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-下

5、堆排序(HeapSort) 在接触“堆排序”前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了“完全二叉树”有一些重要的数学特性: ? 上图就是一...

1765
来自专栏向治洪

算法笔记之排序

最近在看《算法笔记》,如果单从算法来说,这本书真正做到了短小精悍,首先以排序入题,那么我们今天也来说说排序。 排序 将一堆杂乱无章的元素按照某种规则有序排列的过...

19610

扫描关注云+社区