最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第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[i]>L[i+1] then begin
6 swap(L[i],L[i+1]); 7 t:=i; end; 8 up:=t;
9 for i:=up downto low+1 do 10 if L[i]< L[i-1] then begin
11 swap(L[i],L[i-1]); 12 t:=i; end; 13 low:=t; end; end;
算法利用两个变量low和up记录排序的区域L[low..up]，用变量t 记录最近一次交换纪录的位置，4-7行从前向后扫描，9-12行从后向前扫描，每次扫描以后利用t所记录的最后一次交换记录的位置，并不断地缩小需要排序的区间，直到该区间只剩下一个元素。 直观上来看，双向冒泡法先让重的气泡沉到底下，然后让轻的气泡浮上来，然后再让较大气泡沉下去，让较轻气泡浮上来，依次反复，直到排序结束。 [参考算法]：Pascal语言表述的冒泡排序算法 procedure sort; var i,j,k:integer; begin
for i:=n downto 1 do for j:=1 to i-1 do
if a[j] >a[i] then begin
a[0]:=a[i];a[i]:=a[j];a[j]:=a[0]; end; end;
选择排序 Selection Sort
选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过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 3 4 5
s:=i;
for j:=i+1 to Last(L) do
if L[j]< L[s] then s:=j; //记录L[i..n]中最小元素的位置 swap(L[i],L[s]); //交换L[i],L[s]
end; end;
算法Selection_Sort中里面的一个for循环需要进行n-i次比较，所以整个算法需要
次比较，显而易见，算法Selection_Sort中共调用了n-1次swap过程，即进行了n-1次交换。因而，算法Selection_Sort的时间复杂性f(n)=O(n2)。 [参考算法]：Pascal语言表述的选择排序算法 procedure sort; var i,j,k:integer; begin
for i:=1 to n-1 do begin k:=i;
for j:=i+1 to n do if a[j]< a[k] then k:=j;
{找出a[I]..a[n]中最小的数与a[I]作交换} if k< >i then begin
a[0]:=a[k];a[k]:=a[i];a[i]:=a[0]; end; end; end;
思考与练习：完成并提交作业 下面是一选择算法的程序段： begin
1 for i:=1 to n-1 do begin 2 min:=i;
3 for j:= ____ to n do
4 if L[j]< L[s] then s:=j; //选出最小元素的位置min 5 if _____ then swap(L[i],L[s]); //在什么条件下才交换记录?
end; end;
(1)在____中填上正确的语句或表达式；
(2)若待排数据是3，1，2，4，5，整个算法需要进行多少次比较？多少次交换？
插入排序 Insertion Sort
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与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[i]是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L[i]放入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[i]; 3 j:=i;
4 while (j<>First(L))and(L[j-1]< v) do //循环找到插入点 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要比较O(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^.next<>nil do begin
4 tmp:=i^.next; //tmp指向L[i]的下一个位置 5 j:=L;
6 while (j<>i)and(tmp^.data>=j^.next^.data) do //从前向后找到tmp的位置，tmp应该插在j后面 7 j:=j^.next;
8 if j<>i 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;
上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。 插入法虽然在最坏情况下复杂性为O(n2)，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。
这里是一个用Java Applet制作的插入排序演示程序。 [参考算法]：Pascal语言表述的插入排序算法
procedure insert_sort(k,m:word); {k为当前要插入的数，m为插入位置的指针}
var i:word; p:0..1; begin p:=0;
for i:=m downto 1 do if k=a[i] then exit; repeat
If k >a[m] then begin a[m+1]:=k; p:=1; end else begin
a[m+1]:=a[m]; dec(m); end; until p=1; end;{insert_sort} * 主程序中为： a[0]:=0;
for I:=1 to n do insert_sort(b[I],I-1);
思考与练习：完成并提交作业
试对前述的插入排序、冒泡排序、选择排序进行速度比较。
快速排序 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]中任一元素的值。具体可通过这样的途径实现：在序列L[p..r]中选择数据元素L[q]，经比较和移动后，L[q]将处于L[p..r]中间的适当位置，使得数据元素L[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<=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，该函数主要实现以下两个功能： 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 以上算法的一个执行实例如图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. 2. 3. 4. 选择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语言实现的。 [参考算法]：Pascal语言表述的快速排序算法 procedure sort(l,r:integer); var i,j,mid:integer; begin i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数} repeat while a[i]< mid do inc(i); {在左半部分寻找比中间数大的数} while mid< a[j] do dec(j); {在右半部分寻找比中间数小的数} if i< =j then begin {若找到一组与排序目标不一致的数对则交换它们} swap(a[i],a[j]); inc(i);dec(j); {继续找} end; until i >j; if l< j then sort(l,j); {若未到两个数的边界，则递归搜索左右区间} if i< r then sort(i,r); end;{sort} 思考与练习：完成并提交作业 1、仔细阅读下面的Pascal程序，并回答有关问题。 procedure PX(var A:array[1..500] of integer,n:integer); var i,j,x:integer;b:boolean; begin b:=true;i:=1; while (i < n) and b do begin b:=false; for j:=1 to ______ do if _____ then begin x:=A[j];A[j]:=A[j+1];A[j+1]:=x; ______ end; i:=i+1; end; end; (1)在_____中填上正确的语句或表达式； (2)该过程使用的是什么排序方式? (3)当数组A的元素初始时已为递增排列时，该过程运行时会进行几次比较？几次交换？ (4)若A是递减排列，比较和交换次数又是多少？ 2、给出n个学生的考试成绩表，每个数据记录由学生的姓名和成绩组成，试设计一个算法： (1)按成绩高低次序,输出每个学生在考试中获得的名次,成绩相同的名次相同; (2)按名次输出每个学生的姓名和成绩。 下面的内容供参考—— 性能分析 下面我们就最好情况，最坏情况和平均情况对快速排序算法的性能作一点分析。 注意：这里为方便起见，我们假设算法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 因为在[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)。 思考与练习见本页中上部 因篇幅问题不能全部显示，请点此查看更多更全内容