数据结构插入排序

好久不见，这几天有点事情，都快一个礼拜没有学习，对键盘都要陌生起来了，今天也是刚刚学了一点排序，在这里也给大家更新一个插入排序，后面也会渐渐的把八大排序更新完的，还有就是二叉树，二叉树小编能力有限，可能也是学了一点点，废话不多说，我们进入今天的学习吧。

插入排序和我们之前学过的冒泡排序有一点相似之处，首先他们的空间复杂度都是O（N*N），插入排序的整个过程是怎么样的呢，首先我们先引入一个小问题，那就是我们将一个数插入到一个升序的有序列数组当中，我们是怎样插入的，首先我们应该拿这个数去进行比较，从末尾开始比，如果比这个数大我们就要继续往前找，一直到找到大于或者等于这个数的时候，我们在这个数的末尾进行插入，在插入过程中，如果这个数比其他数要小的时候，其他数应该要往后移动，相当于是一个覆盖的思路，我们这里给一个图，让大家比较好理解。

我们end一直往前面走，一直到找到合适的位置才停止，中间还有一个过程是覆盖，画图里没有体现出来，就是不满足条件就往后移动覆盖，我们用代码看看可能更好来理解。

	int end = 9;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end+1] = tmp;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

假设我们有九个数，现在就是要把1放入这个数组当中我们改怎么做呢，上面的代码就可以体现出来，那么我们有这个思路之后，我们是不是可以模拟到插入排序当中，其实很简单只要在我外面套一个循环就能实现了，那我们来试一试吧

void InsertSort(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end+1] = tmp;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这个样子就能把我们的插入排序实现了，我们也可以测试一下
头文件
InsertSort.h

#include

void InsertSort(int* a, int n);

void PrintInsert(int* a, int n);
1
2
3
4
5
6

InsertSort.c

#include"Insert.h"

void InsertSort(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end+1] = tmp;
	}
}

void PrintInsert(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

Test.c

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	InsertSort(arr, sizeof(arr) / sizeof(int));
	PrintInsert(arr, sizeof(arr) / sizeof(int));
	return 0;
}
1
2
3
4
5
6
7

调试之后就能把它变成有序的了，今天我们就讲一个排序，因为小编偷懒，今天只学了一个排序哈哈哈哈

我们下次再见