【数据结构】排序之插入排序（直接插入排序||希尔排序）

1.前言

在生活中处处可见排序，当我们打开京东或者其它购物平台时，搜索物品，它会有一定的排序。
这次就来分享的博客与排序有关。
正文开始。

2. 排序的概念及其运用

2.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2.2 排序的运用

举个例子：
在京东上平板的统合排名：

来看看高校的排名：

可能每个人搜出来的不一样。

2.3 常见的排序算法

3. 插入排序

3.1 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
就像是在玩扑克牌时候，对刚拿的牌来进行一个插入。

3.2 直接插入排序

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

直接看动图：

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

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

3.2.1 直接插入排序实现

以升序为例子

3.2.1.1 分析

就是把没排好的数插入到已经排好的数中，实现有序。
实现排序，先实现单趟。
假设在一个已经排好序的区间[0,end]，然后把end+1位置的值插入进去，那怎么插入呢？
从后往前，依次比较，如果比end+1大，那就往后挪，把位置空出来，再把值放进去。为了记录插入的数据，用一个临时变量tmp存储 end+1的值，避免被覆盖。

假设前面的已经[0,end]，也就是3，4，9已经排好。这时要插入6，先记录一下tmp=6，然后依次往前比较，如果比tmp大，那就往后挪。

还有一种情况：
一直往走，往后挪数据，当end<0时结束。

所以这里循环的条件就是while (end >= 0）。
如果tmp < a[end],就实现a[end + 1] = a[end]，然后end1--。
循环结束就有两种情况：一种是tmp>=end,tmp就得放在end后面。另一种是：在while条件结束，出现end<0。

单趟的已经实现，那怎么实现整体？
在while循环外面再套一层循环。
第一个数据就是[0,0],再往下是[0,1],2位置的往前插入。那么它的结束位置就是n-1，不能是n，因为如果到n,那么tmp位置访问n+1,已经越界了。

3.2.1.2 代码实现

void InsertSort(int* a, int n)
{
	// [0, end] end+1
	for (int 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

来看看结果：

3.3 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：
4. 稳定性：不稳定

3.3.1 希尔排序实现

希尔排序分为两部分：第一部分是预排序，第二部分是直接插入排序。

3.3.1.1 分析

预排序的目的是让数组基本有序，这样直接插入就很快。
举个例子：gap=3
将间隔为3的分为一组，那么总的就分为了三组。红的一组，蓝的一组，绿的一组。

那么它的预排序怎么实现呢？
就是将分的这三组，分别进行插入排序。
首先将9当成已经排好的数据，那么下一个不是8，而是间隔为3的6,把6往前插入，然后继续找下一个就是4，继续往前面插入。
最后就是这样;

剩下的两组也是一样的，最终排出来就是

这里只是接近有序。

就是把上面的直接插入排序的tmp换成end + gap位置的就行。

假设先对红色这组经行排序，那就是：

注意循环的条件如果是i<n，那么就会访问越界，注意看图上，发现结束的位置就是n-gap。
如果排实现的两组，那么就直接再套一层，循环gap=3次就排完了。

这里套了三层排序，也只是预排序，j为0就是红色的一组，j为1就是蓝色那组，j为2就是绿色那一组。

优化一下，实现多组并排，之间是一组一组往后排，现在是直接在gap组之间来回跳，第一次排红色，第二次排蓝色，第三次排绿色。
少一层循环。

gap怎么选择：

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

所以这里实现希尔排序，就是将gap不断变小,
gap > 1时是预排序，目的让他接近有序,而gap == 1是直接插入排序，目的是让他有序。
那么这里gap怎么选择呢？
如果gap = gap / 2，这里跳跃就比较小，所以选择gap = gap / 3 ，但为了保证最后一次为1，这里就得加1，也就是gap = gap / 3 + 1。

来看看结果：

3.3.1.2 代码实现

void ShellSort(int* a, int n)
{
	int gap = n;
	// gap > 1时是预排序，目的让他接近有序
	// gap == 1是直接插入排序，目的是让他有序
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
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

4. 附代码

4.1 sort.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

void PrintArray(int* a, int n);
void InsertSort(int* a, int n);
void ShellSort(int* a, int n);
1
2
3
4
5
6
7
8
9
10

4.2 sort.c

#include"Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 时间复杂度：O(N^2) 逆序
// 最好的情况：O(N)  顺序有序
void InsertSort(int* a, int n)
{
	// [0, end] end+1
	for (int 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;
	}
}


// 平均O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;

	// gap > 1时是预排序，目的让他接近有序
	// gap == 1是直接插入排序，目的是让他有序
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;

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


	/*for (int j = 0; j < gap; ++j)
	{
		for (int i = j; i < n-gap; i += gap)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}*/
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

4.3 test.c

#include"Sort.h"

void TestInsertSort()
{
	int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestShellSort()
{
	int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
	TestInsertSort();	
	TestShellSort();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

在之后的博客中会继续分享与排序有关的内容，请多多关注。
有问题请指出，大家一起进步！