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)是划分元素//
	loop
		loop i = i+1 until A(i) ≥ v repeat //i由左向右移//
		loop p = p-1 until A(p) ≤ v repeat //i由右向左移//
		if (i<p) then
			call INTERCHANGE(A(i), A(p))
		else exit
		endif
	repeat
	A(m) = A(p);
	A(p) = v //划分元素在位置p//
end PARTITION

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

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

（2）当 $if(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）当 $if(i\le 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