众所周知,
稳定性是描述排序算法的一种重要指标。
这是大多数地方对稳定性的定义:
假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。
但是,对于以下代码:
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
if(a[i]>a[j])
swap(a[i], a[j]);
很明显,冒泡排序是稳定的。
但是,如果把if语句改成 if (a[i]>=a[j]),那么两个相同值的相对位置不是会改变了吗? 难道一个“=”号就能使冒泡变得不稳定?
同理,快排等不稳定的算法,是不是也能通过加减“=”号变得稳定?
求助dalao解答,谢谢。