算法导论中文课件讲-快速排序.pptxVIP

1SimpleReview堆排序堆MAX-HEAPIFYBUILD-MAX-HEAPHEAPSORT优先级队列MAXIMUM(S)EXTRACT-MAX(S)INCREASE-KEY(S,x,k)INSERT(S,x)应用

算法分析与设计

快速排序(Ch7)

3算法分析与设计快速排序内容:快速排序随机快排

4随机算法随机算法:随机算法是算法本身包含了随机数生成器的算法。[algorithmsthatflipcoins]随机做决定的算法，即--可生成在{1,r}范围内的随机数x--基于x的值做决定--应用快排

5猜硬币游戏如果你总是猜某个固定的杯子，对手则总会将硬币放入另一个杯子，因此期望的回报为$0如果每次随机选择一个杯子，则期望回报为$0.5随机算法:[algorithmsthatflipcoins]

6随机算法《随机算法》是高等教育出版社出版的图书，作者是莫特瓦尼、拉格哈文。主要介绍了算法本身包含了随机数生成器的算法。每一章集中在随机算法应用的一个重要领域，如数据结构、几何算法、图算法、数论、计数、并行算法及在线算法等。

7随机算法两种基本类型:--LasVegas：通常是高效的(但有时是慢的)--MonteCarlo：通常是正确的(但有时产生的结果不可用)拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。求得正确解的概率也依赖于算法所用的时间。蒙特·卡罗方法（MonteCarlomethod），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。可求问题的精确解，但这个解不一定是正确的，求得正确解的概率也依赖于算法所用的时间。注意：结果的可能性取决于算法执行过程中产生的随机数！(而不是随机选择的问题输入)

8快速排序高效的排序算法--1962年由C.A.R.Hoare提出--分治算法--原地排序(与插入排序类似，与归并排序不同)--非常实用(需要精心实现)--可认为是一个随机拉斯维加斯算法的实例--最坏情况下的计算时间:Θ(n2)--平均计算时间:Θ(nlogn)--Θ(nlogn)量级下的常数系数比较小

9快速排序快速排序由C.A.R.Hoare（东尼霍尔，CharlesAntonyRichardHoare）在1960年提出，之后又有许多人做了进一步的优化。东尼霍尔1962年在ComputerJournal发表的论文“Quicksort”以及《算法导论》的第七章。快速排序算法仅仅是东尼霍尔在计算机领域才能的第一次显露，后来他受到了老板的赏识和重用，公司希望他为新机器设计一个新的高级语言。当时还没有PASCAL或者C语言。后来东尼霍尔参加了由EdsgerWybeDijkstra（1972年图灵奖得主）举办的“ALGOL60”培训班，他觉得自己与其没有把握去设计一个新的语言，还不如对现有的“ALGOL60”进行改进，使之能在公司的新机器上使用。于是便设计了“ALGOL60”的一个子集版本。这个版本在执行效率和可靠性上都在当时“ALGOL60”的各种版本中首屈一指，因此东尼霍尔受到了国际学术界的重视。后来他在“ALGOLX”的设计中还发明了大家熟知的“case”语句，后来也被各种高级语言广泛采用，比如PASCAL、C、Java语言等等。他在1980年获得了图灵奖。

10分治要对n个元素的数组完成快排：--分:将原数组围绕某划分元素x划分为两个子数组，使得前面子数组中元素≤x≤后面子数组中元素--治:递归对子数组进行排序--合并:不需任何工作.关键:线性时间的划分过程

11分治初始调用Quicksort(A,1,n)

12划分过程A[p,…,i]:≤划分元素A[i+1,…,j-1]:划分元素A[j…r]:未检查A[r]:划分元素

13划分示例对于某数组的划分过程。图中浅灰色部分元素均小于等于x(划分元素)，深灰色部分元素均大于x。返回最终位置i+1

14快排分析假设所有元素均不同。实际应用中，如果输入元素可能有相同值，则存在比上述划分算法更好的划分过程。令T(n)=排序n个元素的数组在最坏情况下的计算时间。

15快排的最坏情况输入数据是有序或逆序的。基于最小或最大元素进行划分