对于包含n个数的输入数组来说，快排是一种最坏情况下时间复杂度为O(n*n)的排序算法。虽然最坏时间复杂度很差，但是快排通常是实际排序中的首选，
以为他的平均性能非常好，它的期望时间复杂度为O(nlgn)，而且O(nlgn)中隐含的常数因子非常小。
快排分为两个部分的函数来实现：函数QUICKSORT(A,p,r)和函数PARTITION(A,p,r)
函数QUICKSORT(A,p,r)体现的是总的快排的功能，函数的伪代码如下：
QUICKSORT(A,p,r)（A表示的数组名，p是数组的下标，r是数组的上标，即就是对数组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)，此函数的实现体现的正好是快排算法的核心。算法的思想是：以数组的最后一个元素为标杆，每次进行比较和交换，每一轮过后，结果是使得小于等于此元素的所有数组元素被放置在数组的一端，剩下的大于此元素的所有元素被放置在数组的另一端，两端的分界线刚好是原数组的最后一个元素，完成调换过程之后，再对此元素进行调换，将其调换到数组的分界线所处的位置，此时，相当于此元素一遍的元素全都大于此元素，另一边的所有元素都小于此元素，即就实现了排序。
PARTITION(A,p,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;
快排的随机化版本：
在讨论快排的平均情况性能的时候，我们的前提假设是：输入数据的所有排列都是等概率的，但是在实际工程中，这种假设并不总是成立，因此我们可以通过在算法中引入随机性，来使得算法对所有的输入都能获得较好的期望性能。从上面的描述可以看到，每次分成两部分的标准是A[r]，即就是要进行排序的这一段数组A[p,r]的最后一个元素的值，很容易可以得到，如果每次分的两部分的长度越相近，最后得到的程序运行时间就越短。但实际工程中的A[r]往往呈现出一种有规律的迹象，因此，我们要对原来的程序稍加改动来实现随机化。
新增加一个函数：RANDOMIZED-PARTITION(A,p,r)
RANDOMIZED-PARTITION(A,p,r)函数的伪代码如下：
RANDOMIZED-PARTITION(A,p,r)：
i=RANDOM(p,r); //每次在A[p,r]之间选择一个数来与元素A[r]进行交换
exchange A[r] with A[i];
return PARTITION(A,p,r);
此函数的功能就是每次用产生的随机的值换掉原始的A[r]的值。
此时新的快排不再调用PARTITION，而是调用RANDOMIZED-PARTITION
RANDOMIZED-PARTITION(A,p,r):
If p<r
q=PARTITION(A,p,r);
RANDOMIZED-PARTITION(A,p,q-1);
RANDOMIZED-PARTITION(A,q+1,r);