快速排序也是采用分治法，将问题化整归零来处理。
步骤为：
1. 从数列中调出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，排序规则就是将数列中比基准值大的放在基准的后面，将比基准值小的放在基准的前面，在这个分区退出之后，该基准就处于数列的中间位置（非绝对中间位置），这个称为分区操作；
3. 递归地把小于基准值元素的子数列和大于基准值元素的子序列排序。递归的终止条件就是数列的大小是零或一，也就是都已经被排序好了。
通俗点说就是，
1. 先从数列中取出一个数作为基准；
2. 分区过程，将比这个数大的数全部放到它的右边，小于或等于它的数全放到它的左边；
3. 对左右分区重复第 2 步，直到各分区只有一个数或没有数据。
具体流程参见下图（这里以数列的首元素作为基准）：
经过一轮分区，基准值 “4” 已经到了排序好的位置，然后将其左右两边的子数列再次进行分区比较
全部与基准值比较放置后，基准值便到了合理位置，如此递归，知道子序列中的元素为零或一，如上面的 57，7是基准值，位置放好后，其左子数列元素个数为一，右子数列元素个数为零。
从上面的操作图可以很好地理解快速排序的设计思想，就是留出一个空位，然后用数补上，就又留下一个空位，再补上，最后将基准值补上最后一个空位。
int Partition(int Array[], int left, int right)
{
int L = left, R = right;
int pivot = Array[L];
while (L < R)
{
while ((L < R) && (Array[R] > pivot))
--R;
if (L < R)
{
Array[L] = Array[R]; //补数的时候，要知道空位在哪
++L;
}
while ((L < R) && (Array[L] < pivot))
++L;
if (L < R)
{
Array[R] = Array[L];
--R;
}
}
Array[L] = pivot; //补上最后的空位
return L;
}
void QuickSort(int Array[], int left, int right)
{
if (left < right)
{
int pos = Partition(Array, left, right);
QuickSort(Array, left, pos - 1); //注意边界
QuickSort(Array, pos + 1, right);
}
}
针对上面的 partition() ，下面简化一下
int Partition(int Array[], int left, int right)
{
int pivot = Array[left];
while (left < right)
{
while (left < right && Array[right] > pivot) //两种情况跳出循环
--right;
Array[left] = Array[right];
while (left < right && Array[left] <= pivot) //
++left;
Array[right] = Array[left];
}
Array[left] = pivot;
return left;
}
复杂度分析：
1. 快排的时间复杂度取决于快排递归的深度，上面的分治可以用递归树来描述递归算法的执行情况
细心点就会发现上面这是一棵平衡二叉树（AVL 树，其每个节点的左子树和右子树的高度最多差 1 的二叉查找树），其高度一般都良好地维持在O(logN)，所以快速排序在时间复杂度上性能比较好。上面是AVL 树的前提是 Partition 每次都划分的很均匀（最优情况下）。前面说到快速排序的时间复杂度取决于快排递归的深度，递归树是一棵二叉查找树，其最大深度为 logN，即快速排序会递归 logN，每次对 N 个数进行一次处理，所以其时间复杂度为 O(NlogN)。
2. 空间复杂度，主要是递归造成的栈空间的使用，最好情况下，递归树的深度为 logN，其空间复杂度也就是O(logn)，最坏情况下，递归树严重不平衡，需要进行 N-1 递归调用，其空间复杂度为O(N)，平均情况下，空间复杂度为O(logN)。
3. 稳定性，从上可知，元素值得比较和交换是跳跃进行的，所以，快速排序是一种不稳定的排序算法。
一般情况下，快速排序比大部分排序算法都要快，尤其在Partition 很均与的情况下（递归树为AVL树）。