快速排序是冒泡排序的改进型，是基于分治的思想的排序类型。首先从待排序数组中取出第1个数作为基数，然后把数组中比此数小的全部移动到此数左侧，再把比此数大的移动到此数右侧，第1轮排序完毕；然后把整个数组在此基数位置上二分，左右子数组再按上述做法再次移动一轮算第2轮排序完成，以此类推，直至所有子数组皆成有序状态。

　　快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。

　　最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅比刻分前的无序区中记录个数减少一个，时间复杂度为O(n²)；在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数为O(nlog2n)。

　　尽管快速排序的最坏时间复杂度为O(n²)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。快速排序的时间复杂度（平均）是O(nlog2n)、空间复杂度是O(nlog2n)，为不稳定排序算法（采用分组）。

　　比如，待排序数组arr=[8,4,5,12,7,1,3,6,2]，用快速排序方法对这个数组做排序的图解分析如下图所示。

　　程序代码：

　　运行结果：

　　从算法中可知道，每次运行都会固定一个基准元素的位置，因此只要有一个列表收集分组（基准元素作为中间分组）就可以用循环实现算法。

　　程序代码：

　　运行结果：

　　练习题１：下面是一批学生的姓名、学号和数学成绩，请用两种快速排序法排序，使高分在前，低分在后；同分学号小的在前，学号大的在后。

姓名　　　学号　　　分数

李大伟　　２３　　　９０，

黄晨希　　１５　　　８８，

张丹丹　　１１　　　９０，

王丽丽　　２１　　　９５，

刘华旭　　１２　　　８８，

李小明　　　９　　　９４，

霍顺高　　　５　　　９７，

张飞鹏　　１０　　　８８，

李华峰　　　３　　　９９，

史大维　　　８　　　９０，

黄芬诗　　　２　　　９７。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社