《计算机算法设计与分析》课后练习07

文章列表

《计算机算法设计与分析》课后练习07

Author:龙箬
Computer Application Technology
Change the World with Data and Artificial Intelligence !
CSDN@weixin_43975035
我行及我道

//算法：用A(m)划分集合A(m:p-1)
procedure PARTITION(m,p)integer m,p,i; global A(m:p-1)v = A(m); i = m //A(m)是划分元素//looploop i = i+1 until A(i) ≥ v repeat //i由左向右移//loop p = p-1 until A(p) ≤ v repeat //i由右向左移//if (i<p) thencall INTERCHANGE(A(i), A(p))else exitendifrepeatA(m) = A(p);A(p) = v //划分元素在位置p//
end PARTITION

(1) 在上述算法 $P A RT I T I ON (m, p)$ 中，将 $i f (i < p)$ 改为 $i f (i \leq p)$ ，有何优缺点？
(2) 在数据集 $(5, 4, 3, 2, 5, 8, 9)$ 上执行这两个算法，看看他们在执行时有何不同。

解：
（1）优点：不改变所排序数据的稳定性
缺点：当 $i == p$ 时，原地置换 $A [i]$ 和 $A [p]$ ，并且多进入一轮循环，然后 $i > p$ 跳出循环，导致多进行一次比较及运算。

（2）当 $i f (i < p)$ 时
$5_1，4，3，2，5_2，8，9$
$5_2，4，3，2]，5_1，[8，9]$
$2，3，4]，5_2，5_1，[8，9]$
$2，[4，3]，5_2，5_1，[8，9]$
$2，[3]，4，5_2，5_1，[8，9]$
$2，3，4，5_2，5_1，[8，9]$
$2，3，4，5_2，5_1，8，[9]$
$2，3，4，5_2，5_1，8，9$

（2）当 $i f (i \leq p)$ 时
$5_1，4，3，2，5_2，8，9$
$2，4，3]，5_1，[5_2，8，9]$
$2，[4，3]，5_1，[5_2，8，9]$
$2，[3]，4，5_1，[5_2，8，9]$
$2，3，4，5_1，[5_2，8，9]$
$2，3，4，5_1，5_2，[8，9]$
$2，3，4，5_1，5_2，8，[9]$
$2，3，4，5_1，5_2，8，9$

参考致谢：
国科大马丙鹏老师《计算机算法设计与分析》

如有侵权，请联系侵删
需要本实验源数据及代码的小伙伴请联系QQ:2225872659

《计算机算法设计与分析》课后练习07

相关问题

公告