快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序（比如用前述的冒泡、选择、插入排序均可），否则分三步处理：
注意：下面的记号L[p..r]代表线性表L从位置p到位置r的元素的集合，但是L并不一定要用数组来实现，可以是用任何一种实现方法（比如说链表），这里L[p..r]只是一种记号。
procedure Quick_Sort(p,r:position;var L:List);
const
e=12;
var
q:position;
begin
1 if r-p<=e then Insertion_Sort(L,p,r)
//若L[p..r]足够小则直接对L[p..r]进行插入排序
else begin
2 q:=partition(p,r,L);
//将L[p..r]分解为L[p..q]和L[q+1..r]两部分
3 Quick_Sort(p,q,L); //递归排序L[p..q]
4 Quick_Sort(q+1,r,L);//递归排序L[q+1..r]
end;
end;
对线性表L[1..n]进行排序，只要调用Quick_Sort(1,n,L)就可以了。算法首先判断L[p..r]是否足够小，若足够小则直接对L[p..r]进行排序，Sort可以是任何一种简单的排序法，一般用插入排序。这是因为，对于较小的表，快速排序中划分和递归的开销使得该算法的效率还不如其它的直接排序法好。至于规模多小才算足够小，并没有一定的标准，因为这跟生成的代码和执行代码的计算机有关，可以采取试验的方法确定这个规模阈值。经验表明，在大多数计算机上，取这个阈值为12较好，也就是说，当r-p<=e=12即L[p..r]的规模不大于12时，直接采用插入排序法对L[p..r]进行排序。当然，比较方便的方法是取该阈值为1，当待排序的表只有一个元素时，根本不用排序(其实还剩两个元素时就已经在Partition函数中排好序了)，只要把第1行的if语句改为if p=r then exit else ...。这就是通常教科书上看到的快速排序的形式。
注意：算法Quick_Sort中变量q的值一定不能等于r，否则该过程会无限递归下去，永远不能结束。因此下面在partition函数里加了限制条件，避免q=r情况的出现。
算法Quick_Sort中调用了一个函数partition，该函数主要实现以下两个功能：
在L[p..r]中选择一个支点元素pivot;
对L[p..r]中的元素进行整理，使得L[p..q]分为两部分L[p..q]和L[q+1..r]，并且L[p..q]中的每一个元素的值不大于pivot，L[q+1..r]中的每一个元素的值不小于pivot，但是L[p..q]和L[q+1..r]中的元素并不要求排好序。
快速排序法改进性能的关键就在于上述的第二个功能，因为该功能并不要求L[p..q]和L[q+1..r]中的元素排好序。
函数partition可以实现如下。以下的实现方法是原地置换的，当然也有不是原地置换的方法，实现起来较为简单，这里就不介绍了。
function partition(p,r:position;var L:List):position;
var
pivot:ElementType;
i,j:position;
begin
1 pivot:=Select_Pivot(p,r,L); //在L[p..r]中选择一个支点元素pivot
2 i:=p-1;
3 j:=r+1;
4 while true do
begin
5 repeat j:=j-1 until L[j]<=pivot;
//移动左指针，注意这里不能用while循环
6 repeat i:=i+1 until L[i]>=pivot;
//移动右指针，注意这里不能用while循环
7 if i< j then swap(L[i],L[j]) //交换L[i]和L[j]
8 else if j<>r then return j //返回j的值作为分割点
9 else return j-1; //返回j前一位置作为分割点
end;
end;
该算法的实现很精巧。其中，有一些细节需要注意。例如，算法中的位置i和j不会超出A[p..r]的位置界，并且该算法的循环不会出现死循环，如果将两个repeat语句换为while则要注意当L[i]=L[j]=pivot且i<j时i和j的值都不再变化，会出现死循环。
另外，最后一个if..then..语句很重要，因为如果pivot取的不好，使得Partition结束时j正好等于r，则如前所述，算法Quick_Sort会无限递归下去；因此必须判断j是否等于r，若j=r则返回j的前驱。
http://www.zsqz.com/jsbase/suanfa/commonalg/sort/internal_sorting/quick_sort/quick_sort.htm