关于快速排序的不稳定性说明

不稳定性的含义：不稳定性是指在原始序列中相等的如果元素按照a1 a2 a3…的顺序排列时，排序之后相等元素的原相对位置改变，比如a3跑到a1前面去了

快速排序过程中：在j运动的时候，j的最终落点要么在i左边，要么在i右边，不会和i落在同样的位置，由i和j的性质就可以得到这个结论，如果落在i的右边，那就是没到最后一步，循环继续进行。现在为了讨论不稳定性，我们只讨论最后一步：j落在i左边的情况

看这个序列：
6 5 5 2 3 2 9 7 7
基准元素为6，在j可以运动的时候，i指向9，j这个时候从7开始想左走，跳过9，落在2上，这个时候就会有一个疑问，那如果9左边那个元素比6还大呢？由于i<=j的限制，j没法向左走呢？有意思了…那么如果有这种情况，你以为是i耽误的你？想多了，i既然能跳过9左边的一堆元素，就说明i根本不care那些，也就是i能走过来，证明i最后的落点位置左边的所有元素都比基准位置小，而i的左1元素就是j的最终归宿，即j最终要和基准元素交换的这个一定比基准小，问题又来了，小，小多少？这个小元素设为a*,如果在基准和j落点之间还有一个a，那a*不就跑到a前面去了？什么叫后来居上
总结：快排的不稳定是来自于最后的那一次交换(j指向元素与基准元素的交换）而不是在扫描的过程中控制等号的问题

后记：本文的初衷是为了证明快速排序具有稳定性的
/微笑

附快速排序代码：

void kuaipai(int *p,int start,int end)
{if(start==end)return ;if(start==end-1)return ;int R=p[start];int i=start+1;int j=end-1;while(i<=j){while(p[i]<R&&i<=j){i++;}//  if(p[i]//    i++;//这里的i可能被限制,就是i和j指向同一个位置有两种可能，一个是受iwhile(p[j]>=R&&i<=j){j--;}if(i<=j){int temp=p[i];p[i]=p[j];p[j]=temp;}}p[start]=p[j];p[j]=R;kuaipai(p,start,j);kuaipai(p,j+1,end);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！