排序算法之快速排序

马谦马谦马谦 2018年3月3日20:53:14 发表评论
文章最后编辑于:2019-12-7 17:38:16

一、原理

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

具体的排序过程描述为:

  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:

排序算法之快速排序

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

排序算法之快速排序

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

排序算法之快速排序

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

排序算法之快速排序

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

排序算法之快速排序

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

复杂度分析:

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

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

二、代码实现

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

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

2.1 C++实现

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

2.2 python

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

本文共执行59次查询,耗时0.362秒!
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: