栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【数据结构排序算法】直接插入排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【数据结构排序算法】直接插入排序

文章目录
  • 前言
  • 一、直接插入排序的基本思想
  • 二、直接插入排序代码实现
  • 三、直接插入排序的复杂度分析


前言

直接插入排序是属于插入排序类的一种,这种排序的方法相对较为简单,实现起来较为容易。直接插入排序的算法思想有点类似于我们平时打牌摸牌的操作,将新摸上来的牌插入到原先已经有序的区间里面,使得其仍然有序。下面我们将介绍直接插入排序的具体思想和实现方法,以及其时间复杂度、空间复杂度和稳定性。


一、直接插入排序的基本思想

基本思想: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。

简单一点的描述,就是首先在一个已经排好序的序列当中,我们要插入的新的值依次与原先序列中的值进行比较,(以升序为例)将要插入的值插入到序列当中使得该值前面的数都小于它,后面的数都大于它,从而得到的新序列依然是有序的。


二、直接插入排序代码实现
//以排升序为例
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		//tmp变量保存待插入的数据
		int tmp = a[end + 1];
		while (end >= 0)
		{
		    //当a[end]>tmp时,将a[end]的值往后移,end向前减一
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			//直到a[end]<=tmp时,代表该位置是正确的插入位置,停止循环
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

三、直接插入排序的复杂度分析

时间复杂度: 我们首先来看直接插入排序的最好的情况,也就是当待排序的数据是顺序有序的时候,也就是不需要排序就已经是所要求的有序了,在这种情况下直接插入排序仍然需要对所有数据进行一次遍历,时间复杂度是O(N);再来看最坏的情况,也就是当待排序的数据是逆序有序的时候,也就是说从头到尾每一个数据我们都需要去向后挪动,然后再插入数据,这种情况下的时间复杂度是O(N2),由于时间复杂度算的是最坏的情况,因此直接插入排序的时间复杂度是O(N2)。

空间复杂度: 由于直接插入排序没有开辟额外的空间,因此直接插入排序的空间复杂度是O(1)。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/956075.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号