排序算法之快速排序

马谦马谦马谦 2018年3月3日20:53:14 发表评论
文章最后编辑于:2018-5-4 21:28:29

一、原理

选择排序使用了分治的原理,把排序序列进行切分然后分而治之。

对于每次排序,都是以随机的一个元素为标杆(一般都以排序区间的中间元素或者首元素作为标杆),比他大的元素都放到右边,比它小的都放到左边。然后对该元素左边和右边的元素再分别以相同的方法排序,直到所有的元素都是有序状态。

快速排序的时间复杂度为O(n*lg(n)),是一种不稳定的排序算法。

排序图解:

排序算法之快速排序

二、代码实现

快排的写法多样,这里C++和python写法不一样但大同小异。

1. C++

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

2. python

以区间首元素作为标杆:

本文共执行45次查询,耗时0.264秒!
马谦马谦马谦

发表评论

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