开发者社区> 问答> 正文

为什么快速排序是一个不稳定的排序法?

为什么快速排序是一个不稳定的排序法?简单的阐述一下他的稳定性!

展开
收起
知与谁同 2018-07-15 13:36:45 2352 0
2 条回答
写回答
取消 提交回答
  • 这个时候,玄酱是不是应该说点什么...
    在此先简单阐述一下快速排序的具体做法:设置需要排序序列第一个数字为关键字P(也叫枢轴),同时设置两个指针high和low,初始状态时,low指向P,high指向序列中最后一个数;
    首先从high所指位置起向前找第一个小于关键字P的数字,并与P相互交换位置;然后从low所指位置起向后搜索,找到第一个大于P的数字,并与P相互交换位置,重复这两部直至low=high为止,这就是一趟快速排序完成;但是到此不一定就完成了快速排序的排序工作,第一趟排序完成只是将序列中的数字分成三部分,P在中间部分,P之前的数字肯定比P小,P后面的那些数字都是比P大的,在分别对前后两部分进行快速排序即可。
    所谓排序的稳定性,就是指在排序过程中,在对a关键字排序后会不会改变其他关键字的顺序。
    自己都可以试试,在比较有相同关键字序列的情况下,稳定的排序会将较早出现的元素排在前面,而不会是后面。
    比如:对(49,38,49,20,97,76)排序,就是不稳定排序

    我们也是刚学了这个东西,希望我的理解和解释能帮你解决疑惑
    2019-07-17 22:49:39
    赞同 展开评论 打赏
  • 以Ai与Aj为例子

    快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],
    其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的
    j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,
    i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。
    交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的
    时候,很有可能把前面的元素的稳定性打乱,比如序列5 3 3 4 3 8 9 10 11,
    现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱
    ,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。
    2019-07-17 22:49:39
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载