随机快速排序的期望时间： ·定义随机变量X: 口任意给定一个随机待排序列σ，（σ）表示对σ进行排序时进行的比较次 数 ■关于QS中的“比较”的两个事实： 口任何两个元素之间最多比较1次。 问题9：为什台？ ■比较只发生在pivot:和其它元素之间 口如果将A中元素按照大小重命名为z1,z2,…,Z,定义z列为{2z+1,…,z, 则z和z;进行比较iffz;或者z在z到中首先被选为pivot随机快速排序的期望时间： ◼ 定义随机变量X： ❑ 任意给定一个随机待排序列σ，X(σ)表示对σ进行排序时进行的比较次 数 ◼ 关于QS中的“比较”的两个事实： ❑ 任何两个元素之间最多比较1次。 ◼ 比较只发生在pivot和其它元素之间 ❑ 如果将A中元素按照大小重命名为z1 ,z2 ,…,zn ,定义zij为{zi ,zi+1,…,zj }, 则zi和zj进行比较 iff zi或者zj在zij中首先被选为pivot