各种排序算法稳定性

各种排序算法稳定性

ID:20722120

大小:27.00 KB

页数:5页

时间:2018-10-15

各种排序算法稳定性_第1页
各种排序算法稳定性_第2页
各种排序算法稳定性_第3页
各种排序算法稳定性_第4页
各种排序算法稳定性_第5页
资源描述:

《各种排序算法稳定性》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、各种排序算法的稳定性各种排序算法的稳定性2009-10-2112:02首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai=Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。为了简便下面讨论的都是不降序排列的情形,对于不升序排列的情形讨论方法和结果完全相同。其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位

2、排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些(个人感觉,没有证实)。回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。(1)冒泡排序冒泡排序是通过相邻比较、实时交换、缩小范围实现排序的。第1次操作n个元素,通过相邻比较将0~n-1中的最大元素交换到位置n-1上,第2次操作n-1个元素,通过相邻比较将0~n-2中的最大元素交换到位置n-2上……第n-1次操作2个元素,通过相邻比较将0~1上的最大元素交换到位置1上完成排序。在相邻比较时如果

3、两个元素相等,一般不执行交换操作,因此冒泡排序是一种稳定排序算法。(2)选择排序选择排序是通过不断缩小排序序列长度来实现的。第1次操作n个元素,选择0~n-1中的最小者交换到位置0上,第2次操作n-1个元素,选择1~n-1中的最小者交换到位置1上……第n-1次操作2个元素,选择n-2~n-1上的最小者交换到位置n-2上完成排序。在每次选择最小元素进行交换时,可能破坏稳定性。这种情况可以描述为:约定要发生交换的位置称为当前位置,被交换的位置称为被交换位置,被交换位置上的元素为选中的最小元素。如果当前位置之后和被交换位置之前存在与当前位置相等

4、的元素,执行交换后就破坏了稳定性。如序列58529,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。(3)插入排序插入排序是通过不断扩大排序序列的长度来实现的。第1次操作1个元素,直接放到位置0上即可;第2次操作2个元素,在0~1上为当前元素找到合适位置并插入;第3次操作3个元素,用在0~2上为当前元素找到合适位置并插入它……第n次操作n个元素,在0~n-1上为当前元素找到合适位置并插入完成排序。讨论元素的插入过程,假设当前是第n次操作,要在0~n-1上为当前元素寻

5、找合适位置,设置一个工作指针初始化为n-1,向前移动工作指针直到遇到一个不大于当前元素的元素,就在这个元素的后面插入当前元素,仔细体会这个插入过程,不难理解插入排序是稳定的。(4)快速排序快速排序有两个方向,左边的i下标当a[i]<=a[center]时一直往右走,其中center是中枢元素的数组下标,一般取为当前排序段的第一个元素。而右边的j下标当a[j]>a[center]时一直往左走。如果i和j都走不动了,这时必有结论a[i]>a[center]>=a[j],我们的目的是将a分成不大于a[center]和大于a[center]的两个

6、部分,其中前者位于左半部分后者位于右半部分。所以如果i>j(i不能等于j,为什么?)表明已经分好,否则需要交换两者。当左右分好时,j指向了左侧的最后一个元素,这时需要将a[center]与a[j],交换,这个时侯可能会破坏稳定性。这种情形可以这样描述:center位置之后j位置前存在与j相等的元素,指向center与j的交换后,稳定性破坏。比如序列为53343891011,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法。(5)归并排序归并排序是把序列递归地分成短序列,递归出

7、口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。(6)基数排序基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推

8、,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。