插入排序

插入排序

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

插入排序此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

    在冒泡排序选择排序编写代码之后,楼主渐渐找到了coding的信心,熟能生巧,就像写词唱曲之前,都得先背诵大量的诗词,熟悉各路歌曲,才干走出自己的路线,有自己的杰作。好吧,来让楼主继续进行”社会主义0基础阶段”的任务,这次是插入排序。

一. 算法描写叙述

    插入排序插入即表示将一个新的数据插入到一个有序数组中,并继续保持有序。比如有一个长度为N的无序数组,进行N-1次的插入即能完毕排序;第一次,数组第1个数觉得是有序的数组,将数组第二个元素插入仅有1个有序的数组中;第二次,数组前两个元素组成有序的数组,将数组第三个元素插入由两个元素构成的有序数组中……第N-1次,数组前N-1个元素组成有序的数组,将数组的第N个元素插入由N-1个元素构成的有序数组中,则完毕了整个插入排序。

以以下5个无序的数据为例:

65 27 59 64 58 (文中仅细化了第四次插入过程)

第1次插入: 27 65 59 64 58

第2次插入: 27 59 65 64 58

第3次插入: 27 59 64 65 58

第4次插入: 27 58 59 64 65

插入排序

二. 算法分析

平均时间复杂度:O(n2)

空间复杂度:O(1)  (用于记录须要插入的数据)

稳定性:稳定

三. 算法实现

从前向后查找的插入排序:
/********************************************************
*函数名称:InsertSort
*參数说明:pDataArray 无序数组;
*		   iDataNum为无序数据个数
*说明:    插入排序
*********************************************************/
void InsertSort(int* pDataArray, int iDataNum)
{
	for (int i = 1; i < iDataNum; i++)    //从第2个数据開始插入
	{
		int j = 0;
		while (j < i && pDataArray[j] <= pDataArray[i])    //寻找插入的位置
			j++;
		
		if (j < i)    //i位置之前,有比pDataArray[i]大的数,则进行挪动和插入
		{
			int k = i;
			int temp = pDataArray[i];
			while (k > j)    //挪动位置
			{
				pDataArray[k] = pDataArray[k-1];
				k--;
			}
			pDataArray[k] = temp;    //插入
		}
	}
}

但楼主发现从后面查找插入的方式,代码复杂程度较低:
/********************************************************
*函数名称:InsertSort
*參数说明:pDataArray 无序数组;
*		   iDataNum为无序数据个数
*说明:    插入排序
*********************************************************/
void InsertSort(int* pDataArray, int iDataNum)
{
	for (int i = 1; i < iDataNum; i++)    //从第2个数据開始插入
	{
		int j = i - 1;
		int temp = pDataArray[i];    //记录要插入的数据
		while (j >= 0 && pDataArray[j] > temp)    //从后向前,找到比其小的数的位置
		{
			pDataArray[j+1] = pDataArray[j];    //向后挪动
			j--;
		}

		if (j != i - 1)    //存在比其小的数
			pDataArray[j+1] = temp;
	}
}

四. 算法优化

插入排序中,总是先寻找插入位置,然后在实行挪动和插入过程;寻找插入位置採用顺序查找的方式(从前向后或者从后向前),既然须要插入的数组已经是有序的,那么能够採用二分查找方法来寻找插入位置,提高算法效率,但算法的时间复杂度仍为O(n2)。

//查找数值iData在长度为iLen的pDataArray数组中的插入位置
int FindInsertIndex(int *pDataArray, int iLen, int iData)
{
	int iBegin = 0;
	int iEnd = iLen - 1;
	int index = -1;    //记录插入位置
	while (iBegin <= iEnd)
	{
		index = (iBegin + iEnd) / 2;
		if (pDataArray[index] > iData)
			iEnd = index - 1;
		else
			iBegin = index + 1; 
	}
	if (pDataArray[index] <= iData)
		index++;
	return index;
}

/********************************************************
*函数名称:BinaryInsertSort
*參数说明:pDataArray 无序数组;
*		   iDataNum为无序数据个数
*说明:    二分查找插入排序
*********************************************************/
void BinaryInsertSort(int* pDataArray, int iDataNum)
{
	for (int i = 1; i < iDataNum; i++)    //从第2个数据開始插入
	{
		int index = FindInsertIndex(pDataArray, i, pDataArray[i]);    //二分寻找插入的位置
		
		if (i != index)    //插入位置不为i,才挪动、插入
		{
			int j = i;
			int temp = pDataArray[i];
			while (j > index)    //挪动位置
			{
				pDataArray[j] = pDataArray[j-1];
				j--;
			}
			pDataArray[j] = temp;    //插入
		}
	}
}




版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118019.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 微信公众号网页开发,登录授权和微信支付

    微信公众号网页开发,登录授权和微信支付微信公众号的网页开发基本和H5移动端开发一致,主要是涉及到网页授权获取用户信息和使用js-sdk获取微信原生能力支持。开发前准备申请一个测试号:https://mp.weixin.qq.com/debug/cgi-bin/sandbox?t=sandbox/login用自己微信扫码登录,然后扫码关注当前测试号,这里注意js接口安全域名和网页授权回调域名,需要配置为当前项目地址。使用测试号时用ip即可,但是线上必须是域名。网页授权类似把系统自己的登录体系移除,通过微信授权方式获取微信用户信息。

  • js android 换行符,关于js对textarea换行符的处理方法浅析

    js android 换行符,关于js对textarea换行符的处理方法浅析前言本文很简单,就是记录一下js对textarea换行符的处理。调试随便写一个textarea整个调试如下图:发现:textareaid里面的换行符可以通过indexOf获取textareaid.value.indexOf(“\n”)但是直接通过正则全局替换没有效果(如上图)textareaid.value.replace(‘/\n/g’,’;’)但是单个替换可以替换到:textareaid.v…

  • ora-00984列在此处不允许_嵌套定义和嵌套调用

    ora-00984列在此处不允许_嵌套定义和嵌套调用嵌套循环中要求每一列都有唯一的列名**,特别注意:空字符串一定要起别名,不然会被当做是相同列明处理.**错误示范:正确示范:

  • HTTP请求中的form data和request payload的区别

    HTTP请求中的form data和request payload的区别

  • idea 2021.9最新激活码 mac[最新免费获取]

    (idea 2021.9最新激活码 mac)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~1STL…

  • Java 中的 int 型转为 long 型

    Java 中的 int 型转为 long 型先将int 型转为String 型,然后再将String 转为long 型,如下图: publicclassTestIntToLong{publicstaticvoidmain(String[]args){intnum=18;Stringstr=String.valueOf(num…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号