【数据结构初阶】直接插入排序

最近浅学了直接插入排序，写个博客做笔记！笔记功能除外若能对读者老爷有所帮助最好不过了！

直接插入排序是插入排序的一种，那么介绍直接插入排序之前先介绍一下常见的排序算法！

目录

1.常见的排序算法

2.直接插入排序

 3.直接插入排序的时间复杂度和空间复杂度

---

1.常见的排序算法

那么常见的排序算法包括但不限于以下：

那么鼠鼠今天只是浅介绍一下插入排序中的直接插入排序！

2.直接插入排序

鼠鼠这篇博客拿排升序来讲解直接插入排序！

直接插入排序的思想：

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

说简单一点就是：有一个本身有序的数组，往这个数组插入一个数据，使得这个数组继续有序。那么如何插入就是关键，鼠鼠给各位举一个例子：

鼠鼠上面举的栗子就是让原本有序的数组插入一个数据后继续有序了：下标为0到下标为end的数据组成的数组本身有序，插入下标位end+1的数据，经过上图的操作让数组继续有序。 

其实上图展现的就是直接插入排序的“单趟”，即下标为0到下标为end的数据组成的数组本身有序，插入下标位end+1的数据，经过上图的操作让数组继续有序，用代码写出“单趟”来如下：

int end;
		int tmp = a[end + 1];
		for (end; end >= 0; end--)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;

那么我们只要控制住下标end就可以完成直接插入排序的完整代码，我们想想：

有一个乱序且数据个数为n的数组让我们排序。

当下标end等于0时，取乱序数组的第1个数据充当有序数组，只有1个数据我们当然可以看成是有序的，插入下标为end+1的数据（“前1个有序，第2个插入”），经过“单趟”前2个数据排列有序！

当下标end等于1时，取乱序数组前2个数据，这2个数据已经变为有序的了，插入下标为end+1的数据（“前2个有序，第3个插入”），经过“单趟”前3个数据排列有序！

当下标end等于2时，取乱序数组前3个数据，这3个数据已经变为有序的了，插入下标为end+1的数据（“前3个有序，第4个插入”），经过“单趟”前4个数据排列有序！

…………………………

当下标end等于n-2时，取乱序数组前n-1个数据，这n-1个数据已经变为有序的了，插入下标为end+1的数据（“前n-1个有序，第n个插入”），经过“单趟”前n个数据排列有序，就是乱序数组变成有序的了！

注释：我们要搞清楚数组下标是从0开始的，下标为0的数据是第1个数据，下标为1的数据是第2个数据……

这个动图很好展示了直接插入排序。

那么一个循环控制end，让“单趟”变为“多趟”，我们的直接插入排序就搞定了，代码如下：

//直接插入排序排升序
void InsertSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++)
	{
		int end=j;
		int tmp = a[end + 1];
		for (end; end >= 0; end--)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

鼠鼠来浅浅运用一下：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
//直接插入排序排升序
void InsertSort(int* a, int n)
{
	for (int j = 0; j < n - 1; j++)
	{
		int end=j;
		int tmp = a[end + 1];
		for (end; end >= 0; end--)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
 
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
 
int main()
{
	int a[] = { 0,1,5,4,7,8,6,4,88,3,5, };
	PrintArray(a, sizeof(a) / sizeof(a[0]));
	InsertSort(a, 11);
	PrintArray(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

没有问题的！ 

 3.直接插入排序的时间复杂度和空间复杂度

根据插入排序的思想，很明显直接插入排序的时间复杂度是O(N^2)。

当然当我们想要排升序时，待排序的数组本身是升序或者解决升序的情况下，时间复杂度差不多是O(N)。也就是说待排序数组本身越接近有序（我们期待的有序），直接插入排序的时间效率越高。

不过时间复杂度考虑的是“最坏情况”,所以说直接插入排序时间复杂度是O(N^2)。

直接插入排序空间复杂度是O(1)。

感谢阅读！