排序
排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。
设R 为非空集合A 上的二元关系，如果R 满足自反性(对于每一个x ∈A ，(x,x)∈R ) ，反对称性((x,y)∈R ∧(y,x)∈R →x=y )和传递性((x,y)∈R ∧(y,x)∈R →(x,z)∈R) ，则称R 为A 上的偏序关系，记作≤。如果(x,y)∈R ，则记作x≤y，读作“x小于等于y”。存在偏序关系的集合A 称为偏序集。
注意，这里的≤不是指数的大小，而是指在偏序关系中的顺序性。x≤y的含义是：按照这个序，x 排在y 前面。根据不同的偏序定义，≤有不同的解释。例如整除关系是偏序关系≤，3≤6的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系5≤4是指在大于或等于关系中5排在4的前面，也就是说5比4大。
在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个主键域key ，key 域的类型是某一个偏序集，记录的其他域称为卫星数据。比较线性表中的两个元素Li 和Lj 的大小，实际上是比较Li.key 和Lj.key 的大小（这种比较当然也是偏序集中的比较）。举例而言，某公司的数据库里记 录了员工的数据，每一项纪录包括姓名，编号，年龄，工资等几个域，如果以编号为key 域对员工记录排序，则是将员工记录按照编号排序；如果以工资为key 域对员工记录排序，则是将员工记录按照工资高低排序；如果以姓名为key 域对员工记录排序，则是以员工姓名的汉语拼音按照字典顺序排序。
关于偏序集的具体概念和应用，请参见离散数学的相关资料。
如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做原地置换排序算法(in place sort) ；如果排序后并不改变表中相同的元素原来的相对位置，那么这种排序算法叫做稳定排序算法(stable sort)。
排序问题一般分为内排序( internal sorting )和外排序( external sorting )两类： 内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中；
外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。
排序问题的计算复杂性
对排序算法计算时间的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。
为了对有n 个元素的线性表进行排序，至少必须扫描线性表一遍以获取这n 个元素的信息，因此排序问题的计算复杂性下界为Ω(n)。
如果我们对输入的数据不做任何要求，我们所能获得的唯一信息就是各个元素的具体的值，我们仅能通过比较来确定输入序列的元素间次序。即给定两个元素ai 和aj ，通过测试aiaj 中的哪一个成立来确定ai 和aj 间的相对次序。这样的排序算法称为比较排序算法。下面我们讨论一下比较排序算法在最坏情况下至少需要多少次比较，即比较排序算法的最坏情况复杂性下界。
我们假设每次比较只测试ai≤aj ，如果ai≤aj 成立则ai 排在aj 前面，否则ai 排在aj 后面。任何一个比较排序算法可以描述为一串比较序列:
(ai,aj),(ak,al),..,(am,an),...
表示我们首先比较(ai,aj)，然后比较(ak,al)，... ，比较(am,an)，... ，直到我们获取了足够的信息可以
确定所有元素的顺序。显而易见，如果我们对所有的元素两两进行一次比较的话(总共比较了Cn2次) ，就一定可以确定所有元素的顺序。但是，如果我们运气足够好的话，我们可能不必对所有元素两两进行一次比较。比如说对于有三个元素a1,a2,a3的线性表进行排序，如果我们先比较a1和a2，得到a1≤a2；然后比较a2和a3，得到a2≤a3；则不必比较a1和a3，因为根据偏序集的传递性，必有a1≤a3；但是如果a2≥a3，我们还必须比较a1和a3才能确定a1和a3的相对位置。如果我们适当的安排比较的次序的话，也可以减少比较的次数。这样我们可以用一棵二叉树表示比较的顺序，如下图所示：
该树的每一个非叶节点表示一次比较，每一根树枝表示一种比较结果，每一个叶节点表示一种排列顺序。这样的一棵二叉树叫做决策树，它用树枝表示了每次决策做出的选择。如此我们可以将任何一个比较排序算法用一棵决策树来表示。
请注意上图只表明了对三个元素的一种比较算法，这种比较算法依次比较(a1,a2)(a2,a3)(a1,a3)，一旦中间某步得到足够的信息就可以停止比较，但是当算法执行完后（三次比较后），一定可以确定三个元素间的次序。因此我们有理由将算法在最坏情况下的比较次数作为算法复杂性的度量，对于本例该算法在最坏情况下要进行C32=3次比较。
显然，一棵决策树中最高叶节点的高度就是该决策树对应的算法在最坏情况下所需的比较次数，而决策树中最低叶节点的高度就是该决策树对应的算法在最好情况下所需的比较次数。
我们的问题就变为：对于任意一棵决策树（任意一种比较排序算法），它的最高的树叶的高度是多少？这个高度就对应于比较排序算法所需的最多比较次数（在运气最坏的情况下）；换句话说，对于任何一个输入，该算法至少需要比较多少次就可以对元素进行排序。
我们发现，决策树的每个叶节点对应一个n 个元素的排列，其中可能有重复的；但是由于决策树表明了所有可能遇到的情况，因而n 个元素的所有排列都在决策树中出现过。n 个元素共有n! 种排列，即决策树的叶节点数目至少为n! 。又因为一棵高度为h 的二叉树（指二叉树的最高树叶高度为h ）的叶节点数目最多为2个（这时正好是满二叉树，即每个非叶节点都有两个子节点），因此n!≤2，得到h≥log(n!)，其中log 以2为底。根据Stirling 公式有n!>(n/e)n，于是h>nlogn-nloge，即h=Ω(nlogn)。
这样我们就证明了对于任意一种利用比较来确定元素间相对位置的排序算法，其最坏情况下复杂性为Ω(nlogn)。
在下文中我们将讨论几种比较排序算法，其中快速排序在平均情况下复杂性为O(nlogn)，最坏情况下复杂性为O(n2)；堆排序和合并排序在最坏情况下复杂性为O(nlogn)，因此堆排序和合并排序是渐进最优的比较排序算法。
排序算法是否还能够改进呢？从前文我们知道，如果要改进排序算法的效率，就不能只利用比较来确定元素间相对位置。因此我们还需要知道元素的其他附加信息，光知道元素的大小信息是不够的。下文中h h
我们介绍的计数排序，基数排序和桶排序是具有线性时间复杂性的排序算法，这些算法无一例外地对输入数据作了某些附加限制，从而增加已知的信息，因此可以不通过比较来确定元素间的相对位置。
冒泡排序 Bubble Sort
最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i 遍处理时，不必检查第i 高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。
procedure Bubble_Sort(var L:List);
var
i,j:position;
begin
1 for i:=First(L) to Last(L)-1 do
2 for j:=First(L) to Last(L)-i do
3 if L[j]>L[j+1] then
4 swap(L[j],L[j+1]); //交换L[j]和L[j+1]
end;
上述算法将较大的元素看作较重的气泡，每次最大的元素沉到表尾。其中First(L)和Last(L)分别表示线性表L 的第一个元素和最后一个元素的位置，swap(x,y)交换变量x,y 的值。上述算法简单地将线性表的位置当作整数用for 循环来处理，但实际上线性表可能用链表实现；而且上述算法将线性表元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明，所有的算法都用这种简化方式表达。
容易看出该算法总共进行了n(n-1)/2次比较。如果swap 过程消耗的时间不多的话，主要时间消耗在比较上，因而时间复杂性为O(n2)。但是如果元素类型是一个很大的纪录，则Swap 过程要消耗大量的时间，因此有必要分析swap 执行的次数。
显然算法Bubble_Sort在最坏情况下调用n(n-1)/2次Swap 过程。我们假设输入序列的分布是等可能的。考虑互逆的两个输入序列L1=k1,k2,..,kn和L2=kn,kn-1,..,k1。我们知道，如果ki>kj，且ki 在表中排在kj 前面，则在冒泡法排序时必定要将kj 换到ki 前面，即kj 向前浮的过程中一定要穿过一次ki ，这个过程要调用一次Swap 。对于任意的两个元素ki 和kj ，不妨设ki>kj，或者在L1中ki 排在kj 前面，或者L2在中ki 排在kj 前面，两者必居其一。因此对于任意的两个元素ki 和kj ，在对L1和L2排序时，总共需要将这两个元素对调一次。n 个元素中任取两个元素有Cn2 种取法，因此对于两个互逆序列进行排序，总共要调用Cn2 =n(n-1)/2次Swap ，平均每个序列要调用n(n-1)/4次Swap 。那么算法Bubble_Sort调用Swap 的平均次数为n(n-1)/4。
可以对冒泡算法作一些改进，如果算法第二行的某次内循环没有进行元素交换，则说明排序工作已经完成，可以退出外循环。可以用一个布尔变量来记录内循环是否进行了记录交换，如果没有则终止外循环。 冒泡法的另一个改进版本是双向扫描冒泡法（Bi-Directional Bubble Sort ）。设被排序的表中各元素键值序列为：
483 67 888 50 255 406 134 592 657 745 683
对该序列进行3次扫描后会发现，第3此扫描中最后一次交换的一对纪录是L[4]和L[5]：
50 67 255 134 | 406 483 592 657 683 745 888
显然，第3次扫描(i=3)结束后L[5]以后的序列都已经排好序了，所以下一次扫描不必到达Last(L)-i=11-4=7，即第2行的for 循环j 不必到达7，只要到达4-1=3就可以了。按照这种思路，可以
来回地进行扫描，即先从头扫到尾，再从尾扫到头。这样就得到双向冒泡排序算法：
procedure Bi-Directional_Bubble_Sort(var L:List);
var
low,up,t,i:position;
begin
1 low:=First(L);up:=Last(L);
2 while up>low do
begin
3 t:=low;
4 for i:=low to up-1 do
5 if L>L[i+1] then
begin
6 swap(L,L[i+1]);
7 t:=i;
end;
8 up:=t;
9 for i:=up downto low+1 do
10 if L
begin
11 swap(L,L[i-1]);
12 t:=i;
end;
13 low:=t;
end;
end;
算法利用两个变量low 和up 记录排序的区域L[low..up]，用变量t 记录最近一次交换纪录的位置，4-7行从前向后扫描，9-12行从后向前扫描，每次扫描以后利用t 所记录的最后一次交换记录的位置，并不断地缩小需要排序的区间，直到该区间只剩下一个元素。
直观上来看，双向冒泡法先让重的气泡沉到底下，然后让轻的气泡浮上来，然后再让较大气泡沉下去，让较轻气泡浮上来，依次反复，直到排序结束。
双向冒泡排序法的性能分析比较复杂，目前暂缺，那位朋友知道请告诉我。
冒泡排序法和双向冒泡排序法是原地置换排序法，也是稳定排序法，如果算法Bubble_Sort中第3行的比较条件L[j]>L[j+1]改为L[j]>= L[j+1]，则不再是稳定排序法。
选择排序 Selection Sort
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i 遍处理是将L[i..n]中最小者与L 交换位置。这样，经过i 遍处理之后，前i 个记录的位置已经是正确的了。
选择排序算法可实现如下。
procedure Selection_Sort(var L:List);
var
i,j,s:position;
begin
1 for i:=First(L) to Last(L)-1 do
begin
2 s:=i;
3 for j:=i+1 to Last(L) do
4 if L[j]
5 s:=j; //记录L[i..n]中最小元素的位置
6 swap(L,L[s]); //交换L,L[s]
end;
end;
算法Selection_Sort中里面的一个for 循环需要进行n-i 次比较，所以整个算法需要
次比较。
显而易见，算法Selection_Sort中共调用了n-1次swap 过程。选择排序法是一个原地置换排序法，也是稳定排序法。
插入排序 Insertion Sort
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i 遍处理仅将L 插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L 和L[i-1]，如果L[i-1]≤ L，则L[1..i]已排好序，第i 遍处理就结束了；否则交换L 与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1) ，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。
图1 对4个元素进行插入排序
在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型ElementType 中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L 是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i 遍的处理。另一个办法是在第i 遍处理开始时，就将L 放入L[0]中，这样也可以保证在适当的时候结束第i 遍处理。下面的算法中将对当前位置进行判断。
插入排序算法如下：
procedure Selection_Sort(var L:List);
var
i,j:position;
v:ElementType;
begin
1 for i:=First(L)+1 to Last(L) do
begin
2 v:=L;
3 j:=i;
4 while (jFirst(L))and(L[j-1]
begin
5 L[j]:=L[j-1]; //移动元素
6 j:=j-1;
end;
7 L[j]:=v; //插入元素
end;
end;
下面考虑算法Insertion_Sort的复杂性。对于确定的i ，内while 循环的次数为O(i)，所以整个循环体内执行了∑O(i)=O(∑i)，其中i 从2到n 。即比较次数为O(n2)。如果输入序列是从大到小排列的，那么内while 循环次数为i-1次，所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知，最坏情况下，Insertion_Sort要比较Ω(n2)次。
如果元素类型是一个很大的纪录，则算法第5行要消耗大量的时间，因此有必要分析移动元素的次数。经过分析可知，平均情况下第5行要执行n(n-1)/4次，分析方法与冒泡排序的分析相同。
如果移动元素要消耗大量的时间，则可以用链表来实现线性表，这样Insertion_Sort可以改写如下(当然前一个算法同样也适用于链表，只不过没下面这个好，但是下面算法这个比较复杂) ：
注意：在下面的算法中链表L 增加了一个哨兵单元，其中的元素为-∞，即线性表L 的第一个元素是L^.next^ procedure Selection_Sort_II(var L:PList);
var
i,j,tmp:Position;
begin
1 if L^.next=nil then exit; //如果链表L 为空则直接退出
2 i:=L^.next; //i指向L 的第一个元素，注意，L 有一个哨兵元素，因此L^.next^才是L 的第一个元素
3 while i^.nextnil do
begin
4 tmp:=i^.next; //tmp指向L 的下一个位置
5 j:=L;
6 while (ji)and(tmp^.data>=j^.next^.data) do //从前向后找到tmp 的位置，tmp 应该插在j 后面
7 j:=j^.next;
8 if ji then //j=i说明不需要改变tmp 的位置
begin
9 i^.next:=tmp^.next; //将tmp 从i 后面摘除
10 tmp^.next:=j^.next; //在j 后面插入tmp
11 j^.next:=tmp;
end
12 else i:=i^.next; //否则i 指向下一个元素
end;
end;
上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。
插入排序法是一个原地置换排序法，也是一个稳定排序法。插入法虽然在最坏情况下复杂性为θ(n2)，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。
下面是一个Java Applet制作的插入排序演示程序。
快速排序 Quick Sort
我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。
下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare 发明的。 算法的基本思想
快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：
分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。 算法的实现
算法Quick_Sort的实现：
注意：下面的记号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
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
注意：算法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 循环 7 if i
8 else if jr then return j //返回j 的值作为分割点
9 else return j-1; //返回j 前一个位置作为分割点
end;
end;
该算法的实现很精巧。其中，有一些细节需要注意。例如，算法中的位置i 和j 不会超出A[p..r]的位置界，并且该算法的循环不会出现死循环，如果将两个repeat 语句换为while 则要注意当L=L[j]=pivot且i
另外，最后一个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≥pivot≥L[j]。如果这两个不等式是严格的，则L 不会是左边区域的元素，而L[j]不会是右边区域的元素。此时若i 在j 之前，就应该交换L 与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 的方法。
选择L[p..r]的第一个元素L[p]的值作为pivot ；
选择L[p..r]的最后一个元素L[r]的值作为pivot ；
选择L[p..r]中间位置的元素L[m]的值作为pivot ；
选择L[p..r]的某一个随机位置上的值L[random(r-p)+p]的值作为pivot ；
按照第4种方法随机选择pivot 的快速排序法又称为随机化版本的快速排序法，在下面的复杂性分析中我们将看到该方法具有平均情况下最好的性能，在实际应用中该方法的性能也是最好的。
下面是一个快速排序的Java Applet演示程序，该程序使用第一种pivot 选择法，即选L[p]为pivot ，因此Partition 过程作了一些简化，与我们这里的Partition 过程实现方法不同，但功能相同。该程序是针对用数组实现的线性表，用C 语言实现的。
性能分析
下面我们就最好情况，最坏情况和平均情况对快速排序算法的性能作一点分析。
注意：这里为方便起见，我们假设算法Quick_Sort的范围阈值为1（即一直将线性表分解到只剩一个元素），这对该算法复杂性的分析没有本质的影响。
我们先分析函数partition 的性能，该函数对于确定的输入复杂性是确定的。观察该函数，我们发现，对于有n 个元素的确定输入L[p..r]，该函数运行时间显然为θ(n)。
最坏情况
无论适用哪一种方法来选择pivot ，由于我们不知道各个元素间的相对大小关系（若知道就已经排好序了），所以我们无法确定pivot 的选择对划分造成的影响。因此对各种pivot 选择法而言，最坏情况和最好情况都是相同的。
我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的
时候(设输入的表有n 个元素) 。下面我们暂时认为该猜测正确，在后文我们再详细证明该猜测。
对于有n 个元素的表L[p..r]，由于函数Partition 的计算时间为θ(n)，所以快速排序在序坏情况下的复杂性有递归式如下：
T(1)=θ(1), T(n)=T(n-1)+T(1)+θ(n) (1)
用迭代法可以解出上式的解为T(n)=θ(n2)。
这个最坏情况运行时间与插入排序是一样的。
下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。 设T(n)是过程Quick_Sort作用于规模为n 的输入上的最坏情况的时间，则
T(n)=max(T(q)+T(n-q))+θ(n) ,其中1≤q≤n-1 (2)
我们假设对于任何k
将归纳假设代入(2)，得到：
T(n)≤max(cq2+c(n-q)2)+θ(n)=c*max(q2+(n-q)2)+θ(n)
因为在[1,n-1]上q2+(n-q)2关于q 递减，所以当q=1时q2+(n-q)2有最大值n2-2(n-1)。于是有： T(n)≤cn2-2c(n-1)+θ(n)≤cn2
只要c 足够大，上面的第二个小于等于号就可以成立。于是对于所有的n 都有T(n)≤cn2 。
这样，排序算法的最坏情况运行时间为θ(n2)，且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。
最好情况
如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了。这时有：
T(n)=2T(n/2)+θ(n), T(1)=θ(1) (3)
解得： T(n)=θ(nlogn)
快速排序法最佳情况下执行过程的递归树如下图所示，图中lgn 表示以2位底的对数，而本文中用logn 表示以2位底的对数
.
图2 快速排序法最佳情况下执行过程的递归树
由于快速排序法也是基于比较的排序法，其运行时间为Ω(nlogn)，所以如果每次划分过程产生的区间大小都为n/2，则运行时间θ(nlogn)就是最好情况运行时间。
但是，是否一定要每次平均划分才能达到最好情况呢？要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分，乍一看该划分很不对称。我们可以得到递归式：
T(n)=T(n/10)+T(9n/10)+θ(n) , T(1)=θ(1) (4)
这个递归式对应的递归树如下图所示：
图3 (4)式对应的递归树
请注意该树的每一层都有代价n ，直到在深度log10n=θ(logn)处达到边界条件， 以后各层代价至多为n 。递归于深度log10/9n=θ(logn)处结束。这样，快速排序的总时间代价为T(n)=θ(nlogn)，从渐进意义上看就和划分是在中间进行的一样。事实上，即使是99:1的划分时间代价也为θ(nlogn)。其原因在于，任何一种按常数比例进行划分所产生的递归树的深度都为θ(nlogn)，其中每一层的代价为O(n)，因而不管常数比例是什么，总的运行时间都为θ(nlogn)，只不过其中隐含的常数因子有所不同。(关于算法复杂性的渐进阶，请参阅算法的复杂性)
平均情况
我们首先对平均情况下的性能作直觉上的分析。
要想对快速排序的平均情况有个较为清楚的概念，我们就要对遇到的各种输入作个假设。通常都假设输入数据的所有排列都是等可能的。后文中我们要讨论这个假设。
当我们对一个随机的输入数组应用快速排序时，要想在每一层上都有同样的划分是不太可能的。我们所能期望的是某些划分较对称，另一些则很不对称。事实上，我们可以证明，如果选择L[p..r]的第一个元素作为支点元素，Partition 所产生的划分80%以上都比9:1更对称，而另20%则比9:1差，这里证明从略。 平均情况下，Partition 产生的划分中既有“好的”，又有“差的”。这时，与Partition 执行过程对应的递归树中，好、差划分是随机地分布在树的各层上的。为与我们的直觉相一致，假设好、差划分交替出现在树的各层上，且好的划分是最佳情况划分，而差的划分是最坏情况下的划分，图4(a)表示了递归树的连续两层上的划分情况。在根节点处，划分的代价为n ，划分出来的两个子表的大小为n-1和1，即最坏情况。在根的下一层，大小为n-1的子表按最佳情况划分成大小各为(n-1)/2的两个子表。这儿我们假设含1个元素的子表的边界条件代价为1。
(a)
(b)
图4 快速排序的递归树划分中的两种情况
在一个差的划分后接一个好的划分后，产生出三个子表，大小各为1，(n-1)/2和(n-1)/2，代价共为2n-1=θ(n)。这与图4(b)中的情况差不多。该图中一层划分就产生出大小为(n-1)/2+1和(n-1)/2的两个子表，代价为n=θ(n)。这种划分差不多是完全对称的，比9:1的划分要好。从直觉上看，差的划分的代价θ(n)可被吸收到好的划分的代价θ(n)中去，结果是一个好的划分。这样，当好、差划分交替分布划分都是好的一样：仍是θ(nlogn)，但θ记号中隐含的常数因子要略大一些。关于平均情况的严格分析将在后文给出。
在前文从直觉上探讨快速排序的平均性态过程中，我们已假定输入数据的所有排列都是等可能的。如果输入的分布满足这个假设时，快速排序是对足够大的输入的理想选择。但在实际应用中，这个假设就不会总是成立。
解决的方法是，利用随机化策略，能够克服分布的等可能性假设所带来的问题。
一种随机化策略是：与对输入的分布作“假设”不同的是对输入的分布作“规定”。具体地说，在排序输入的线性表前，对其元素加以随机排列，以强制的方法使每种排列满足等可能性。事实上，我们可以找到一个能在O(n)时间内对含n 个元素的数组加以随机排列的算法。这种修改不改变算法的最坏情况运行时间，但它却使得运行时间能够独立于输入数据已排序的情况。
另一种随机化策略是：利用前文介绍的选择支点元素pivot 的第四种方法，即随机地在L[p..r]中选择一个元素作为支点元素pivot 。实际应用中通常采用这种方法。
快速排序的随机化版本有一个和其他随机化算法一样的有趣性质：没有一个特别的输入会导致最坏情况性态。这种算法的最坏情况性态是由随机数产生器决定的。你即使有意给出一个坏的输入也没用，因为随机化排列会使得输入数据的次序对算法不产生影响。只有在随机数产生器给出了一个很不巧的排列时，随机化算法的最坏情况性态才会出现。事实上可以证明几乎所有的排列都可使快速排序接近平均情况性态, 只有非常少的几个排列才会导致算法的近最坏情况性态。
一般来说，当一个算法可按多条路子做下去，但又很难决定哪一条保证是好的选择时，随机化策略是很有用的。如果大部分选择都是好的，则随机地选一个就行了。通常，一个算法在其执行过程中要做很多选择。如果一个好的选择的获益大于坏的选择的代价，那么随机地做一个选择就能得到一个很有效的算法。我们在前文已经了解到，对快速排序来说，一组好坏相杂的划分仍能产生很好的运行时间。因此我们可以认为该算法的随机化版本也能具有较好的性态。
在前文我们从直觉上分析了快速排序在平均情况下的性能为θ(nlogn)，我们将在下面定量地分析快速排序法在平均情况下的性能。为了满足输入的数据的所有排列都是等可能的这个假设，我们采用上面提到的随机选择pivot 的方法，并且在Select_pivot函数中将选出的pivot 与L[p]交换位置（这不是必需的，纯粹是为了下文分析的方便，这样L[p]就是支点元素pivot ）。那种基于对输入数据加以随机排列的随机化算法的平均性态也很好，只是比这儿介绍的这个版本更难以分析。
我们先来看看Partition 的执行过程。为简化分析，假设所有输入数据都是不同的。即使这个假设不满足，快速排序的平均情况运行时间仍为θ(nlogn)，但这时的分析就要复杂一些。
由Partition 返回的值q 仅依赖于pivot 在L[p..r]中的秩(rank)，某个数在一个集合中的秩是指该集合中小于或等于该数的元素的个数。如果设n 为L[p..r]的元素个数，将L[p]与L[p..r]中的一个随机元素pivot 交换就得rank(pivot)=i(i=1,2,..,n)的概率为l/n。
下一步来计算划分过程不同结果的可能性。如果rank(pivot)=1，即pivot 是L[p..r]中最小的元素，则Partition 的循环结束时指针i 停在i=p处，指针j 停在k=p处。当返回q 时，划分结果的" 低区" 中就含有唯一的元素L[p]=pivot。这个事件发生的概率为1/n，因为rank(pivot)=i的概率为1/n。
如果rank(pivot)≥2，则至少有一个元素小于L[p]，故在外循环while 循环的第一次执行中，指针i 停于i=p处，指针j 则在达到p 之前就停住了。这时通过交换就可将L[p]置于划分结果的高区中。当Partition 结束时，低区的rank(pivot)-1个元素中的每一个都严格小于pivot （因为假设输入的元素不重复）。这样，对每个i=1,2,..,n-1，当rank(pivot)≥2时，划分的低区中含i 个元素的概率为 l/n。 把这两种情况综合起来，我们的结论为：划分的低区的大小为1的概率为2/n，低区大小为i 的概率为1/n，i=2,3,..n-1。
现在让我们来对Quick_Sort的期望运行时间建立一个递归式。设T(n)表示排序含n 个元素的表所需的平均时间，则：
（5）
其中T(1)=θ(1)。
q 的分布基本上是均匀的，但是q=1的可能性是其他值的两倍。根据前面作的最坏情况的分析有： T(1)=θ(1),T(n-1)=θ(n2)，所以
这可被(5)式中的θ(n)所吸收，所以(5)式可简化为：
(6)
注意对k=1,2,..,n-1，和式中每一项T(k)为T(q)和T(n-q)的机会各有一次，把这两项迭起来有：
(7)
我们用代入法来解上述递归方程。归纳假设T(n)≤a*nlogn+b，其中a>0,b>0为待定常数。可以选择足够大的a,b 使anlogn+b>T(1)，对于n>1有：
（8）
下面我们来确定和式
（9）
的界。
因为和式中每一项至多是nlogn ，则有界：
这是个比较紧的界，但是对于解递归式（8）来说还不够强。为解该递归式，我们希望有界：
为了得到这个界，可以将和式(9)分解为两部分，这时有：
等号右边的第一个和式中的logk 可由log(n/2)=logn-1从上方限界。第二个和式中的logk 可由logn 从上方限界，这样，
对于n≥2成立。即
:
(10)
将(10)代入(8）式得：
（11）
因为我们可以选择足够大的a 使a*n/4能够决定θ(n)+b，所以快速排序的平均运行时间为θ(nlogn)。
计数排序 Counting Sort
计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件：
输入的线性表的元素属于有限偏序集S ；
设输入的线性表的长度为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}；则计数排序算法可以描述如下：
扫描整个集合S ，对每一个Si ∈S ，找到在线性表L 中小于等于Si 的元素的个数T(Si)；
扫描整个线性表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:=0;
2 for j:=1 to n do inc(tmp[L[j]]);
//执行完上面的循环后，tmp 的值是L 中等于i 的元素的个数
3 for i:=2 to k do tmp:=tmp+tmp[i-1];
//执行完上面的循环后，tmp 的值是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 的每一个元素都是不大于k=6的正整数。
图1 计数排序算法演示
容易理解，算法的第(l)行是对数组tmp 初始化。第(2)行检查每个输入元素。如果输入元素的键值为i ，则tmp 增1。因此，在第(2)行执行结束后，tmp 中存放着值等于i 的输入元素个数，i=1,2,..,k。算法的第(3)行，对每个i=1,2,..,i，统计值小于或等于i 的输入元素个数。最后在(4)-(8)行中，将每个元素L[j]存放到输出数组R 中相应的最终位置上。如果所有n 个元素的值都不相同，则共有tmp[L[j]]个元素的键值小于或等于L[j]，而小于L[j]的元素有tmp[L[j]]-1个，因此tmp[L[j]]就是L[j]在输出数组R 中的正确位置。当输入元素有相同的值时，每将一个L[j]存放到数组R 时，tmp[L[j]]就减1，使下 个值等于L[j]的元素存放在输出数组R 中存放元素L[j]的前一个位置上。
计数排序算法的计算时间复杂性很容易分析。其中，第(1)行需要O(k)时间；第(2)行需要O(n)时间，第(3)行需要O(k)时间；第(4)-(8)行的for 循环需要O(n)时间。这样，整个算法所需的计算间为O(n+k)。当k=O(n)时，算法的计算时间复杂性为O(n)。
我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到线性时间的上界。此外，我们还看到，由于算法第4行使用了downto 语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法，但显然不是原地置换排序算法。
基数排序 Radix Sort
基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地" 程序化" 以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，
操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。 对十进制数字来说，每列中只用到10个位置(另两个位置用于编码非数值字符) 。一个d 位数占用d 个列。因为卡片排序器一次只能查看一个列，要对n 张片上的d 位数进行排序就要有个排序算法。
直感上，大家可能觉得应该按最重要的一位排序，然后对每个盒子中的数递归地排序，最后把结果合并起来。不幸的是，为排序每一个盒子中的数，10个盒子中的9个必须先放在一边，这个过程产生了许多要加以记录的中间卡片堆。
与人们的直感相反，基数排序是首先按最不重要的一位数字排序来解决卡片排序问题的。同样，把各堆卡片收集成一迭，其中0号盒子中的在1号盒子中的前面，后者又在2号盒子中的前面，等等。然后对整个一迭卡片按次重要位排序，并把结果同样地合并起来。重复这个过程，直到对所有的d 位数字都进行了排序。所以，仅需要n 遍就可将一迭卡片排好序。图1说明了基数排序作“一迭”7个三位数的过程。第一列为输入，其余各列示出了对各个数位进行逐次排序后表的情形。垂直向上的箭头指示了当前要被加以排序的数位。
图1 基数排序作用于一个由7个3位数组成的表上的过程
关于这个算法很重要的一点就是按位排序要稳定。由卡片排序器所故的排序是稳定的，但操作员在把卡片从盒子里拿出来时不能改变他们的次序，即使某一盒子中所有卡片在给定列上的穿孔位置都相同。 在一台典型的顺序随机存取计算机上，有时采用基数排序来对有多重域关键字的记录进行排序。例如，假设我们想根据三个关键字处、月和日来对日期排序。对这个问题，可以用带有比较函数的排序算法来做。给定两个日期，先比较年份，如果相同，再比较月份，如果再相同，再比较日。这儿我们可以采用另一个方法，即用一种稳定的排序方法对所给信息进行三次排序：先对日，其次对月，再对年。
基数排序的代码是很简单的、下面的过程假设长度为n 的数组A 中的每个元素都有d 位数字，其中第1位是最低的，第d 位是最高位。
procedure Radix_Sort(var L:List;d:integer);
var
i:integer;
begin
1 for i:=1 to d do
2 使用一种稳定的排序方法来对数组L 按数字i 进行排序;
end;
基数排序的正确性可以通过对正在被排序的列进行归纳而加以证明。对本算法时间代价的分析要取决于选择哪种稳定的中间排序算法。当每位数字都界于l 到k 之间，且k 不太大时，可以选择计数排序。对n 个d 位数的每一遍处理的时间为O(n+k)，共有d 遍，故基数排序的总时间为θ(dn+kd)。当d 为常数，k=O(n)时，基数排序有线性运行时间。
某些计算机科学家倾向于把一个计算机字中所含位数看成是θ(lgn)。具体一点说，假设共有dlgn 位数字，d 为正常数。这样，如果待排序的每个数恰能容于一个计算机字内，我们就可以把它视为一个以n 为基数的d 位数。看一个例子：对一百万个64位数排序。通过把这些数当作是以216为基数的四位数，用基数排序四遍就可完成排序。这与一个典型的O(nlgn)比较排序相比要好得多，后者对每一个参加排序的数约要
lgn=20次操作。但有一点不理想，即采用计数排序作为中间稳定排序算法的基数排序版本不能够进行原地置换排序，而很多O(nlgn)比较排序算法却是可以的。因此，当内存比较紧张时，一般来说选择快速排序更合适些。
桶排序 Bin Sort
平均情况下桶排序以线性时间运行。像计数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1) 上。
桶排序的思想就是把区间[0，1) 划分成n 个相同大小的子区间，或称桶，然后将n 个输入数分布到各个桶中去。因为输入数均匀分布在[0，1) 上，所以一般不会有很多数落在 一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列 出来即可。
在桶排序算法的代码中，假设输入是个含n 个元素的数组A ，且每个元素满足0≤ A
桶排序的算法如下，其中floor(x)是地板函数，表示不超过x 的最大整数。
procedure Bin_Sort(var A:List);
begin
1 n:=length(A);
2 for i:=1 to n do
3 将A 插到表B[floor(n*A)]中;
4 for i:=0 to n-1 do
5 用插入排序对表B 进行排序;
6 将表B[0],B[1],...,B[n-1]按顺序合并;
end;
图1 Bin_Sort的操作
图1演示了桶排序作用于有10个数的输入数组上的操作过程。(a)输入数组A[1..10]。(b)在该算法的第5行后的有序表(桶) 数组B[0..9]。桶i 中存放了区间[i/10，(i+1)/10]上的值。排序输出由表B[O]、B[1]、... 、B[9]的按序并置构成。
要说明这个算法能证确地工作，看两个元素A 和A[j]。如果它们落在同一个桶中，则它们在输出序列中有着正确的相对次序，因为它们所在的桶是采用插入排序的。现假设它们落到不同的桶中，设分别为B[i']和B[j']。不失一般性，假设i'
我们有：
i'=floor(n*A)≥floor(n*A[j])=j'
得矛盾 (因为i'
现在来分析算法的运行时间。除第5行外，所有各行在最坏情况的时间都是O(n)。第5行中检查所有桶的时间是O(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的时间。
为分析插人排序的时间代价，设ni 为表示桶B 中元素个数的随机变量。因为插入排序以二次时间运行，故为排序桶B 中元素的期望时间为E[O(ni2)]=O(E[ni2])，对各个桶中的所有元素排序的总期望时间为：
(1)
为了求这个和式，要确定每个随机变量ni 的分布。我们共有n 个元素，n 个桶。某个元素落到桶B 的概率为l/n，因为每个桶对应于区间[0，1) 的l/n。这种情况与投球的例子很类似：有n 个球 (元素) 和n 个盒子 (桶) ，每次投球都是独立的，且以概率p=1/n落到任一桶中。这样，ni=k的概率就服从二项分布B(k;n,p)，其期望值为E[ni]=np=1，方差V[ni]=np(1-p)=1-1/n。对任意随机变量X ，有
:
(2)
将这个界用到(1)式上，得出桶排序中的插人排序的期望运行时间为O(n)。因而，整个桶排序的期望运行时间就是线性的。
在该演示程序中，线性表的元素类型为整型，桶的标号为整数，算法将值为i 的元素放入标号为i 的桶中，再按照桶的标号的顺序将元素依次取出，就得到了最终的排序结果。
排序
排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。
设R 为非空集合A 上的二元关系，如果R 满足自反性(对于每一个x ∈A ，(x,x)∈R ) ，反对称性((x,y)∈R ∧(y,x)∈R →x=y )和传递性((x,y)∈R ∧(y,x)∈R →(x,z)∈R) ，则称R 为A 上的偏序关系，记作≤。如果(x,y)∈R ，则记作x≤y，读作“x小于等于y”。存在偏序关系的集合A 称为偏序集。
注意，这里的≤不是指数的大小，而是指在偏序关系中的顺序性。x≤y的含义是：按照这个序，x 排在y 前面。根据不同的偏序定义，≤有不同的解释。例如整除关系是偏序关系≤，3≤6的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系5≤4是指在大于或等于关系中5排在4的前面，也就是说5比4大。
在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个主键域key ，key 域的类型是某一个偏序集，记录的其他域称为卫星数据。比较线性表中的两个元素Li 和Lj 的大小，实际上是比较Li.key 和Lj.key 的大小（这种比较当然也是偏序集中的比较）。举例而言，某公司的数据库里记 录了员工的数据，每一项纪录包括姓名，编号，年龄，工资等几个域，如果以编号为key 域对员工记录排序，则是将员工记录按照编号排序；如果以工资为key 域对员工记录排序，则是将员工记录按照工资高低排序；如果以姓名为key 域对员工记录排序，则是以员工姓名的汉语拼音按照字典顺序排序。
关于偏序集的具体概念和应用，请参见离散数学的相关资料。
如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做原地置换排序算法(in place sort) ；如果排序后并不改变表中相同的元素原来的相对位置，那么这种排序算法叫做稳定排序算法(stable sort)。
排序问题一般分为内排序( internal sorting )和外排序( external sorting )两类： 内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中；
外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。
排序问题的计算复杂性
对排序算法计算时间的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。
为了对有n 个元素的线性表进行排序，至少必须扫描线性表一遍以获取这n 个元素的信息，因此排序问题的计算复杂性下界为Ω(n)。
如果我们对输入的数据不做任何要求，我们所能获得的唯一信息就是各个元素的具体的值，我们仅能通过比较来确定输入序列的元素间次序。即给定两个元素ai 和aj ，通过测试aiaj 中的哪一个成立来确定ai 和aj 间的相对次序。这样的排序算法称为比较排序算法。下面我们讨论一下比较排序算法在最坏情况下至少需要多少次比较，即比较排序算法的最坏情况复杂性下界。
我们假设每次比较只测试ai≤aj ，如果ai≤aj 成立则ai 排在aj 前面，否则ai 排在aj 后面。任何一个比较排序算法可以描述为一串比较序列:
(ai,aj),(ak,al),..,(am,an),...
表示我们首先比较(ai,aj)，然后比较(ak,al)，... ，比较(am,an)，... ，直到我们获取了足够的信息可以
确定所有元素的顺序。显而易见，如果我们对所有的元素两两进行一次比较的话(总共比较了Cn2次) ，就一定可以确定所有元素的顺序。但是，如果我们运气足够好的话，我们可能不必对所有元素两两进行一次比较。比如说对于有三个元素a1,a2,a3的线性表进行排序，如果我们先比较a1和a2，得到a1≤a2；然后比较a2和a3，得到a2≤a3；则不必比较a1和a3，因为根据偏序集的传递性，必有a1≤a3；但是如果a2≥a3，我们还必须比较a1和a3才能确定a1和a3的相对位置。如果我们适当的安排比较的次序的话，也可以减少比较的次数。这样我们可以用一棵二叉树表示比较的顺序，如下图所示：
该树的每一个非叶节点表示一次比较，每一根树枝表示一种比较结果，每一个叶节点表示一种排列顺序。这样的一棵二叉树叫做决策树，它用树枝表示了每次决策做出的选择。如此我们可以将任何一个比较排序算法用一棵决策树来表示。
请注意上图只表明了对三个元素的一种比较算法，这种比较算法依次比较(a1,a2)(a2,a3)(a1,a3)，一旦中间某步得到足够的信息就可以停止比较，但是当算法执行完后（三次比较后），一定可以确定三个元素间的次序。因此我们有理由将算法在最坏情况下的比较次数作为算法复杂性的度量，对于本例该算法在最坏情况下要进行C32=3次比较。
显然，一棵决策树中最高叶节点的高度就是该决策树对应的算法在最坏情况下所需的比较次数，而决策树中最低叶节点的高度就是该决策树对应的算法在最好情况下所需的比较次数。
我们的问题就变为：对于任意一棵决策树（任意一种比较排序算法），它的最高的树叶的高度是多少？这个高度就对应于比较排序算法所需的最多比较次数（在运气最坏的情况下）；换句话说，对于任何一个输入，该算法至少需要比较多少次就可以对元素进行排序。
我们发现，决策树的每个叶节点对应一个n 个元素的排列，其中可能有重复的；但是由于决策树表明了所有可能遇到的情况，因而n 个元素的所有排列都在决策树中出现过。n 个元素共有n! 种排列，即决策树的叶节点数目至少为n! 。又因为一棵高度为h 的二叉树（指二叉树的最高树叶高度为h ）的叶节点数目最多为2个（这时正好是满二叉树，即每个非叶节点都有两个子节点），因此n!≤2，得到h≥log(n!)，其中log 以2为底。根据Stirling 公式有n!>(n/e)n，于是h>nlogn-nloge，即h=Ω(nlogn)。
这样我们就证明了对于任意一种利用比较来确定元素间相对位置的排序算法，其最坏情况下复杂性为Ω(nlogn)。
在下文中我们将讨论几种比较排序算法，其中快速排序在平均情况下复杂性为O(nlogn)，最坏情况下复杂性为O(n2)；堆排序和合并排序在最坏情况下复杂性为O(nlogn)，因此堆排序和合并排序是渐进最优的比较排序算法。
排序算法是否还能够改进呢？从前文我们知道，如果要改进排序算法的效率，就不能只利用比较来确定元素间相对位置。因此我们还需要知道元素的其他附加信息，光知道元素的大小信息是不够的。下文中h h
我们介绍的计数排序，基数排序和桶排序是具有线性时间复杂性的排序算法，这些算法无一例外地对输入数据作了某些附加限制，从而增加已知的信息，因此可以不通过比较来确定元素间的相对位置。
冒泡排序 Bubble Sort
最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i 遍处理时，不必检查第i 高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。
procedure Bubble_Sort(var L:List);
var
i,j:position;
begin
1 for i:=First(L) to Last(L)-1 do
2 for j:=First(L) to Last(L)-i do
3 if L[j]>L[j+1] then
4 swap(L[j],L[j+1]); //交换L[j]和L[j+1]
end;
上述算法将较大的元素看作较重的气泡，每次最大的元素沉到表尾。其中First(L)和Last(L)分别表示线性表L 的第一个元素和最后一个元素的位置，swap(x,y)交换变量x,y 的值。上述算法简单地将线性表的位置当作整数用for 循环来处理，但实际上线性表可能用链表实现；而且上述算法将线性表元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明，所有的算法都用这种简化方式表达。
容易看出该算法总共进行了n(n-1)/2次比较。如果swap 过程消耗的时间不多的话，主要时间消耗在比较上，因而时间复杂性为O(n2)。但是如果元素类型是一个很大的纪录，则Swap 过程要消耗大量的时间，因此有必要分析swap 执行的次数。
显然算法Bubble_Sort在最坏情况下调用n(n-1)/2次Swap 过程。我们假设输入序列的分布是等可能的。考虑互逆的两个输入序列L1=k1,k2,..,kn和L2=kn,kn-1,..,k1。我们知道，如果ki>kj，且ki 在表中排在kj 前面，则在冒泡法排序时必定要将kj 换到ki 前面，即kj 向前浮的过程中一定要穿过一次ki ，这个过程要调用一次Swap 。对于任意的两个元素ki 和kj ，不妨设ki>kj，或者在L1中ki 排在kj 前面，或者L2在中ki 排在kj 前面，两者必居其一。因此对于任意的两个元素ki 和kj ，在对L1和L2排序时，总共需要将这两个元素对调一次。n 个元素中任取两个元素有Cn2 种取法，因此对于两个互逆序列进行排序，总共要调用Cn2 =n(n-1)/2次Swap ，平均每个序列要调用n(n-1)/4次Swap 。那么算法Bubble_Sort调用Swap 的平均次数为n(n-1)/4。
可以对冒泡算法作一些改进，如果算法第二行的某次内循环没有进行元素交换，则说明排序工作已经完成，可以退出外循环。可以用一个布尔变量来记录内循环是否进行了记录交换，如果没有则终止外循环。 冒泡法的另一个改进版本是双向扫描冒泡法（Bi-Directional Bubble Sort ）。设被排序的表中各元素键值序列为：
483 67 888 50 255 406 134 592 657 745 683
对该序列进行3次扫描后会发现，第3此扫描中最后一次交换的一对纪录是L[4]和L[5]：
50 67 255 134 | 406 483 592 657 683 745 888
显然，第3次扫描(i=3)结束后L[5]以后的序列都已经排好序了，所以下一次扫描不必到达Last(L)-i=11-4=7，即第2行的for 循环j 不必到达7，只要到达4-1=3就可以了。按照这种思路，可以
来回地进行扫描，即先从头扫到尾，再从尾扫到头。这样就得到双向冒泡排序算法：
procedure Bi-Directional_Bubble_Sort(var L:List);
var
low,up,t,i:position;
begin
1 low:=First(L);up:=Last(L);
2 while up>low do
begin
3 t:=low;
4 for i:=low to up-1 do
5 if L>L[i+1] then
begin
6 swap(L,L[i+1]);
7 t:=i;
end;
8 up:=t;
9 for i:=up downto low+1 do
10 if L
begin
11 swap(L,L[i-1]);
12 t:=i;
end;
13 low:=t;
end;
end;
算法利用两个变量low 和up 记录排序的区域L[low..up]，用变量t 记录最近一次交换纪录的位置，4-7行从前向后扫描，9-12行从后向前扫描，每次扫描以后利用t 所记录的最后一次交换记录的位置，并不断地缩小需要排序的区间，直到该区间只剩下一个元素。
直观上来看，双向冒泡法先让重的气泡沉到底下，然后让轻的气泡浮上来，然后再让较大气泡沉下去，让较轻气泡浮上来，依次反复，直到排序结束。
双向冒泡排序法的性能分析比较复杂，目前暂缺，那位朋友知道请告诉我。
冒泡排序法和双向冒泡排序法是原地置换排序法，也是稳定排序法，如果算法Bubble_Sort中第3行的比较条件L[j]>L[j+1]改为L[j]>= L[j+1]，则不再是稳定排序法。
选择排序 Selection Sort
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i 遍处理是将L[i..n]中最小者与L 交换位置。这样，经过i 遍处理之后，前i 个记录的位置已经是正确的了。
选择排序算法可实现如下。
procedure Selection_Sort(var L:List);
var
i,j,s:position;
begin
1 for i:=First(L) to Last(L)-1 do
begin
2 s:=i;
3 for j:=i+1 to Last(L) do
4 if L[j]
5 s:=j; //记录L[i..n]中最小元素的位置
6 swap(L,L[s]); //交换L,L[s]
end;
end;
算法Selection_Sort中里面的一个for 循环需要进行n-i 次比较，所以整个算法需要
次比较。
显而易见，算法Selection_Sort中共调用了n-1次swap 过程。选择排序法是一个原地置换排序法，也是稳定排序法。
插入排序 Insertion Sort
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i 遍处理仅将L 插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L 和L[i-1]，如果L[i-1]≤ L，则L[1..i]已排好序，第i 遍处理就结束了；否则交换L 与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1) ，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。
图1 对4个元素进行插入排序
在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型ElementType 中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L 是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i 遍的处理。另一个办法是在第i 遍处理开始时，就将L 放入L[0]中，这样也可以保证在适当的时候结束第i 遍处理。下面的算法中将对当前位置进行判断。
插入排序算法如下：
procedure Selection_Sort(var L:List);
var
i,j:position;
v:ElementType;
begin
1 for i:=First(L)+1 to Last(L) do
begin
2 v:=L;
3 j:=i;
4 while (jFirst(L))and(L[j-1]
begin
5 L[j]:=L[j-1]; //移动元素
6 j:=j-1;
end;
7 L[j]:=v; //插入元素
end;
end;
下面考虑算法Insertion_Sort的复杂性。对于确定的i ，内while 循环的次数为O(i)，所以整个循环体内执行了∑O(i)=O(∑i)，其中i 从2到n 。即比较次数为O(n2)。如果输入序列是从大到小排列的，那么内while 循环次数为i-1次，所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知，最坏情况下，Insertion_Sort要比较Ω(n2)次。
如果元素类型是一个很大的纪录，则算法第5行要消耗大量的时间，因此有必要分析移动元素的次数。经过分析可知，平均情况下第5行要执行n(n-1)/4次，分析方法与冒泡排序的分析相同。
如果移动元素要消耗大量的时间，则可以用链表来实现线性表，这样Insertion_Sort可以改写如下(当然前一个算法同样也适用于链表，只不过没下面这个好，但是下面算法这个比较复杂) ：
注意：在下面的算法中链表L 增加了一个哨兵单元，其中的元素为-∞，即线性表L 的第一个元素是L^.next^ procedure Selection_Sort_II(var L:PList);
var
i,j,tmp:Position;
begin
1 if L^.next=nil then exit; //如果链表L 为空则直接退出
2 i:=L^.next; //i指向L 的第一个元素，注意，L 有一个哨兵元素，因此L^.next^才是L 的第一个元素
3 while i^.nextnil do
begin
4 tmp:=i^.next; //tmp指向L 的下一个位置
5 j:=L;
6 while (ji)and(tmp^.data>=j^.next^.data) do //从前向后找到tmp 的位置，tmp 应该插在j 后面
7 j:=j^.next;
8 if ji then //j=i说明不需要改变tmp 的位置
begin
9 i^.next:=tmp^.next; //将tmp 从i 后面摘除
10 tmp^.next:=j^.next; //在j 后面插入tmp
11 j^.next:=tmp;
end
12 else i:=i^.next; //否则i 指向下一个元素
end;
end;
上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。
插入排序法是一个原地置换排序法，也是一个稳定排序法。插入法虽然在最坏情况下复杂性为θ(n2)，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。
下面是一个Java Applet制作的插入排序演示程序。
快速排序 Quick Sort
我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。
下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare 发明的。 算法的基本思想
快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：
分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。 算法的实现
算法Quick_Sort的实现：
注意：下面的记号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
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
注意：算法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 循环 7 if i
8 else if jr then return j //返回j 的值作为分割点
9 else return j-1; //返回j 前一个位置作为分割点
end;
end;
该算法的实现很精巧。其中，有一些细节需要注意。例如，算法中的位置i 和j 不会超出A[p..r]的位置界，并且该算法的循环不会出现死循环，如果将两个repeat 语句换为while 则要注意当L=L[j]=pivot且i
另外，最后一个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≥pivot≥L[j]。如果这两个不等式是严格的，则L 不会是左边区域的元素，而L[j]不会是右边区域的元素。此时若i 在j 之前，就应该交换L 与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 的方法。
选择L[p..r]的第一个元素L[p]的值作为pivot ；
选择L[p..r]的最后一个元素L[r]的值作为pivot ；
选择L[p..r]中间位置的元素L[m]的值作为pivot ；
选择L[p..r]的某一个随机位置上的值L[random(r-p)+p]的值作为pivot ；
按照第4种方法随机选择pivot 的快速排序法又称为随机化版本的快速排序法，在下面的复杂性分析中我们将看到该方法具有平均情况下最好的性能，在实际应用中该方法的性能也是最好的。
下面是一个快速排序的Java Applet演示程序，该程序使用第一种pivot 选择法，即选L[p]为pivot ，因此Partition 过程作了一些简化，与我们这里的Partition 过程实现方法不同，但功能相同。该程序是针对用数组实现的线性表，用C 语言实现的。
性能分析
下面我们就最好情况，最坏情况和平均情况对快速排序算法的性能作一点分析。
注意：这里为方便起见，我们假设算法Quick_Sort的范围阈值为1（即一直将线性表分解到只剩一个元素），这对该算法复杂性的分析没有本质的影响。
我们先分析函数partition 的性能，该函数对于确定的输入复杂性是确定的。观察该函数，我们发现，对于有n 个元素的确定输入L[p..r]，该函数运行时间显然为θ(n)。
最坏情况
无论适用哪一种方法来选择pivot ，由于我们不知道各个元素间的相对大小关系（若知道就已经排好序了），所以我们无法确定pivot 的选择对划分造成的影响。因此对各种pivot 选择法而言，最坏情况和最好情况都是相同的。
我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的
时候(设输入的表有n 个元素) 。下面我们暂时认为该猜测正确，在后文我们再详细证明该猜测。
对于有n 个元素的表L[p..r]，由于函数Partition 的计算时间为θ(n)，所以快速排序在序坏情况下的复杂性有递归式如下：
T(1)=θ(1), T(n)=T(n-1)+T(1)+θ(n) (1)
用迭代法可以解出上式的解为T(n)=θ(n2)。
这个最坏情况运行时间与插入排序是一样的。
下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。 设T(n)是过程Quick_Sort作用于规模为n 的输入上的最坏情况的时间，则
T(n)=max(T(q)+T(n-q))+θ(n) ,其中1≤q≤n-1 (2)
我们假设对于任何k
将归纳假设代入(2)，得到：
T(n)≤max(cq2+c(n-q)2)+θ(n)=c*max(q2+(n-q)2)+θ(n)
因为在[1,n-1]上q2+(n-q)2关于q 递减，所以当q=1时q2+(n-q)2有最大值n2-2(n-1)。于是有： T(n)≤cn2-2c(n-1)+θ(n)≤cn2
只要c 足够大，上面的第二个小于等于号就可以成立。于是对于所有的n 都有T(n)≤cn2 。
这样，排序算法的最坏情况运行时间为θ(n2)，且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。
最好情况
如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了。这时有：
T(n)=2T(n/2)+θ(n), T(1)=θ(1) (3)
解得： T(n)=θ(nlogn)
快速排序法最佳情况下执行过程的递归树如下图所示，图中lgn 表示以2位底的对数，而本文中用logn 表示以2位底的对数
.
图2 快速排序法最佳情况下执行过程的递归树
由于快速排序法也是基于比较的排序法，其运行时间为Ω(nlogn)，所以如果每次划分过程产生的区间大小都为n/2，则运行时间θ(nlogn)就是最好情况运行时间。
但是，是否一定要每次平均划分才能达到最好情况呢？要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分，乍一看该划分很不对称。我们可以得到递归式：
T(n)=T(n/10)+T(9n/10)+θ(n) , T(1)=θ(1) (4)
这个递归式对应的递归树如下图所示：
图3 (4)式对应的递归树
请注意该树的每一层都有代价n ，直到在深度log10n=θ(logn)处达到边界条件， 以后各层代价至多为n 。递归于深度log10/9n=θ(logn)处结束。这样，快速排序的总时间代价为T(n)=θ(nlogn)，从渐进意义上看就和划分是在中间进行的一样。事实上，即使是99:1的划分时间代价也为θ(nlogn)。其原因在于，任何一种按常数比例进行划分所产生的递归树的深度都为θ(nlogn)，其中每一层的代价为O(n)，因而不管常数比例是什么，总的运行时间都为θ(nlogn)，只不过其中隐含的常数因子有所不同。(关于算法复杂性的渐进阶，请参阅算法的复杂性)
平均情况
我们首先对平均情况下的性能作直觉上的分析。
要想对快速排序的平均情况有个较为清楚的概念，我们就要对遇到的各种输入作个假设。通常都假设输入数据的所有排列都是等可能的。后文中我们要讨论这个假设。
当我们对一个随机的输入数组应用快速排序时，要想在每一层上都有同样的划分是不太可能的。我们所能期望的是某些划分较对称，另一些则很不对称。事实上，我们可以证明，如果选择L[p..r]的第一个元素作为支点元素，Partition 所产生的划分80%以上都比9:1更对称，而另20%则比9:1差，这里证明从略。 平均情况下，Partition 产生的划分中既有“好的”，又有“差的”。这时，与Partition 执行过程对应的递归树中，好、差划分是随机地分布在树的各层上的。为与我们的直觉相一致，假设好、差划分交替出现在树的各层上，且好的划分是最佳情况划分，而差的划分是最坏情况下的划分，图4(a)表示了递归树的连续两层上的划分情况。在根节点处，划分的代价为n ，划分出来的两个子表的大小为n-1和1，即最坏情况。在根的下一层，大小为n-1的子表按最佳情况划分成大小各为(n-1)/2的两个子表。这儿我们假设含1个元素的子表的边界条件代价为1。
(a)
(b)
图4 快速排序的递归树划分中的两种情况
在一个差的划分后接一个好的划分后，产生出三个子表，大小各为1，(n-1)/2和(n-1)/2，代价共为2n-1=θ(n)。这与图4(b)中的情况差不多。该图中一层划分就产生出大小为(n-1)/2+1和(n-1)/2的两个子表，代价为n=θ(n)。这种划分差不多是完全对称的，比9:1的划分要好。从直觉上看，差的划分的代价θ(n)可被吸收到好的划分的代价θ(n)中去，结果是一个好的划分。这样，当好、差划分交替分布划分都是好的一样：仍是θ(nlogn)，但θ记号中隐含的常数因子要略大一些。关于平均情况的严格分析将在后文给出。
在前文从直觉上探讨快速排序的平均性态过程中，我们已假定输入数据的所有排列都是等可能的。如果输入的分布满足这个假设时，快速排序是对足够大的输入的理想选择。但在实际应用中，这个假设就不会总是成立。
解决的方法是，利用随机化策略，能够克服分布的等可能性假设所带来的问题。
一种随机化策略是：与对输入的分布作“假设”不同的是对输入的分布作“规定”。具体地说，在排序输入的线性表前，对其元素加以随机排列，以强制的方法使每种排列满足等可能性。事实上，我们可以找到一个能在O(n)时间内对含n 个元素的数组加以随机排列的算法。这种修改不改变算法的最坏情况运行时间，但它却使得运行时间能够独立于输入数据已排序的情况。
另一种随机化策略是：利用前文介绍的选择支点元素pivot 的第四种方法，即随机地在L[p..r]中选择一个元素作为支点元素pivot 。实际应用中通常采用这种方法。
快速排序的随机化版本有一个和其他随机化算法一样的有趣性质：没有一个特别的输入会导致最坏情况性态。这种算法的最坏情况性态是由随机数产生器决定的。你即使有意给出一个坏的输入也没用，因为随机化排列会使得输入数据的次序对算法不产生影响。只有在随机数产生器给出了一个很不巧的排列时，随机化算法的最坏情况性态才会出现。事实上可以证明几乎所有的排列都可使快速排序接近平均情况性态, 只有非常少的几个排列才会导致算法的近最坏情况性态。
一般来说，当一个算法可按多条路子做下去，但又很难决定哪一条保证是好的选择时，随机化策略是很有用的。如果大部分选择都是好的，则随机地选一个就行了。通常，一个算法在其执行过程中要做很多选择。如果一个好的选择的获益大于坏的选择的代价，那么随机地做一个选择就能得到一个很有效的算法。我们在前文已经了解到，对快速排序来说，一组好坏相杂的划分仍能产生很好的运行时间。因此我们可以认为该算法的随机化版本也能具有较好的性态。
在前文我们从直觉上分析了快速排序在平均情况下的性能为θ(nlogn)，我们将在下面定量地分析快速排序法在平均情况下的性能。为了满足输入的数据的所有排列都是等可能的这个假设，我们采用上面提到的随机选择pivot 的方法，并且在Select_pivot函数中将选出的pivot 与L[p]交换位置（这不是必需的，纯粹是为了下文分析的方便，这样L[p]就是支点元素pivot ）。那种基于对输入数据加以随机排列的随机化算法的平均性态也很好，只是比这儿介绍的这个版本更难以分析。
我们先来看看Partition 的执行过程。为简化分析，假设所有输入数据都是不同的。即使这个假设不满足，快速排序的平均情况运行时间仍为θ(nlogn)，但这时的分析就要复杂一些。
由Partition 返回的值q 仅依赖于pivot 在L[p..r]中的秩(rank)，某个数在一个集合中的秩是指该集合中小于或等于该数的元素的个数。如果设n 为L[p..r]的元素个数，将L[p]与L[p..r]中的一个随机元素pivot 交换就得rank(pivot)=i(i=1,2,..,n)的概率为l/n。
下一步来计算划分过程不同结果的可能性。如果rank(pivot)=1，即pivot 是L[p..r]中最小的元素，则Partition 的循环结束时指针i 停在i=p处，指针j 停在k=p处。当返回q 时，划分结果的" 低区" 中就含有唯一的元素L[p]=pivot。这个事件发生的概率为1/n，因为rank(pivot)=i的概率为1/n。
如果rank(pivot)≥2，则至少有一个元素小于L[p]，故在外循环while 循环的第一次执行中，指针i 停于i=p处，指针j 则在达到p 之前就停住了。这时通过交换就可将L[p]置于划分结果的高区中。当Partition 结束时，低区的rank(pivot)-1个元素中的每一个都严格小于pivot （因为假设输入的元素不重复）。这样，对每个i=1,2,..,n-1，当rank(pivot)≥2时，划分的低区中含i 个元素的概率为 l/n。 把这两种情况综合起来，我们的结论为：划分的低区的大小为1的概率为2/n，低区大小为i 的概率为1/n，i=2,3,..n-1。
现在让我们来对Quick_Sort的期望运行时间建立一个递归式。设T(n)表示排序含n 个元素的表所需的平均时间，则：
（5）
其中T(1)=θ(1)。
q 的分布基本上是均匀的，但是q=1的可能性是其他值的两倍。根据前面作的最坏情况的分析有： T(1)=θ(1),T(n-1)=θ(n2)，所以
这可被(5)式中的θ(n)所吸收，所以(5)式可简化为：
(6)
注意对k=1,2,..,n-1，和式中每一项T(k)为T(q)和T(n-q)的机会各有一次，把这两项迭起来有：
(7)
我们用代入法来解上述递归方程。归纳假设T(n)≤a*nlogn+b，其中a>0,b>0为待定常数。可以选择足够大的a,b 使anlogn+b>T(1)，对于n>1有：
（8）
下面我们来确定和式
（9）
的界。
因为和式中每一项至多是nlogn ，则有界：
这是个比较紧的界，但是对于解递归式（8）来说还不够强。为解该递归式，我们希望有界：
为了得到这个界，可以将和式(9)分解为两部分，这时有：
等号右边的第一个和式中的logk 可由log(n/2)=logn-1从上方限界。第二个和式中的logk 可由logn 从上方限界，这样，
对于n≥2成立。即
:
(10)
将(10)代入(8）式得：
（11）
因为我们可以选择足够大的a 使a*n/4能够决定θ(n)+b，所以快速排序的平均运行时间为θ(nlogn)。
计数排序 Counting Sort
计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件：
输入的线性表的元素属于有限偏序集S ；
设输入的线性表的长度为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}；则计数排序算法可以描述如下：
扫描整个集合S ，对每一个Si ∈S ，找到在线性表L 中小于等于Si 的元素的个数T(Si)；
扫描整个线性表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:=0;
2 for j:=1 to n do inc(tmp[L[j]]);
//执行完上面的循环后，tmp 的值是L 中等于i 的元素的个数
3 for i:=2 to k do tmp:=tmp+tmp[i-1];
//执行完上面的循环后，tmp 的值是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 的每一个元素都是不大于k=6的正整数。
图1 计数排序算法演示
容易理解，算法的第(l)行是对数组tmp 初始化。第(2)行检查每个输入元素。如果输入元素的键值为i ，则tmp 增1。因此，在第(2)行执行结束后，tmp 中存放着值等于i 的输入元素个数，i=1,2,..,k。算法的第(3)行，对每个i=1,2,..,i，统计值小于或等于i 的输入元素个数。最后在(4)-(8)行中，将每个元素L[j]存放到输出数组R 中相应的最终位置上。如果所有n 个元素的值都不相同，则共有tmp[L[j]]个元素的键值小于或等于L[j]，而小于L[j]的元素有tmp[L[j]]-1个，因此tmp[L[j]]就是L[j]在输出数组R 中的正确位置。当输入元素有相同的值时，每将一个L[j]存放到数组R 时，tmp[L[j]]就减1，使下 个值等于L[j]的元素存放在输出数组R 中存放元素L[j]的前一个位置上。
计数排序算法的计算时间复杂性很容易分析。其中，第(1)行需要O(k)时间；第(2)行需要O(n)时间，第(3)行需要O(k)时间；第(4)-(8)行的for 循环需要O(n)时间。这样，整个算法所需的计算间为O(n+k)。当k=O(n)时，算法的计算时间复杂性为O(n)。
我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到线性时间的上界。此外，我们还看到，由于算法第4行使用了downto 语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法，但显然不是原地置换排序算法。
基数排序 Radix Sort
基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地" 程序化" 以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，
操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。 对十进制数字来说，每列中只用到10个位置(另两个位置用于编码非数值字符) 。一个d 位数占用d 个列。因为卡片排序器一次只能查看一个列，要对n 张片上的d 位数进行排序就要有个排序算法。
直感上，大家可能觉得应该按最重要的一位排序，然后对每个盒子中的数递归地排序，最后把结果合并起来。不幸的是，为排序每一个盒子中的数，10个盒子中的9个必须先放在一边，这个过程产生了许多要加以记录的中间卡片堆。
与人们的直感相反，基数排序是首先按最不重要的一位数字排序来解决卡片排序问题的。同样，把各堆卡片收集成一迭，其中0号盒子中的在1号盒子中的前面，后者又在2号盒子中的前面，等等。然后对整个一迭卡片按次重要位排序，并把结果同样地合并起来。重复这个过程，直到对所有的d 位数字都进行了排序。所以，仅需要n 遍就可将一迭卡片排好序。图1说明了基数排序作“一迭”7个三位数的过程。第一列为输入，其余各列示出了对各个数位进行逐次排序后表的情形。垂直向上的箭头指示了当前要被加以排序的数位。
图1 基数排序作用于一个由7个3位数组成的表上的过程
关于这个算法很重要的一点就是按位排序要稳定。由卡片排序器所故的排序是稳定的，但操作员在把卡片从盒子里拿出来时不能改变他们的次序，即使某一盒子中所有卡片在给定列上的穿孔位置都相同。 在一台典型的顺序随机存取计算机上，有时采用基数排序来对有多重域关键字的记录进行排序。例如，假设我们想根据三个关键字处、月和日来对日期排序。对这个问题，可以用带有比较函数的排序算法来做。给定两个日期，先比较年份，如果相同，再比较月份，如果再相同，再比较日。这儿我们可以采用另一个方法，即用一种稳定的排序方法对所给信息进行三次排序：先对日，其次对月，再对年。
基数排序的代码是很简单的、下面的过程假设长度为n 的数组A 中的每个元素都有d 位数字，其中第1位是最低的，第d 位是最高位。
procedure Radix_Sort(var L:List;d:integer);
var
i:integer;
begin
1 for i:=1 to d do
2 使用一种稳定的排序方法来对数组L 按数字i 进行排序;
end;
基数排序的正确性可以通过对正在被排序的列进行归纳而加以证明。对本算法时间代价的分析要取决于选择哪种稳定的中间排序算法。当每位数字都界于l 到k 之间，且k 不太大时，可以选择计数排序。对n 个d 位数的每一遍处理的时间为O(n+k)，共有d 遍，故基数排序的总时间为θ(dn+kd)。当d 为常数，k=O(n)时，基数排序有线性运行时间。
某些计算机科学家倾向于把一个计算机字中所含位数看成是θ(lgn)。具体一点说，假设共有dlgn 位数字，d 为正常数。这样，如果待排序的每个数恰能容于一个计算机字内，我们就可以把它视为一个以n 为基数的d 位数。看一个例子：对一百万个64位数排序。通过把这些数当作是以216为基数的四位数，用基数排序四遍就可完成排序。这与一个典型的O(nlgn)比较排序相比要好得多，后者对每一个参加排序的数约要
lgn=20次操作。但有一点不理想，即采用计数排序作为中间稳定排序算法的基数排序版本不能够进行原地置换排序，而很多O(nlgn)比较排序算法却是可以的。因此，当内存比较紧张时，一般来说选择快速排序更合适些。
桶排序 Bin Sort
平均情况下桶排序以线性时间运行。像计数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1) 上。
桶排序的思想就是把区间[0，1) 划分成n 个相同大小的子区间，或称桶，然后将n 个输入数分布到各个桶中去。因为输入数均匀分布在[0，1) 上，所以一般不会有很多数落在 一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列 出来即可。
在桶排序算法的代码中，假设输入是个含n 个元素的数组A ，且每个元素满足0≤ A
桶排序的算法如下，其中floor(x)是地板函数，表示不超过x 的最大整数。
procedure Bin_Sort(var A:List);
begin
1 n:=length(A);
2 for i:=1 to n do
3 将A 插到表B[floor(n*A)]中;
4 for i:=0 to n-1 do
5 用插入排序对表B 进行排序;
6 将表B[0],B[1],...,B[n-1]按顺序合并;
end;
图1 Bin_Sort的操作
图1演示了桶排序作用于有10个数的输入数组上的操作过程。(a)输入数组A[1..10]。(b)在该算法的第5行后的有序表(桶) 数组B[0..9]。桶i 中存放了区间[i/10，(i+1)/10]上的值。排序输出由表B[O]、B[1]、... 、B[9]的按序并置构成。
要说明这个算法能证确地工作，看两个元素A 和A[j]。如果它们落在同一个桶中，则它们在输出序列中有着正确的相对次序，因为它们所在的桶是采用插入排序的。现假设它们落到不同的桶中，设分别为B[i']和B[j']。不失一般性，假设i'
我们有：
i'=floor(n*A)≥floor(n*A[j])=j'
得矛盾 (因为i'
现在来分析算法的运行时间。除第5行外，所有各行在最坏情况的时间都是O(n)。第5行中检查所有桶的时间是O(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的时间。
为分析插人排序的时间代价，设ni 为表示桶B 中元素个数的随机变量。因为插入排序以二次时间运行，故为排序桶B 中元素的期望时间为E[O(ni2)]=O(E[ni2])，对各个桶中的所有元素排序的总期望时间为：
(1)
为了求这个和式，要确定每个随机变量ni 的分布。我们共有n 个元素，n 个桶。某个元素落到桶B 的概率为l/n，因为每个桶对应于区间[0，1) 的l/n。这种情况与投球的例子很类似：有n 个球 (元素) 和n 个盒子 (桶) ，每次投球都是独立的，且以概率p=1/n落到任一桶中。这样，ni=k的概率就服从二项分布B(k;n,p)，其期望值为E[ni]=np=1，方差V[ni]=np(1-p)=1-1/n。对任意随机变量X ，有
:
(2)
将这个界用到(1)式上，得出桶排序中的插人排序的期望运行时间为O(n)。因而，整个桶排序的期望运行时间就是线性的。
在该演示程序中，线性表的元素类型为整型，桶的标号为整数，算法将值为i 的元素放入标号为i 的桶中，再按照桶的标号的顺序将元素依次取出，就得到了最终的排序结果。