【校招VIP】[数据结构1.0]直接插入排序- 校招VIP

转载声明：文章来源https://blog.csdn.net/X__cheng/article/details/138470928

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;
	}
}

鼠鼠来浅浅运用一下：

#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.直接插入排序的复杂度和稳定性
1.复杂度：
根据插入排序的思想，很明显直接插入排序的时间复杂度是O(N^2)。
当然当我们想要排升序时，需排序数组本身是升序或者接近升序的情况下，时间复杂度差不多是O(N)。也就是说需排序数组本身越接近有序（我们期待的有序），直接插入排序的时间效率越高。
不过时间复杂度考虑的是“最坏情况”,所以说直接插入排序时间复杂度是O(N^2)。
直接插入排序空间复杂度是O(1)。

2.稳定性：
大概介绍一下稳定性的概念：在数组中相同的数据，排序之后能保证相对顺序不变的话该排序就是稳定的。反之，就不稳定。比如：
有一个需排序数组需要我们排升序如图：
这里有两个5，如果排序完成后能保证绿色的5能排在紫色的5前面的话该排序就是稳定的。反之，该排序就是不稳定的！
根据这个思想，我们可以知道直接插入排序是稳定的，当然我们要保证每趟直接插入排序的“单趟”中遇到相等的数据就break掉结束“单趟”，不然就难以保证直接插入排序是稳定的。

感谢阅读！