§10.3.2快速排序（续） §10.3.2快速排序（续） 时间分析：主要耗费在partition.上。对长度为k的区 ②量好情况：每次划分所取的基准是当前区间中的 间划分，需比较keys共k-1次 “中值记录，划分后左、右子区间大数相等 ④最坏情况：每次划分都是基准恰为当前区间中关 设Cn)表示对长度为n的文件进行快速排序所需比 键字最小（或最大）的记录 较次数 划分结果是左子区间（或右子区间）为空，而另 显然C(n)≤n-1+2C(n/2) 一子区间长度仅比原区间小了1 /设n=2%,n-1是划分R1.n可的比较次数 这时须微-1次划分，第次划分开始时区间长度 C(n)≤n+2C(n/2) 为n-+1,需比较的次数为n-i ≤n+2n/2+2C(n/22)】=2n+4C(n/22)≤. c-2a-n=ma-/2=0时） <kn+2kC(n/2k)=nlgn+nC(1) 显然，当文件状态递增（减）有序时，正是如 =O(nlgn)//k=lgn 此。 §10.3.2快速排序（续） §10.4选择排序 ③平均情况：Tavg(n)≈1.39nlgn+O(n 尽管它的最坏情况0()，但就平均时间而言最快 竞示莞持装笔品秀韩学装 童改进 §10.4.1直接选择排序（简单选择） 为使划分较均匀，避免取当前区间最大最小元做基准 ·基本思想： 三者取中法：然后将它与当前区间第1个元素交换，仍可 第1慧，无序区为R[1.n),选量小者放在R[1],无序区变 使用上述Partition算法 为[2.nJ. ◆景好方法是产生一个j】之间的随机数 第越， 有序区为R[1.i-1],无序区为R.n可 K=random,j:lk∈[] 显然R[1.i-1].keys≤R.n.keys 交换R叮和R[K],然后使用Partition 选无序区中量小者R内，交换R和R的后使R[1.keys ≤R+1n].keys厂有序区长度加1，无序区长度减1 ■不稳定：请检查反例2,2,1] 。第n-1越之后，R[1.n-1.keys≤Rn.keys,结束 ■递归：要使用栈，平均深度0(lgn) §10.4.1直接选择排序（简单选择） §10.4.1直接选择排序（简单选择） ■算法 ■时间 void SelectSort(SeqList R){ ◆比较： int i,j,k; for(i=1;iKn;i++K/第魅排序，1≤i≤n-1 无论文件状态为何，第热排序中需比较n-i次（内循 k=i好 环次数) for (j=i+1;j<=n;j++) (2)ICm=Cmin 在当前无序区Rn中选key最小的记录R冈 ◆移动： if (R[].key<R[k].key)k=j; 状态正序：Mmin=0 f(k=iR可一Rk:∥可用RO做交换单元 0n) 状态逆序：每超交换1次，Mmax=3(n-1) 较少 ◆就地，不稳定，检验反例2,2,1]25 §10.3.2 快速排序（续） „ 时间分析：主要耗费在partition上。对长度为k的区 间划分，需比较keys共k-1次 ① 最坏情况：每次划分都是基准恰为当前区间中关 键字最小（或最大）的记录 划分结果是左子区间（或右子区间）为空，而另 一子区间长度仅比原区间小了1 这时须做n-1次划分，第i次划分开始时区间长度 为n-i+1，需比较的次数为n-i 显然，当文件状态递增（减）有序时，正是如 此。 1 2 max 1 ( ) ( 1) / 2 ( ) n i C n i nn On − = = −= − = ∑ 26 §10.3.2 快速排序（续） ② 最好情况：每次划分所取的基准是当前区间中的 “中值”记录，划分后左、右子区间大致相等。 设C(n)表示对长度为n的文件进行快速排序所需比 较次数 显然C(n) ≤n-1+2C(n/2) //设n=2k，n-1是划分R[1..n]的比较次数 C(n) ≤n+2C(n/2) ≤n+2[n/2+2C(n/22)] = 2n+4C(n/22) ≤… ≤kn+2kC(n/2k) = nlgn+nC(1) = O(nlgn) //k=lgn 27 §10.3.2 快速排序（续） ③ 平均情况：Tavg(n) ≈1.39nlgn+O(n) 尽管它的最坏情况O(n2)，但就平均时间而言最快 „ 改进 为使划分较均匀，避免取当前区间最大最小元做基准 ™ 三者取中法：然后将它与当前区间第1个元素交换，仍可 使用上述Partition算法 ™ 最好方法是产生一个R[i..j]之间的随机数 K=random(i,j); //k∈ [i,j] 交换R[i]和R[k]，然后使用Partition „ 不稳定：请检查反例[2, 2, 1] „ 递归： 要使用栈，平均深度O(lgn) 28 §10.4 选择排序 基本思想：每一趟从待排序的记录中选出最小key的 记录（简称最小元），放在已排好序的子区间最后 §10.4.1 直接选择排序（简单选择） „ 基本思想： ™ 第1趟，无序区为R[1..n]，选最小者放在R[1]，无序区变 为[2..n]. ™ 第i趟，有序区为R[1..i-1]，无序区为R[i..n] 显然R[1..i-1].keys≤R[i..n].keys 选无序区中最小者R[k]，交换R[i]和R[k]后使R[1..i].keys ≤R[i+1..n].keys //有序区长度加1，无序区长度减1 ™ 第n-1趟之后，R[1..n-1].keys ≤R[n].keys，结束 29 § 10.4.1 直接选择排序（简单选择） „ 算法 void SelectSort(SeqList R){ int i, j, k; for (i=1; i<n; i++){ //第i趟排序，1≤i ≤n-1 k = i; for (j=i+1; j<=n; j++) //在当前无序区R[i..n]中选key最小的记录R[k] if (R[j].key<R[k].key) k=j; if (k!=i) R[i]↔R[k]; //可用R[0]做交换单元 } } 30 § 10.4.1 直接选择排序（简单选择） „时间 ™比较： 无论文件状态为何，第i趟排序中需比较n-i次（内循 环次数） //Cmax=Cmin ™移动： 状态正序：Mmin=0 状态逆序：每趟交换1次，Mmax=3(n-1) ™就地，不稳定，检验反例[2, 2, 1] 1 2 1 ( ) ( 1) / 2 ( ) n i n i nn On − = ∑ −= − = }O(n), 较少