? 博客内容：【数据结构】插入排序详细图解（一看就懂）

? 作  者：陈大大陈

?所属专栏：数据结构笔记

? 个人简介：一个正在努力学技术的准前端，专注基础和实战分享 ，欢迎私信！

? 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 ? ? ?

目录

前言引入

 插入排序的原理

插入排序源码

详细实例过程图解

本章小结

前言引入

  插入排序是一种非常有意思且比较高效的排序方法，同时插入排序是希尔排序的基础 。

我预备下一篇博客讲解希尔排序，这一篇就先讲一下插入排序。

在生活中，这种排序方法也随处可见。

例如，我们在玩扑克牌时，总会按照插入排序的方法调整扑克牌的位置。 

玩扑克牌怎么会用到插入排序的方法呢？

当我们拿起第二张牌时，就会下意识的与第一张牌进行比较，如果比第一张牌小，我们就会将牌插入至第一张牌的左边，反之就插入至右边。

这样边插入边排序，就是插入排序，插入后的序列依旧是有序的。

大家先看一下下面的原理和代码，然后再看实例图可能会比较好。

 插入排序的原理

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。 

我们将原数组空间看成两个部分，前边是有序部分，后边是无序部分，有序部分我们默认为它就已经是排好序的，在尾部新加入的元素有可能会导致整个有序数组变得无序，因此我们需要进行调整。

调整方式就是将新加入的元素进行对比并往前移动，新加入元素和它前边的元素进行对比，如果它比它前边的元素小，则二者互换位置，不断重复这个过程，直到它前边的元素小于它才会停止，这样一来，他就仍然是有序数组。

插入排序源码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void InsertSort(int* a, int n)
{
	int tmp;
	int end;
	for (int i = 1; i < n; i++)
	{
		end = i - 1;
		tmp = a[i];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
int main()
{
	int a[] = { 45,67,89,12,34,5,6,8,1,2,67,99,55 };
	InsertSort(a, sizeof(a) / sizeof(a[0]));
	for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}
/*{ 45,45,89,12,34,5,6,8,1,2,67,99,55 };*/

运行结果

详细实例过程图解

就按这组数据为例，此时end处的值不大于i处的值，不用进入循环， a[end + 1] = tmp;不造成影响

第二次，同理，i++继续往后走。

第三次，这次不一样了！a[end]>a[i]，也就是a[end]大于tmp了，进入循环。

循环一次，完成 a[end + 1] = a[end];  end--;a[end+1]=tmp;的操作。

此时end值为1，大于0，循环继续。

循环两次，完成 a[end + 1] = a[end];  end--;a[end+1]=tmp;的操作。

此时end值为0，等于0，循环继续。

循环三次， 完成 a[end + 1] = a[end];  end--;a[end+1]=tmp;的操作。

此时end值为-1，小于0，循环结束。

第一次排序结束，下面的排序也就是比葫芦画瓢了，这里我就不列举了。

本章小结

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，是一种稳定的排序算法

4. 是否稳定：稳定

下一篇更新希尔排序，博客里如果有问题的话，还请大佬私信我，我会修改的。

有问题的话请私信问我，我看到就会回的。