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

发布网友 发布时间：2022-04-24 19:42

我来回答

共5个回答

热心网友 时间：2023-10-09 00:08

以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]交换的时刻。

参考资料：http://hi.baidu.com/lovebenxiaohai/blog/item/20b6b6349fd2a4b0d1a2d32e.html

热心网友 时间：2023-10-09 00:09

在此先简单阐述一下快速排序的具体做法：设置需要排序序列第一个数字为关键字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）排序，就是不稳定排序

我们也是刚学了这个东西，希望我的理解和解释能帮你解决疑惑

热心网友 时间：2023-10-09 00:09

一组数据用快速排序究竟用多少次能排完？这是不确定的。在最坏的情况下比其它的排序算法还要慢，当然这种几率出现的情况很少。因此说它不稳定，不是说它排序的结果不稳定，而是时间复杂度不稳定。

热心网友 时间：2023-10-09 00:10

不稳定只是说在排序没有完成之前（假设说：降序排列）会暂时的出现小的排在前面的情况
没有排完就中断，不能保证一部分是有序的，所以称为不稳定
大学教科书:
数据结构里面写的，不信去查

热心网友 时间：2023-10-09 00:10

用AAAAAB举例（A>B），以B为标准,第一个A到B后面去了，不稳定了