快速排序是最常用的一种排序算法，包括C的qsort，C++和Java的sort，都采用了快排（C++和Java的sort经过了优化，还混合了其他排序算法）。
快排最坏情况 푂(푛2) ，但平均效率 푂(푛lg푛) ，而且这个 푂(푛lg푛) 记号中隐含的常数因子很小，快排可以说是最快的排序算法，它还是就地排序。
快速排序是基于分治策略的。对一个子数组A[p…r]快速排序的分治过程的三个步骤为：
1、分解
数组A[p…r]被划分成两个（可能空）子数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]中的每个元素都小于等于A[q]，且小于等于A[q+1…r]中的元素。下标q也在这个划分过程中进行计算。
2、解决
通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]排序。
3、合并
因为两个子数组就是原地排序的，将它们的合并不需要操作：整个数组A[p…r]已排序。
快速排序伪代码
QuickSort(A, p, r)
if p < r
q=Partition(A, p, r)
QuickSort(A, p, q-1)
QuickSort(A, q+1, r)
Partition(A, p, r)
x = A[r]
i = p-1
for j = p to r-1
if A[j]<=x
i=i+1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
Return i+1
我们给出PARTITION代码中第3行至第8行迭代的循环不变式：
每一轮迭代的开始，对于任何数组下标k，有：
如果 푝≤푘≤푖 ，则 퐴[푘]≤푥 。
如果 푖+1≤푘≤푗−1 ，则 퐴[푘]>푥 。
如果 푘=푟 ，则 퐴[푘]=푥 。
下面便是证明这个循环不变式：
初始化：循环开始前，有 푖=푝−1 和 푗=푝 。不存在k使得 푝≤푘≤푖 或 푖+1≤푘≤푗−1 ，所以1)和2)成立。程序第一行代码里的 푥=퐴[푟] 使得条件3)成立。
保持：根据第4行代码的比较结果，有两种情况：
(1) 퐴[푗]>푥 时，仅做一个j增加1的操作，所以条件1)和3)不受影响。j增加后 퐴[푗−1]>푥 ，又因为 퐴[1…푗−2] 在迭代前同样都大于x，所以条件2)成立；
(2) 퐴[푗]≤푥 时，i增加1，因为 퐴[푝…푖−1] 都小于等于x，而 퐴[푖] 也小于等于x，所以 퐴[푝…푖] 都小于等于x，条件1)成立。j也增加1，与情况1一样，条件2)和条件3)也都成立。 终止：循环结束时j=r，根据条件1) 퐴[푝…푖] 都会小于等于x，而 퐴[푖+1…푟−1] 都大于x。
#快速排序代码
def quickSort(data, start, end):
i = start
j = end
#i与j重合时，一次排序结束
if i >= j:
return
#设置最左边的数为基准值
flag = data[start]
while i < j:
while i= flag:
j -= 1
#找到右边第一个小于基准的数，赋值给左边i。此时左边i被记录在flag中
data[i] = data[j]
while i 
