=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]进行排序(参见 Sorting and Searching Algorithms: A Cookbook)。当然，比较方便的方法是取该阈值为1，当待排序的表只有一个元素时，根本不用排序(其实还剩两个元素时就已经在Partition函 数中排好序了)，只要把第1行的if语句该为if p=r then exit else ...。这就是通常教科书上看到的快速排序的形式。

注意：算法Quick_Sort中变量q的值一定不能等于r，否则该过程会无限递归下去，永远不能结束。因此下文中在partition函数里加了限制条件，避免q=r情况的出现。

算法Quick_Sort中调用了一个函数partition，该函数主要实现以下两个功能：

1. 在L[p..r]中选择一个支点元素pivot;

2. 对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的前驱。

以上算法的一个执行实例如图1所示，其中pivot=L[p]=5：


图1 Partition过程的一个执行实例

Partition 对L[p..r]进行划分时，以pivot作为划分的基准，然后分别从左、右两端开始，扩展两个区域L[p..i]和L[j..r]，使得L[p..i] 中元素的值小于或等于pivot，而L[j..r]中元素的值大于或等于pivot。初始时i=p-1，且j=i+1，从而这两个区域是空的。在 while循环体中，位置j逐渐减小，i逐渐增大，直到L[i]≥pivot≥L[j]。如果这两个不等式是严格的，则L[i]不会是左边区域的元素，而 L[j]不会是右边区域的元素。此时若i在j之前，就应该交换L[i]与L[j]的位置，扩展左右两个区域。 while循环重复至i不再j之前时结束。这时L[p..r]己被划分成L[p..q]和L[q+1..r]，且满足L[p..q]中元素的值不大于L [q+1..r]中元素的值。在过程Partition结束时返回划分点q。

寻找支点元素select_pivot有多种实现方法，不同的实现方法会导致快速排序的不同性能。根据分治法平衡子问题的思想，我们希望支点元素可以使L[p..r]尽量平均地分为两部分，但实际上这是很难做到的。下面我们给出几种寻找pivot的方法。

1. 选择L[p..r]的第一个元素L[p]的值作为pivot；

2. 选择L[p..r]的最后一个元素L[r]的值作为pivot；

3. 选择L[p..r]中间位置的元素L[m]的值作为pivot；

4. 选择L[p..r]的某一个随机位置上的值L[random(r-p)+p]的值作为pivot；

按照第4种方法随机选择pivot的快速排序法又称为随机化版本的快速排序法，在下面的复杂性分析中我们将看到该方法具有平均情况下最好的性能，在实际应用中该方法的性能也是最好的。

下 面是一个快速排序的Java Applet演示程序，该程序使用第一种pivot选择法，即选L[p]为pivot，因此Partition过程作了一些简化，与我们这里的 Partition过程实现方法不同，但功能相同。该程序是针对用数组实现的线性表，用C语言实现的。

线性时间排序算法

我们已经知道，通过比较确定两个元素之间相对位置的比较排序算法计算时间复杂性下界为O(nlogn)，要想改进这个下界，就必须对输入的数据作某些限制。下面介绍的几种排序算法都可以在O(n)时间内对一个线性表进行排序，但是他们要求输入数据满足某种条件。

计数排序
基数排序
桶排序
计数排序 Counting Sort

计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件：

1. 输入的线性表的元素属于有限偏序集S；

2. 设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。

在这两个条件下，计数排序的复杂性为O(n)。

计 数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列 的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时， 我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序算法可以描述如下：

1. 扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；

2. 扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。

具体的实现如下。

注意：在以下的讨论中，为了方便，我们假设线性表是用数组来实现的，并且假设线性表的元素类型TElement为整型，其值在1..k之间，线性表的长度为n，且k=O(n)。这些假设对计数排序算法没有实质的影响，但是可以使以下介绍的算法看起来容易理解。

在下面的计数排序算法中，我们假设L为输入的长度为n的线性表，输出的排序结果存放在线性表R中。算法中还用到一个辅助表tmp用于对输入元素进行计数。

Type

TElement=1..k;

TList=array [1..maxlength] of TElement;

TPosition=integer;



procedure Counting_Sort(var L,R:TList);

var

i,j:integer;

tmp:TList;

begin

1 for i:=1 to k do tmp[i]:=0;

2 for j:=1 to n do inc(tmp[L[j]]);

//执行完上面的循环后，tmp[i]的值是L中等于i的元素的个数

3 for i:=2 to k do tmp[i]:=tmp[i]+tmp[i-1];

//执行完上面的循环后，tmp[i]的值是L中小于等于i的元素的个数

4 for j:=n downto 1 do //注意这里的downto保证了排序的稳定性

begin

5 R[tmp[L[j]]]:=L[j];//L[j]存放在输出数组R的第tmp[L[j]]个位置上

6 dec(tmp[L[j]]); //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的个数

end;

end;

图1所示的是Counting_Sort作用于一个输入数组L[1..8]上的过程，其中L的每一个元