4173人阅读
趁空闲时间，我决定把所学过的排序算法实现并总结下，以便温故知新。
将提到的排序算法有：冒泡排序，快速排序，选择排序，堆排序，插入排序，合并排序，希尔排序，计数排序，基数排序，桶排序。
所有排序结果都默认为排成从前往后升序。程序都在VS2008中运行成功。
交换排序：
1，冒泡排序：
冒泡排序是最简单的排序，是刚学c语言时最早接触到的一个算法。
他的思想就是，对待排序元素的关键字从后往前进行多遍扫描，遇到相邻两个关键字次序与排序规则不符时，就将这两个元素进行交换。这样关键字较小的那个元素就像一个泡泡一样，从最后面冒到最前面来。
不多说了，直接写出代码：
#include &iostream&
void BubbleSort(int a[], int n) {
for (int i = 0; i & i++) //遍历n次
for (int j = n-1; j & j--) {
if (a[j] & a[j-1]) { //当前比较前面键值，使当前总为最小的
swap(a[j-1], a[j]);//交换
int main()
int num[6] = {23,45,13,2,99,78};
cout && &冒泡排序前：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
BubbleSort(num, 6);
cout && &冒泡排序后：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
这样的代码是效率比较低的，下面是改进后的冒泡排序：
void BubbleSort(int a[], int n) {
int i, j, flag = 0;//使用flag标记在某次遍历时出现了交换元素
for (i = 0; i & i++) {
for (j = n-1; j & j--) {
if (a[j-1] & a[j]) {
swap(a[j], a[j-1]);
if (flag == 0)//没有出现交换的情况说明已经是完成了排序
}冒泡的时间复杂度为O(n2)，空间复杂度O(1)。稳定。
2，快速排序：
快速排序采用了分治算法策略，它是冒泡排序的一种改进。
基本思路是：把待排列的数据分为两个子列，从数列中挑出一个数作为基准，遍历其他数据，把小于它的放前面，大的放在基准的后面。之后，通过递归，将各个子序列划分为更小的序列，直到把小于基准值元素的子数列和大于基准值元素的字数列排序。
快速排序示意图：
它的示例代码如下：
#include &iostream&
//拆分为两个子列
int Partition(int a[], int left, int right) {
int base = a[left];
while (left & right) {
while (left & right && a[right]&base) //从右往左找出第一个比基准小的数据
a[left] = a[right]; //将这个数放到基准的左边
while (left & right && a[left]&base) //从左往右找出第一个比基准大的数据
a[right] = a[left]; //放到右边
//返回基准的位置
QuickSort(int a[], int left, int right) {
if (left & right) {
i = Partition(a, left, right);
QuickSort(a, left, i-1);
QuickSort(a, i+1, right);
int main()
int num[6] = {23,45,13,2,99,78};
cout && &排序前：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
QuickSort(num, 0, 5);
cout && &排序后：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
快速排序时间复杂度为O(nlog2n)，空间复杂度O(nlog2n)，但是不稳定。快速排序平时用得比较多，比如algorithm里面的sort就是快速排序。
&#include &algorithm&
void sort( iterator start, iterator end );
void sort( iterator start, iterator end, StrictWeakOrdering cmp );
但是它不适合对链式结构进行排序。
选择排序：
基本思想就是每次遍历，选出键值最小的数据，依次放在已排序好的数列后面，直到全部记录排完为止。
1，直接选择排序：
对待排序的序列，选出关键字最小的数据，将它和第一个位置的数据交换，接着，选出关键字次小的数据，将它与第二个位置上的数据交换。以此类推，直到完成整个过程。
所以如果有n个数据，那个需要遍历n-1遍。其实现代码如下：
#include &iostream&
void SelectSort(int a[], int n) {
for (i = 0; i & n-1; ++i) {
for (j = i+1; j & ++j) {
if (a[small] & a[j]) small =
if (small != i)
swap(a[small], a[i]);
int main()
int num[6] = {23,45,13,2,99,78};
cout && &排序前：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
SelectSort(num, 6);
cout && &排序后：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
}直接选择排序的时间复杂度为O(n2)。同样适合对链式结构进行排序，只不过需要修改实现代码。
2，树形选择排序：
树形选择排序也称为竞标赛排序，基本思想是：两两比较，选出第一个最小值，将原来的叶子节点设置为∞，进行同样的两两比较，既可选出第二个最小值，如此往复。缺点：占用的辅助存储空间较多，和“∞”进行多余的比较等。为了弥补这些缺点J.willioms提出了另一种形式的选择排序——堆排序。它的时间复杂度为O(nlog2n)。
& 首先将待排序记录两两分组，将每组的最小值设置为他们的父结点，把所有这些筛选出来的父结点再两两分组，选出每组的最小值并设置为这组的父结点。一层一层筛选，直到选出根结点，就是最小值了，然后将其对应的叶结点设置为∞。
中心思想类似于锦标赛，先分组然后层层选拨，将每次选拨出来的根结点的值单独记录下来。然后把之前选拨出来的值，设置为∞（无穷大）。那么再次比较时，之前选拨出来的值已经变成无穷大了，自然会被忽略。但有一个问题就是每一次选拨都会重新进行比较。和“∞”进行的多余的比较太多，而且占用过多的辅助存储空间。借助树形选择排序的思想，理解堆排序就会更容易一些。
时间复杂度为O (n log2n)，空间复杂度O(n)。是稳定排序 。
3，堆排序：
堆排序就是利用堆的特性排序，堆是一个二叉树，如果从上至下，从左至右按照节点的关键字大小顺序排列节点，那就是堆排序。堆排序的排序过程如下图所示：
其排序示例实现如下：
#include &iostream&
//用数组二叉树
void HeapAdjust(int a[], int s, int n)//构成堆
while(2*s + 1 & n) //第s个结点有右子树
j=2*s + 1 ;
if((j+1) & n)
if(a[j] & a[j+1])//右左子树小于右子树，则需要比较右子树
j++; //序号增加1，指向右子树
if(a[s] & a[j])//比较s与j为序号的数据
swap(a[s], a[j]);
s =//堆被破坏，需要重新调整
else //比较左右孩子均大则堆未破坏，不再需要调整
void HeapSort(int a[],int n)//堆排序
for(i = n/2 - 1; i &= 0; i--)
//将a[0,n-1]建成大根堆
HeapAdjust(a, i, n);
for(i = n-1; i & 0; i--)
swap(a[0], a[i]);
HeapAdjust(a, 0, i);
//将a[0]至a[i]重新调整为堆
int main()
int num[6] = {23,45,13,2,99,78};
cout && &排序前：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
HeapSort(num, 6);
cout && &排序后：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
}堆排序的时间复杂度为O(nlog2n)，空间复杂度为O(1)。不稳定。
插入排序：
插入排序基本思想，每次将一个待排序的数据按照其关键字的大小插入到前面已经排序好的数据中的适当位置，直到全部数据排序完成。
1，直接插入排序
直接插入排序是一种简单直观的排序算法，它的工作原理是通过建有序序列，对于没有排序的数据，在已排序序列中从后往前扫描，找到相应位置，并插入。故，如果是数组这样的连续空间的数据序列，那就每次插入都要将其位置的后面数据都向后移动。
其示例实现为：
#include &iostream&
void InsertSort(int a[], int n) {
for (i = 1; i & ++i) {
temp = a[i]; //先保存当前值
for (j = i-1; j &= 0 && temp & a[j]; --j) //从后往前移，直到找到适合位置
a[j+1] = a[j]; //往后移一位，腾出位置
a[j+1] = //将值放入已找出的适当位置
int main()
int num[6] = {23,45,13,2,99,78};
cout && &排序前：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
InsertSort(num, 6);
cout && &排序后：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
这样的直接插入排序空间复杂度O(1)，但是时间复杂度为O(n2)
还有几种对直接插入排序改进的几种排序：折半插入排序，2-路插入排序，表插入排序。
2，希尔排序
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
它的具体做法是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2&d1重复上述的分组和排序，直至所取的增量dt=1(dt&dt-l&…&d2&d1)，即所有记录放在同一组中进行直接插入排序为止。
具体示例代码：
#include &iostream&
void ShellSort(int a[], int n) {
int d, i, j,
d = n/2; //分成n/2组
while (d &= 1) {
for (i = i & ++i) { //对每组进行直接插入排序
temp = a[i];
while (j &= 0 && a[j] & x) {
a[j+d] = a[j];
int main()
int num[6] = {23,45,13,2,99,78};
cout && &排序前：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
ShellSort()
cout && &排序后：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
希尔排序时间复杂度为O(n4/3)，空间复杂度为O(1)，但是不适合在链表结构上使用。
合并排序：
&合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。
其具体是的实现实例：
#include &iostream&
//2-路合并
void Merge(int a[], int r[], int left, int mid, int n) {//a[]归并到r[]
int s1 = left, s2 = mid+1, s3 =
while (s1 &= mid && s2 &= n)//比较较小的数据填充到a[]
if (a[s1] &= a[s2])
r[s3++] = a[s1++];
r[s3++] = a[s2++];
while (s1 &= mid) r[s3++] = a[s1++];//将未填充的数补全
while (s2 &= n) r[s3++] = a[s2++];//将未填充的数补全
//2-路归并排序
void MergePass(int a[], int r[], int n, int len) {
int beg = 0,
while (beg + len & n) {
end = beg + 2*len - 1;
if (end &= n)//最后一个可能少于len个
end = n - 1;
Merge(a, r, beg, beg+len-1, end);//合并
beg = end + 1;//提供给下次开始
if (beg & n)
while (beg & n) {
r[beg] = a[beg];
void MergeSort(int a[], int n) {
int len = 1;//当前进行归并有序数列的长度
int f = 0;
int *p = (int *)malloc(sizeof(int)*n);
while(len & n) {
if (f) MergePass(p, a, n, len);//交替归并到p和a
else MergePass(a, p, n, len);
if (f) //排序后是归并到p的情况，复制回到a
for (f = 0; f & f++)
a[f] = p[f];
int main()
int num[6] = {23,45,13,2,99,78};
cout && &排序前：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
MergeSort(num, 6);
cout && &排序后：& &&
for (int i = 0; i & 6; i++) {
cout && num[i] && & &;
}2-路归并排序的时间复杂度为O(nlog2n)，空间复杂度为O(n)
分配排序：
1，桶排序：
假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] &1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。
他的排序过程如图：
桶排序只是用于关键字取值范围较小的情况，否则会因为所需箱子的数目太多而导致资源的浪费。这种排序的使用价值不大，他一般用于基数排序的一个中间过程。
2，基数排序：
基数排序是桶排序的一种改进和推广。它的基本思想是，先设立r个队列，队列编号分别为0~r-1，（r为关键字的基数），然后按照下面的规则对关键字进行“分配”和“收集”。
1，&按照最低有效位的值，把n个关键字分配到上述的r个队列里，然后从小到达将各队列中关键字收集起来。
2，&再按低次有效位的值把刚刚收集起来的关键字分配到r个队列中，重复收集工作。
3，&重复上述分配和收集工作，直到最高的有效位。（也就是说，如果数位为d，则需要重复进行d次。d由所有元素中最长的一个元素的位数计量。）
图示如下：
上图过程，就是先按个位分配然后收集，再按十位，百位分配和收集，最后就得出排序结果。
在C++中可以使用库函数lexicongraphical_compare（）进行字典次序比较。
每一趟分配的时间是O(n)，所以总时间的开销为O(d(n+r)) = O(n)，通常d,r为常数。空间负复杂度为O(n+r)。基数排序使用于采用链式结构存储结构的排序。
3，计数排序：
&计数排序是一个类似于桶排序的排序算法，其优势是对已知数量范围的数组进行排序。它创建一个长度为这个数据范围的数组C，C中每个元素记录要排序数组中对应记录的出现个数。这个算法于1954年由
Harold H. Seward 提出。
计数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。
#include &iostream&
//n为个数，k为最大值,b为输出
void CountingSort(int a[], int b[], int n, int k)
int* c = new int[k+1];
memset(c, 0, (k+1) * sizeof(int));
for (int j = 0; j & j++) c[a[j]]++;//保存每个下标的值的个数
for (int j = 1; j &= j++) c[j] += c[j - 1];//从前到后累计的位置
for (int j = n - 1; j &= 0; j--)
b[c[a[j]] - 1] = a[j];
c[a[j]]--;
delete []c;
int main()
int num[6] = {23,45,13,2,99,78};
int out[6];
cout && &排序前：& &&
int max = 0;
for (int i = 0; i & 6; i++) {
if (max & num[i]) max = num[i];
cout && num[i] && & &;
CountingSort(num, out, 6, max);
cout && &排序后：& &&
for (int i = 0; i & 6; i++) {
cout && out[i] && & &;
可以看出计数排序很快，O(n)的时间复杂度，但是我们平时还是用的很少，是因为它的缺陷：需要一个至少等于待排序数组取值范围的缓冲区。
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：223026次
积分：3285
积分：3285
排名：第4861名
原创：109篇
评论：46条
(2)(1)(3)(4)(8)(19)(4)(3)(4)(8)(56)(6)算法与数据结构――快速排序 Quick Sort
快速排序 Quick Sort
我们已经知道，。如果我们能设计一个需要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:var L:List);
if r-p&=e then Insertion_Sort(L,p,r)
//若L[p..r]足够小则直接对L[p..r]进行插入排序
else begin
q:=partition(p,r,L);
//将L[p..r]分解为L[p..q]和L[q+1..r]两部分
Quick_Sort(p,q,L);
//递归排序L[p..q]
Quick_Sort(q+1,r,L);//递归排序L[q+1..r]
对线性表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，否则该过程会无限递归下去，永远不能结束。因此下面在里加了限制条件，避免q=r情况的出现。
算法Quick_Sort中调用了一个函数partition，该函数主要实现以下两个功能：
在L[p..r]中选择一个支点元素
对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:var L:List):
pivot:ElementT
pivot:=Select_Pivot(p,r,L); //在L[p..r]中选择一个支点元素pivot
while true do
repeat j:=j-1 until L[j]&=
//移动左指针，注意这里不能用while循环
repeat i:=i+1 until L[i]&=
//移动右指针，注意这里不能用while循环
if i& j then swap(L[i],L[j])
//交换L[i]和L[j]
else if j&&r then return j
//返回j的值作为分割点
else return j-1;
//返回j前一位置作为分割点
该算法的实现很精巧。其中，有一些细节需要注意。例如，算法中的位置i和j不会超出A[p..r]的位置界，并且该算法的循环不会出现死循环，如果将两个repeat语句换为while则要注意当L[i]=L[j]=pivot且i&j时i和j的值都不再变化，会出现死循环。
另外，最后一个if..then..语句很重要，因为如果pivot取的不好，使得Partition结束时j正好等于r，则如前所述，会无限递归下去；因此必须判断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的方法。
选择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:
&&&& 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); {继续找}
&&&& until i &j;
&&&& if l& j then sort(l,j);&
&&&& {若未到两个数的边界，则递归搜索左右区间}
&&&& if i& r then sort(i,r);
思考与练习：
　　1、仔细阅读下面的Pascal程序，并回答有关问题。
procedure PX(var A:array[1..500] of integer,n:integer);
var i,j,x:b:
& b:=i:=1;
& while (i & n) and b do
for j:=1 to ______ do
& if _____ then
x:=A[j];A[j]:=A[j+1];A[j+1]:=x;&
(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)&&&&&&&&&&&&
用迭代法可以解出上式的解为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&n，总有T(k)≤ck2 ，其中c为常数；显然当k=1时是成立的。
将归纳假设代入(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& 快速排序法最佳情况下执行过程的递归树
由于快速排序法也是，所以如果每次划分过程产生的区间大小都为n/2，则运行时间θ(nlogn)就是最好情况运行时间。
但是，是否一定要每次平均划分才能达到最好情况呢？要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分，乍一看该划分很不对称。我们可以得到递归式：
T(n)=T(n/10)+T(9n/10)+θ(n) , T(1)=θ(1)&&&&&&&&
这个递归式对应的递归树如下图所示：
图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。
图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个元素的数组加以随机排列的算法。这种修改不改变算法的最坏情况运行时间，但它却使得运行时间能够独立于输入数据已排序的情况。
另一种随机化策略是：利用前文介绍的，即随机地在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]中最小的元素，则的循环结束时指针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个元素的概率为
把这两种情况综合起来，我们的结论为：划分的低区的大小为1的概率为2/n，低区大小为i的概率为1/n，i=2,3,..n-1。
现在让我们来对Quick_Sort的期望运行时间建立一个递归式。设T(n)表示排序含n个元素的表所需的平均时间，则：
其中T(1)=θ(1)。
q的分布基本上是均匀的，但是q=1的可能性是其他值的两倍。根据前面作的有：
T(1)=θ(1),T(n-1)=θ(n2)，所以
这可被(5)式中的θ(n)所吸收，所以(5)式可简化为：
&&&&&&&&&&
注意对k=1,2,..,n-1，和式中每一项T(k)为T(q)和T(n-q)的机会各有一次，把这两项迭起来有：
&&&&&&&&&&&&&&&&&&&&&&&
我们用来解上述递归方程。归纳假设T(n)≤a*nlogn+b，其中a&0,b&0为待定常数。可以选择足够大的a,b使anlogn+b&T(1)，对于n&1有：
下面我们来确定和式
&&&&&&&&&&&&&&&&&&&
因为和式中每一项至多是nlogn，则有界：
这是个比较紧的界，但是对于解递归式（8）来说还不够强。为解该递归式，我们希望有界：
为了得到这个界，可以将和式(9)分解为两部分，这时有：
等号右边的第一个和式中的logk可由log(n/2)=logn-1从上方限界。第二个和式中的logk可由logn从上方限界，这样，
对于n≥2成立。即:
将(10)代入(8）式得：
&&&&& （11）
因为我们可以选择足够大的a使a*n/4能够决定θ(n)+b，所以快速排序的平均运行时间为θ(nlogn)。
思考与练习见本页中上部