这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判
别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不
是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据
结构书上哪些是稳定的,哪些不是稳定的,做起来应该可以轻松搞
定。本文是针对老是记不住这个或者想真正明白到底为什么是稳定
或者不稳定的人准备的。
首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排
序前 2 个相等的数其在序列的前后位置顺序和排序后它们两个的前
后位置顺序相同。在简单形式化一下,如果 Ai = Aj, Ai 原来在位置
前,排序后 Ai 还是要在 Aj 位置前。
稳定排序: 待排序的记录序列中可能存在两个或两个以上关键字
相等的记录。排序前的序列中 Ri 领先于 Rj(即 i<j).若在排序后的
序列中 Ri 仍然领先于 Rj,则称所用的方法是稳定的。
其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个
键上排序,然后再从另一个键上排序,第一个键排序的结果可以为
第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高
位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另
外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的
次数可能会少一些(个人感觉,没有证实)。
回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简
单的理由。
评论10
最新资源