排序算法六:快速排序

马谦马谦马谦 数据结构和算法评论723字数 1102阅读 3 分 40 秒阅读模式

一、原理

选择排序的原理是分治,把排序序列切分成若干个小组后分别排序。每次排序都以随机的一个元素作为哨兵 (一般都以排序区间的中间元素或者首元素作为哨兵),比他大的元素都放到右边,比它小的都放到左边。然后分别对该元素左边和右边的元素再法排序,直到所有的元素都是有序状态。

具体的排序过程描述为:

  1. 选取一个哨兵元素 temp,设置两个指针 low 和 high 分别从数组的两端开始遍历。
  2. high 指针从右到左遍历,当遇到 A[high] < temp 的时候,设置 A[left] 的值为 A[high] 。
  3. low 指针从左到右遍历,当遇到 A[high] > temp 的时候,设置 A[high] 的值为 A[left] 。
  4. 重复执行 2 、 3 步,直到 low 和 high 相遇,设置 low 元素的值为 temp 。此时 low 左边的元素都小于 temp,low 右边的元素都大于 temp 。再分别对左右子区间的元素分别排序。

图例:

以数组 [54, 15, 34, 82, 15, 46, 85, 43] 为例,初始状态时设置 low 指针指向第一个元素,high 指针指向最后一个元素,temp 为第一个元素的值 54:

排序算法六:快速排序-图片1

遍历 high 指针,从右到左找到第一个小于 54 的元素 43,赋值给 low:

排序算法六:快速排序-图片2

遍历 low 指针,从左到右找到第一个大于 54 的元素 82,赋值给 high:

排序算法六:快速排序-图片3

遍历 high 指针,从右到左找到一个小于 54 的元素 46,赋值给 low:

排序算法六:快速排序-图片4

遍历 low 指针,继续寻找第一个大于 54 的元素。但是直到遇见 high 指针,都没有找到再比 54 大的元素,把 temp 值赋值给 low:

排序算法六:快速排序-图片5

此时第一轮排序完成,54 左边的元素都比它小,右边的元素都比它大。因此按照这个操作,继续对左边和右边的区间再执行相同的操作,多次排序即可完成整个数组的排序。

复杂度分析:

最坏的情况下,数组无序,快速排序和冒泡排序差不多。

  • 时间复杂度:最坏情况下,时间复杂度为 O(n2);最好的情况和平均情况下算法复杂度为 O(nlog⁡(n))​。
  • 空间复杂度:最坏情况下,空间复杂度为 O(n);平均情况下空间复杂度为 O(log⁡(n)) 。

二、代码实现

快排的写法多样,以下实现了 C++和 Python 两种语言的快速排序算法实现。

其中 C++选取的哨兵是数组第一个元素,python 选取的哨兵是数组中间元素。

2.1 C++实现

以区间中点作为排序标杆:

2.2 python

以区间中点元素作为标杆:

2.3 golang 实现快速排序

2020-02-29 刷 leetcode 添加,使用数组中间元素作为哨兵:

 

  最后更新:2020-3-20
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2018 年 3 月 3 日 20:53:14
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/quick-sort.html
排序算法四:梳排序 数据结构和算法

排序算法四:梳排序

一、梳排序简介 梳排序是冒泡排序的一种优化方案,主要是为了解决冒泡排序中的尾部小数值问题。它主要的思想是通过比较元素和固定步长位置上的数据,先进行部分优化,然后逐步减少步长,以此来对数据进行预处理。 ...
排序算法五:堆排序 数据结构和算法

排序算法五:堆排序

一、堆排序原理 通过最大堆的性质可以知道:一个堆中最大的元素总是在堆顶的,即数组下标 0 的位置。基于这一点,我们可以每次都把堆中的最大值提取出来,放到当前数组的后面。然后重新构建最大堆,重复这个过程,以...
排序算法七:计数排序 数据结构和算法

排序算法七:计数排序

一、计数排序 其基本思想为:假设 n 个输入的元素中的每一个都是在 0 到 k 之间的一个整数,对于每一个输入元素 x,确定小于 x 的元素个数,直接把 x 放在它输出的数组中的位置上。例如有 17 个元素小于 x,则 x 就应该在...
排序算法三:冒泡排序 数据结构和算法

排序算法三:冒泡排序

一、原理 冒泡排序的原理很简单, 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序 (如从大到小、首字母从从 Z 到 A) 错误就把他们交换过来。 冒泡排序是一种稳定的排序算法。 冒泡排序不管在什...
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证