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