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

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

相关文章

  • 粗略的物体碰撞预测及检测

      该博客实时更新于我的Github。

    waylon
  • 不使用额外空间交换2个数据的源代码

      最近做求职笔试题,遇到比较有意思的题目,题目或多或少涉及到《剑指Offer》的思路和知识点,如果不是刷书两遍,估计不会做出来,分享一下互相学习! *****...

    waylon
  • ArcGIS二次开发AO软件安装破解教程

          最近在做ArcGIS二次开发时,采用C#中的WPF技术,在调研中发现ArcGIS 10.3及以上版本支持WPF技术,但是关于ArcGIS10.3的破...

    waylon
  • 加权有向图----无环情况下的最短路径算法

    SuperHeroes
  • Leetcode 189. 旋转数组

    输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6]...

    zhipingChen
  • 《coredump问题原理探究》windows版5.2节数组

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

    血狼
  • HandlerMethodArgumentResolver(三):基于HttpMessageConverter消息转换器的参数处理器【享学Spring MVC】

    通过 前面两篇文章 的介绍,相信你对HandlerMethodArgumentResolver了解已经很深刻了。但是你或许和我一样还有一种感觉,似乎还缺点什么:...

    YourBatman
  • C#入门1.0 与J2ee对立的平台.net

    既然说要写一些c#语法了,那就必须得说一说.net平台了。先水一下。 ? ---- ? ---- ? ---- ? ---- ? ---- ? 更详细的东西...

    东风冷雪
  • org.springframework.context.ApplicationContextException: Unable to start web server; nested exceptio

    3.启动类上必须添加注解@EnableAutoConfiguration 或 @SpringBootApplication

    yuanyuan
  • OpenStack查看安全组详细规则

    院长技术

扫码关注云+社区

领取腾讯云代金券