1.算法介绍

快速排序也是“交换”类的排序，它通过多次划分操作实现排序。以升序为例，其执行流程可以概括为：每一趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比枢轴小的移到枢轴前边，比枢轴大的移到枢轴后边；当本趟所有子序列都被枢轴以上述规则划分完毕后会得到新的一组更短的子序列，它们成为下一趟划分的初始序列集。

2.执行流程

进行第一趟快速排序，以第一个数49作为枢轴，整个过程是一个交替扫描和交换的过程。

1）使用j，从序列最右端开始向前扫描，直到遇到比枢轴49小的数27，j停在这里。

2）将27交换到序列前端i的位置。

3）使用i，变换扫描方向，从前向后扫描，直到遇到比枢轴49大的数65，i停在这里。

4）将65交换到序列后端j的位置。

5）使用j，变换扫描方向，从后向前扫描，直到遇到比枢轴49小的数13，j停在这里。

6）将13交换到i的位置。

7）使用i，变换扫描方向，从前向后扫描，直到遇到比枢轴49大的数97，i停在这里。

8）将97交换到j的位置。(www.daowen.com)

9）使用j，变换扫描方向，从后向前扫描，直到遇到比枢轴49小的数，当扫描到i与j相遇时，说明扫描过程结束了。

10）此时i等于j的这个位置就是枢轴49的最终位置，将49放入这个位置，第一趟快速排序结束。

可以看出第一趟划分后，将原来的序列以49为枢轴，划分为两部分，49左边的数都小于或等于它，右边的数都大于或等于它。接下来按照同样的方法对序列{27 38 13}和序列{76 97 65 49}分别进行排序。经过几趟这样的划分，最终会得到一个有序的序列。

注意：上边这个例子是第一趟划分，这一趟只有一个子序列即原始序列本身。当存在多个子序列时，把所有子序列都划分完毕称为一趟划分。对子序列的划分没有次序上的要求。

快速排序算法代码如下：

3.性能分析

（1）时间复杂度分析

快速排序最好情况下的时间复杂度为O（nlog₂n），待排序列越接近无序，本算法效率越高。最坏情况下的时间复杂度为O（n²），待排序列越接近有序，本算法效率越低。平均情况下时间复杂度为O（nlog₂n）。快速排序的排序趟数和初始序列有关。

说明：后边还会出现多个时间复杂度同为O（nlog₂n）的排序算法，但仅有本节的算法称为快速排序，原因是这些算法的基本操作执行次数的多项式最高次项为X*nlog2n（X为系数），快速排序的X最小。可见它在同级别的算法中是最好的，因此叫快速排序。

（2）空间复杂度分析

本算法的空间复杂度为O（log₂n）。快速排序是递归进行的，递归需要栈的辅助，因此它需要的辅助空间比前面几类排序算法大。