稳定排序和非稳定排序那些事-稳定排序讲解

待排序的元素序列中可能存在两个或以上关键字相等的元素。若排序前Ri位于Rj前（i<j,Ri=Rj），若排序后Ri依然Rj位于前面，则称排序的方法稳定的，即：稳定排序，否则为非稳定排序。

例如：序列5、3、2、3、5

经过上述排序后，a[0]和a[4]的相对位置不变，即a[0]排序后还是位于a[4]前，a[1]和a[3]同理，那么就是稳定排序。如果有任意一对相同的元素在排序后相对位置发生了变化，则是非稳定排序。

二、常用排序算法的稳定性和复杂度

    上述排序算法的稳定性以及复杂度需要熟记，经常在选择题和填空题中出现，还需要理解各排序算法的排序原理，有的题目会要求对序列进行排序，例如：北京工业大学2017年考研真题第三大题，第4小题。

北京工业大学2014年硕士研究生入学考试试题-895

第一大题第5小题：

如果需要在O(nlog2n)的时间复杂度内完成对含有n个记录的关键字序列进行稳定排序，可以选择的排序算法是（）

A.快速排序    B. 堆排序    C. 归并排序   D. 直接插入排序

【解题思路】

本题是对时间复杂度和稳定性的考查，这两点是考研经常考到的，需要对所有排序算法的时间复杂度和稳定性有所掌握。首先从时间复杂度上来看，排除D，然后从稳定性上来看，排除A和B，只有C是满足的时间复杂度，且是稳定排序，故选C。 

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬