我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分插入 >

二分插入排序是稳定的吗?我不懂如何保证其稳定性?(详见内容)

归档日期:06-06       文本归类:二分插入      文章编辑:爱尚语录

  比如1122这个序列为有序区,在这个有序区中插入新的元素2,可是二分插入排序好像只能保证2插入后依然有序,可不能保证2插入到正确的位置(正确的位置是指符合排序算法稳定性)

  那二分插入排序还是稳定的吗?为什么好多资料都说是稳定的?展开我来答

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  2012-02-12展开全部判断排序算法稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

  那么就很明显了,二分插入排序后并没有改变相等元素的相对位置。追问为什么没有改变?比如二分插入排序,2有多个位置都可以插入,如何保证二分查找找到的是正确的2的位置?追答比如二分查找举个例子吧。。。1122在数组a中的位置是0,1,2,3.。。。先二分(0 + 3) 2 = 1(此处取整了)需要插入的2与a[1]比较a[1]是1,然后继续二分(2 + 3) 2 = 2(取整),需要插入的2与a[2]比较发现a[2] = 2,然后插入,稳定是指排序前相同的数字的相对次序不变。。。以前数组a中的两个2并没有顺序改变。。。

本文链接:http://pikeducation.com/erfencharu/345.html