快速排序是运用了分治思想的排序方式，具有O(NlogN)的平均时间复杂度，极端情况下时间复杂度为O(N^2)，跟冒泡排序一样，但是快排的实际效率远比最坏情况好很多。它的关键部分是一轮划分（由Partition()函数完成），每一轮划分会导致序列中的元素分成两部分，一部分比参照数小，一部分比参照数大。函数QSort()通过不断调用Partition()完成给定序列的排序，当排序序列细化为1个元素时，排序也就完成了，因为单个元素是有序的。
算法描述如下：

上面的Partition()存在很有必要优化的地方
我们先来看几个例子：
如果执行Partition()前的序列是:
10 5 6 3 2 7
用第一个元素做参照（上面说的t），我们发现后面所有的元素都小于t，因此i后一直向后找，直到找到最后一个元素；而j一次就找到了<= t 的元素，也就是最后一个元素。这样，while(1)结束了，Partition()执行之后，原序列变成：
5 6 3 2 7 10
如果执行Partition()前的序列是:
10 14 15 16 20
用第一个元素做参照（上面说的t），我们发现后面所有的元素都大于t，因此i一次就找到了 >= t的元素；而j一直向前找，直到找到第一个元素；这样，while(1)结束了,Partition()执行之后，原序列不变，仍然是：
10 14 15 16 20
上面这两种情况都是我们不愿看到的，因为它导致Partition()执行后，两边的元素很不平均，极端情况下（比如，原序列是已排好序的），快排的时间复杂度是O(N^2)，跟冒泡排序一样。为了避免这种情况出现，我们可以采用随机化的策略，即不老是选择第一个元素做参照，为达到这一目的，可以提前将后面的任意一个元素与第一个元素交换。
优化后的算法为：


接下来我们在快速排序中划分函数Partition()的基础上讲解一下线性时间选择问题。所谓线性时间就是在平均O(N)的时间内找出无序序列中第k大的元素。先排序再找出该元素是比较容易想到的方法，但排序所花的时间很可能超过O(N)（比如，快排、堆排的时间复杂度都是O(NlogN)，选择排序、插入排序以及冒泡排序时间复杂度是O(N^2)）。
其实结合Partition()函数完成的一次划分我们很容易想到，选择第k大的元素不一定要排序原序列，因为经过一次划分，原序列以参照数t为基准被分成了两部分，我们要找的第k大的数要么就是t，要么在t左边，要么在t右边，因此每次迭代我们只需要考虑原序列接近1/2的数字就行了。显然，Select()函数的效率跟Partition()的好坏有直接关系，最坏情况下，Select()函数的时间复杂度仍为O(N^2)。
算法描述如下：
上面两种描述略有不同，前面是我写的，后面一个是书上的。这两种算法都忽略了一个问题，那就是没有考虑非法情况，即要选择的数超出了原有序列，比如原序列只有n个数，而却让找出第n+1大的数。