快速排序：与归并排序一样，快速排序也使用了分治思想。
三步：
分解：数组A[p...r]被划分为两个（可能为空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中计算下标q也是划分过程的一部分。
解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序。
合并：因为子数组都是原址排序的，所以不需要合并操作：数组A[q+1..r]进行排序。
伪代码：
QUICKSORT(A,p,r)
if p<r
q = PARTITION(A,p,r) //这里的q就为分割数，将输入数组分为两部分。
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)
为了排序数组A的全部元素，初始调用的是QUICKSORT(A,1,A.length)。
数组的划分：
算法的关键部分时PARTITION过程，它实现了对子数组A[p..r]的原址重排。
PARTITION(A,p,r)
x = A[r] //这里取出此输入序列的末尾元素，作为分割元素。
i = p-1
for j = p to r-1
if A[j] <= x //如果A[j]小于等于被选出的数x，执行下面交换操作。如果大于则不做任何操作
i = i+1
exchenge A[i] with A[j] //此交换操作的目的是：将小于x的元素放到此子数列的前面部分。假设第二个元素大于x，第三个元素小于x，那么需要交换
exchange A[i+1] with A[r]
return i+1
上图d到e步对应伪代码中：exchenge A[i] with A[j]
快速排序的性能：
快速排序的运行时间依赖于划分是否平衡，而平衡与否又依赖于用于划分的元素。如果划分是平衡的（即按比例划分，无论是什么比例），那么快速排序的算法性能与归并排序一样。如果划分是不平衡的，那么快速排序的性能就接近于插入排序了。
最坏情况划分：
当划分产生的两个子问题分别包含了n-1个元素和0个元素时，快速排序的最坏情况发生了。不妨假设算法的每一次递归调用中都出现了这种不平衡划分。划分操作的时间复杂度是0(n)。对于一个大小为0的数组进行递归调用会直接返回，因此T(0)=0(1)，于是算法运行时间的递归式可以表示为：
T(n)=T(n-1)+T(0)+0(n)=T(n-1)+0(n)
从直观上来看，每一层递归式累加，得到一个算数级数，其结果为0(n^2)。 因此最坏情况下的算法时间复杂度是 0(n^2)。与插入排序一样。此外当输入数组已经完全有序时，快速排序的时间复杂度仍然为0(n^2)，而插入排序则是O(n)。
最好情况划分：即按比例划分，其时间复杂度为O(nlgn)。
原文：http://www.cnblogs.com/zxCoding/p/5249100.html