最佳情况划分： T(n)=2T(n/2)+(n)=(nlgn)
常数比例划分： T(n)=T(an)+T((1-a)n)+(n)=(nlgn)
平均情况划分： 直觉：(nlgn) 差的划分可以吸收到好的划分中。
三、快速排序的随机化版本
1. 随机化版本的提出 2.在快速排序中使用随机选择策略
3 j r+1
4 while TRUE //三次循环就把前一个数组搞定了
5 do rep/后面小于主元
7
repeat i i+1
8
until A[i]≥x //前面的大于主元
9
if i<j
10
then exchange A[i] A[j]
11
算法设计与分析
谭守标 安徽大学 电子学院
2007.9
第六章 快速排序
快速排序算法 快速排序的随机化版本 程序演示及说明 算法性能分析（三种情况）
问题：
1、什么是分治法？ 2、什么是排序？ 3、用分治法解决排序问题的思想是什么？
一、快速排序算法的基本概念
1.算法的提出：由C.A.R.Hoare提出。 2.定义：快速排序(quick sort)又称分划交
RANDOMIZED-QUICKSORT(A,p,r)
1 if p<r
2 then q RANDOMIZED-PARTITION(A,p,r)
3
RANDOMIZED-QUICKSORT(A,p,q)
4
RANDOMIZED- QUICKSORT(A,q+1,r)
四、快速排序分析
最坏情况分析
n² -2(n-1)
c.合并：快速排序无需合并操作。
算法描述
快速排序算法:
QUICKSORT(A,p,r)
1 if p<r
2 then q PARTITION(A,p,r)
3
QUICKSORT(A,p,q)
4
QUICKSORT(A,q+1,r)
二、快速排序的分解、解决过程
1. 分解：调用PARTITION对数组A[p..r]进行划分。
else return j
划分的正确性
a.下标i和j不会指向数组A中区间[p..r]以 外的元素。
b.当PARTITION结束时，下标j不等于r。 c.当PARTITION结束时，A[p..j]中的每个
元素都小于等于A[j+1..r]中的每个元素。
性能分析
最坏情况划分： T(n)=T(n-1)+(n)
换排序。
3.其解决排序问题的基本思路：使用分 治法。
基本步骤：
a.分解：数组A[p..r]被划分为两个非空子数 组A[p..q]和A[q+1..r],使得A[p..q]的每一个 元素都小于等于A[q+1..r]的元素。
b.解决：通过递归调用快速排序对子数组 A[p..q]和A[q+1..r]进行排序。
PARTITION实例：
A[p..r]
53264137
i 主元
(a)
j
53264137
i
j
(b)
A[p..q] A[q+1..r]
33264157 33264157 33214657
i
j
(c)
i
j
(d)
return j i (e)
一次划分结束
PARTITION(A,p,r)
1 x A[p]
2 i p-1
分解方法：在待排序的数组A[p..r]中选择一个元素作为 分划元素，也称为主元(最简单的做法是选择数组的第一个 元素为主元)。 经过一趟划分操作将数组重新排列，将小于 主元的元素放在原数组的底部区域，把大于主元的元素放 在原数组的顶部区域。
示意图：
主元
PARTITION
53264137
33214657
底部区域
顶部区域
2.解决：通过递归调用快速排序对子数组 A[p..q]和A[q+1..r]排序，直到划分得到的子数 组中只有一个元素时，递归调用结束。
3.合并：快速排序经过一趟划分操作将数组分 解成两个子数组，且位于底部区域的元素均不 大于主元，位于顶部区域的元素均不小于主元， 所以，一旦两个子数组已经完成分别排序，整 个数组自然成为有序序列。
(n-1)²=
平均情况分析 两个假设：
（1）假设所有输入数据均不同； （2）假定每个排列出现是等概率的；
关于划分过程的分析 关于平均情况性态的一个递归式 解递归式 上述和式的紧确界
关于划分过程的分析
关于平均情况性态的一个递归式
解递归式
上述和式的紧确界
The End
Thank you!
在快速排序算法的每一步中，当数组 还没有被划分时，可将元素A[p]与A[p..r] 中随机选出的一个元素交换后再执行 PARTITION。
3.使用随机化版本的优点
随机化版本的算法
RANDOMIZED-PARTITION 1 i RANDOM(p,r) 2 exchange A[p] A[i] 3 return PARTITION(p,q,r)