数据结构排序稳定性总结.doc
5星 · 超过95%的资源 需积分: 50 57 浏览量
2020-04-03
09:55:53
上传
评论 1
收藏 38KB DOC 举报 
排序稳定性
【1】选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法
冒泡排序、插入排序、归并排序和基数排序都是稳定的排序算法。
【2】研究排序算法的稳定性有何意义？
首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前两个相
等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。
再简单具体一点，如果 A i == A j，Ai 原来在 Aj 位置前，排序后 Ai 仍然是在 Aj
位置前。
下面我们分析一下稳定性的好处：
（1）如果排序算法是稳定的，那么从一个键上排序，然后再从另一个键上排序，
第一个键排序的结果可以为第二个键排序所利用。基数排序就是这样，先按低
位排序，逐次按高位排序，那么，低位相同的数据元素其先后位置顺序即使在
高位也相同时是不会改变的。详细请参见随笔《基数排序》。
（2）学习排序原理时，可能编的程序里面要排序的元素都是简单类型，实际上
真正应用时，可能是对一个复杂类型（自定义类型）的数组排序，而排序的键
值仅仅只是这个元素中的一个属性，对于一个简单类型，数字值就是其全部意
义，即使交换了也看不出什么不同。但是，对于复杂类型，交换的话可能就会
使原本不应该交换的元素交换了。比如：一个“学生”数组，欲按照年龄排序，
“学生”这个对象不仅含有“年龄”，还有其它很多属性。假使原数组是把学号作为
主键由小到大进行的数据整理。而稳定的排序会保证比较时，如果两个学生年
龄相同，一定不会交换。那也就意味着尽管是对“年龄”进行了排序，但是学号
顺序仍然是由小到大的要求。
（3）如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能相
对会少一些（个人感觉，没有证实）。
【3】各种排序算法稳定性分析
现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。
（1）冒泡排序
冒泡排序就是把小的元素往前调（或者把大的元素往后调）。注意是相邻的两
个元素进行比较，而且是否需要交换也发生在这两个元素之间。所以，如果两
个元素相等，我想你是不会再无聊地把它们俩再交换一下。如果两个相等的元
素没有相邻，那么即使通过前面的两两交换把两个元素相邻起来，最终也不会
交换它俩的位置，所以相同元素经过排序后顺序并没有改变。
所以冒泡排序是一种稳定排序算法。
（2）选择排序
选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位
置选择最小的，在剩余元素里面给第二个位置选择次小的，依次类推，直到第
n-1 个元素，第 n 个元素不用选择了，因为只剩下它一个最大的元素了。那么，
在一趟选择时，如果当前锁定元素比后面一个元素大，而后面较小的那个元素
又出现在一个与当前锁定元素相等的元素后面，那么交换后位置顺序显然改变
了。举个例子：序列 5 8 5 2 9， 我们知道第一趟选择第 1 个元素 5 会与 2 进行交
换，那么原序列中两个 5 的相对先后顺序也就被破坏了。
所以选择排序不是一个稳定的排序算法。
（3）插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚
- 1
- 2
前往页