排序算法：折半插入排序

2021-06-19 17:03

阅读：521

标签：cto 元素存储空间 ++ using 附加移动如何查找

算法分析：

（1）时间复杂度

　　从时间上比较，折半查找比顺序查找快，所以就平均性能来说，折半插入排序优于直接插入排序。

　　折半插入排序所需要的关键字比较次数与待排序序列的初始排列无关，仅依赖于记录的个数。不论初始序列情况如何，在插入第i个记录时，需要经过logi+1(向下取整+1)次比较，才能确定它插入的位置。所以当记录的初始排列为正序或接近正序时，直接插入排序比折半插入排序执行的关键字比较次数要少。

　　折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。

　　在平均情况下，折半插入排序仅减少了关键字的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍然为O（n^2）。

（2）空间复杂度

　　折半插入排序所需附加存储空间和直接插入排序相同，只需要一个记录的辅助空间r[0]，所以空间复杂度为O（1）

算法特点：

（1）是稳定排序。

（2）因为要进行折半插入查找，所以只能用于顺序结构，不能用于链式结构。

（3）适合初始记录无序、n较大的情况。

#include
#include
using namespace std;
void BSort(int a[],int n)
{
	for (int i = 1; i = high + 1; j--)
		{//i-1是已经排好序的序列的数量，high+1是待插入的的位置，元素后移腾出high+1这个位置
			a[j + 1] = a[j];
		}
		a[high + 1] = key;
	}
}
int main()
{
	int a [11] = { 2,6,4,5,54,53,53,5,34,34,32};
	BSort(a, 11);
	for (int i = 0; i

排序算法：折半插入排序

标签：cto 元素存储空间 ++ using 附加移动如何查找

原文地址：https://www.cnblogs.com/wuyepeng/p/9690299.html

上一篇：排序算法：冒泡排序

下一篇：浅谈JavaScript的Object类型

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：排序算法：折半插入排序
文章链接：http://soscw.com/essay/96033.html

亲，登录后才可以留言！

排序算法：折半插入排序

评论

热门文章

推荐文章

最新文章

置顶文章