前言

插入排序一般分为两种，一种直接插入排序，另一种则是希尔排序。

一、直接插入排序

1.简介

  直接插入排序是一种简单的排序方法，基本操作就是将需要排序的元素插入到已排好的有序表序列中，从而得到一个完整的序列。
  时间复杂度为：O(n²)    空间复杂度：O(1)      稳定性：稳定
  生活中最明显的例子就是，打扑克，把牌洗混，然后抓牌，以第一张为基础，然后将后面的牌依次插入，最后得到有顺序的牌面。

2.算法思路

将待排的序列看作成2个部分，一部分为有序，另一部分为无序。
我们将第一个元素看作有序序列，第二个到最后都是无序序列。
将无序序列的每一个元素依次插入到有序序列的合适位置。
讲解：有一个待排序序列：【2,5,8,3】
我们将第一个2看成已经排序好的序列，即有序序列，从第二个元素到最后一个元素看作是无序序列。
待排序元素比有序元素大，则插在有序元素后，反之，插在有序元素前

3.代码实现

#include<stdio.h>
#define num 12
void insert_sort(int* a, int n)
{
	
	for (int i = 0; i < n - 1; ++i)
	{
		// 将x插入[0, end]有序区间
		int end = i;
		int x = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				end--;
			}
			else break;
		}
		a[end + 1] = x;
	}
}
int main()
{
	int arr[num] = { 3,1,4,5,2,7,9,0,8,10,11,6 };
	printf("\n初始序列\n");
	for (int i = 0; i < num; i++)
	{
		printf("%d ", arr[i]);
	}
	insert_sort(arr, num);
	printf("\n排序后序列\n");
	for (int i = 0; i < num; i++)
	{
		printf("%d ", arr[i]);
	}
}
45
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
35
36
37

运行结果：
在这里插入图片描述

二、希尔排序

1.简介

希尔排序是在直接插入排序的基础上做了较大的改进，是将整个无序序列分割成若干个的子序列分别进行插入排序。
简单而言：将数组预排序，接近有序。
元素为逆排序时，时间复杂度最差为O(n²）空间最差复杂度: O(n)
平均时间复杂度为O(nlog2n) 平均空间复杂度（O(1)）
稳定性：差

2.算法思路

先取一个小于数组数的整数x作为第一个增量，把文件的全部记录分成x个组。
所有距离为x的倍数的值在同一组里，然后进行直接插入排序，变成有序序列。
取一个小于x的 x1 作为第二个增量，重复上述分组和排序，直到增量为1。
注：当增量为1时，相当于所有记录放在同一组里进行直接插入排序

来自百度
假设有一组{70，30，40，10，80，20，90，100，75，60，45}无序序列

第一趟：增量gap为3时，即距离为3的元素放在一组，可以分成3组，分别是{70，10，90，60}，{30，80，100，45}，{40，20，75}，按照直接插入排序对每个组进行排序。
第二趟：gap变成了2，接着和第一趟一样，最后也是按照直接插入排序对每个组进行排序。
第三趟：gap为1，后续操作也是如此…

3.代码实现

代码如下：

#include<stdio.h>
#define num 12
void ShellSort(int* a, int n)
{
	int gap = n;	
	while (gap > 1)
{
	gap = gap / 3 + 1; 
		for (int i = 0; i < gap; i++)
		{
			for (int j = i; j < n - gap; j += gap)
			{
				int end = j;
				int x = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > x)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else break;
				}
				a[end + gap] = x;
			}
		}
	}
}
int main()
{
	int arr[num] = { 3,1,4,5,2,7,9,0,8,10,11,6 };
	printf("初始序列:\n");
	for (int i = 0; i < num; i++)
	{
		printf("%d ", arr[i]);
	}
	ShellSort(arr, num);
	printf("\n排序后序列\n");
	for (int i = 0; i < num; i++)
	{
		printf("%d ", arr[i]);
	}
}
45
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
35
36
37
38
39
40
41
42
43