`
synchronized_lala
  • 浏览: 40955 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
最近访客 更多访客>>
社区版块
存档分类
最新评论

二分插入排序

阅读更多

二分(折半)插入排序基本思想:设在数据表中有一个元素序列v[0],v[1],v[2]......v[n].其中v[0],v[1],v[2]......v[i-1]是已经排好序的元素。在插入v[i]。利用折半搜索寻找v[i]的插入位置。

二分插入排序是一种稳定的排序。当n较大时,总排序码比较次数比直接插入排序的最差情况好得多,但比最好情况要差,所元素初始序列已经按排序码接近有序时,直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同,依赖于元素初始序列。

 

#include<iostream>
#include<cstring>

using namespace std;

int const ic_limit = 100002;

void vInputData(int &iNum,int iArr[]);
void BinaryInsertSort(int iArr[],int iLeft,int iRight);
void vPrintAns(int iNum,int iArr[]);

int main()
{
	int iNum;
	int iArr[ic_limit];

	memset(iArr,0,sizeof(iArr));
	vInputData(iNum,iArr);
	BinaryInsertSort(iArr,1,iNum);
	vPrintAns(iNum,iArr);

	return 0;
}

void vInputData(int &iNum,int iArr[])
{
	cin >> iNum;
	for(int i=1; i<=iNum; i++)
	{
		cin >> iArr[i];
	}
}

void BinaryInsertSort(int iArr[],int iLeft,int iRight)
{
	int iFo;
	int iTo;
	int iMid;
	int iTemp;

	for(int i=2; i<=iRight; i++)
	{
		iFo = 1;
		iTo = i-1;
		iTemp = iArr[i];
		while(iFo <= iTo)//确定插入位置
		{
			iMid = (iFo + iTo) / 2;
			if(iArr[i] < iArr[iMid])
			{
				iTo = iMid - 1;
			}
			else
			{
				iFo = iMid + 1;
			}
		}
		for(int j=i-1; j>=iFo; j--)//iFo == iTo == iMid
		{
			iArr[j+1] = iArr[j];
		}
		iArr[iFo] = iTemp;
	}
}

void vPrintAns(int iNum,int iArr[])
{
	for(int i=1; i<iNum; i++)
	{
		cout << iArr[i]  << " ";
	}
	cout << iArr[iNum] << endl;
}
 
1
0
分享到:
评论

相关推荐

    易语言源码二分插入排序.rar

    二分插入排序是一种高效且常用于优化的排序算法,尤其在处理近似有序的数据时表现优秀。它结合了二分查找的效率与插入排序的稳定性。在这个“易语言源码二分插入排序.rar”压缩包中,我们可以找到一个用易语言实现的...

    易语言二分插入排序

    二分插入排序是一种在编程领域中常见的排序算法,尤其在使用易语言编程时,它能够有效地对数组进行排序。易语言是一种以中文为程序代码的编程语言,旨在降低编程的难度,让更多的人能够参与到编程中来。在此,我们将...

    二分插入排序算法

    使用二分方法实现插入排序

    内部排序之二分插入排序

    ### 内部排序之二分插入排序:深入解析与实现 #### 一、知识点概览 在计算机科学中,排序算法是数据结构与算法领域的重要组成部分,广泛应用于各种场景,如数据库管理、搜索引擎优化等。其中,二分插入排序是一种...

    易语言二分插入排序.rar

    二分插入排序是一种在计算机科学中用于对列表或数组进行排序的算法,它结合了二分查找的效率和插入排序的稳定性。在易语言中,我们可以利用其丰富的语法和编程结构来实现这一算法。易语言是一款中国本土开发的、以...

    JS实现二分插入排序,前端必会

    二分插入排序是一种在计算机科学中用于对数组或列表进行排序的算法,它结合了二分查找和插入排序的优点。在前端开发中,理解和掌握这种排序算法对于优化数据处理和提高程序性能至关重要。以下是关于JS实现二分插入...

    二分插入排序-易语言.zip

    二分插入排序是一种效率较高的排序算法,尤其在处理近乎有序的数据时表现优秀。它基于分治策略,将未排序部分与已排序部分相结合,通过二分查找确定插入位置,从而达到排序的目的。在这个"二分插入排序-易语言.zip...

    易语言源码二分插入排序.7z

    二分插入排序是一种效率较高的排序算法,尤其在处理已经部分有序的数据时,其性能更为显著。易语言作为中国本土的一款编程语言,以其独特的汉字编程方式,使得编程更加直观易懂,特别适合初学者。在这个“易语言源码...

    Java经典排序算法之二分插入排序详解

    二分插入排序是一种改进的插入排序算法,它利用了二分查找的思想来减少在序列中找到合适插入位置的时间复杂度。在直接插入排序中,为了找到一个元素的正确位置,我们需要从当前元素开始向后逐个比较,直到找到合适的...

    模拟实验-C#版基于二分查找的稳定“插入排序”算法

    在本模拟实验中,我们关注的是使用C#编程语言实现基于二分查找的稳定“插入排序”算法。插入排序是一种简单直观的排序算法,它的工作原理是通过构造一个有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到...

    《数据结构》折半插入排序

    - **最好情况**:如果输入数组已经是正序,二分插入排序只需进行n-1次比较,时间复杂度为O(n log n)。 - **最坏情况**:如果输入数组反序,每次插入都需要移动n-i次元素,总比较次数仍为O(n^2),但移动次数减少,...

    MATLAB实现插入排序、二分归并排序、归并排序.rar

    在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...

    插入排序的设计实现分析比较.rar_C# 插入_插入排序

    在二分插入排序中,我们在寻找插入位置时使用二分查找,这可以显著减少比较次数,提高效率。但是,由于插入操作仍然需要移动元素,时间复杂度仍为O(n²),但常数因子有所减少。 在《插入排序的设计实现分析比较.doc...

    二分插入排序-易语言

    二分插入排序是一种效率较高的排序算法,尤其在处理近乎有序的数据时表现优秀。它基于插入排序,但在插入新元素时采用二分查找的方法来降低时间复杂度。在易语言中实现二分插入排序,可以更好地理解和应用这个算法。...

    Sort-algorithm.zip_插入排序_直接插入排序

    - **拆半插入排序**(二分插入排序):在查找插入位置时使用二分查找,提高了查找效率,降低了比较次数,但总的移动次数并没有减少,因此时间复杂度仍为O(n^2)。 - **简单选择排序**:每次从未排序的部分中选取最小...

    排序算法-插入排序

    - **二分插入排序**:在插入元素时,使用二分查找找到合适位置,减少比较次数,提高了效率。 4. **时间复杂度**: - 最好情况(输入数组已排序):时间复杂度为O(n)。 - 最坏情况(输入数组逆序):时间复杂度为...

    常用算法 2分法插入排序

    2分法插入排序(Binary Insertion Sort)是一种基于插入排序的算法,它结合了二分查找的策略来优化传统插入排序的过程。在传统插入排序中,我们需要将一个新元素与已排序的序列逐个比较,找到合适的位置插入。而2分...

    从二分排序看到的知识

    二分排序,也被称为二分插入排序(Binary Insertion Sort),是一种基于插入排序的优化算法。在普通插入排序中,我们需要遍历整个已排序部分来找到新元素的正确位置,而二分排序则通过二分查找来降低这个过程的时间...

Global site tag (gtag.js) - Google Analytics