首页 > 其他 > 详细

白话简述:排序算法的稳定性 (什么样的排序是不稳定的)

时间:2014-01-23 09:36:51      阅读:393      评论:0      收藏:0      [点我收藏+]

拿{ 6,2,4,6,1}举例。

a[0] a[1] a[2] a[3] a[4]
6 2 4 6 1

 

 

有两个6,a[0]和a[3]。排序结果就有两种可能

1 2 4 6 6
原a[4] 原a[1] 原a[2] 原a[0] 原a[3]
原a[4] 原a[1] 原a[2] 原a[3] 原a[0]

 

 

 

如果排序结束后,a[0]可以保证一定在a[3]前头,也就是他们原有的顺序不变,那这种排序算法就是稳定的。(比如常见的冒泡排序、基数排序、插入排序、归并排序、桶排序、二叉树排序等都是稳定的排序算法

反之,如果不能保证原有顺序,这种算法就是不稳定的。(比如常见的选择排序,希尔排序,堆排序,快速排序等都是不稳定的排序算法)

要证明一种排序算法不稳定,举出一组例子就OK了;但要证明算法稳定,就要对算法设计进行彻底分析了。

白话简述:排序算法的稳定性 (什么样的排序是不稳定的)

原文:http://www.cnblogs.com/hydor/p/3530593.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!