C语言描述数据结构 —— 常见排序(1)直接插入排序、希尔排序、选择排序、堆排序

1.开始之前

在正式介绍排序之前，先了解一下排序的分类。当然是基于常用的排序算法分类。

可以看到常用的排序算法是有8种的，这8种的效率各不相同，而每种排序都有不同版本的实现算法。那么排序这个章节呢，我也会分篇介绍。

那么排序的概念就不介绍了。排序最直接的应用在我们的日常购物软件或者一些搜索功能上。例如我们在购物软件上搜索“笔记本电脑”，我们可以按照热度排序、销量排序、价格排序等等排序方式来方便我们的选择。

在C语言中，封装了排序算法 qsort 函数，为什么还要学习其他的排序算法呢？因为在不同的环境当中、不同的使用场景当中，对排序的要求都是不一样的。而我们学习的目的不仅仅是学会排序这么简单，重要的是掌握其算法的核心思想，提升我们的技能。

2.直接插入排序

​我们可以试想一下我们正在打扑克牌，我们的手里有一些有序的牌，而此时我们摸进来了一张牌。如果是你，你会怎么把牌插入牌堆里？

那么如图所示的这种算法，叫做直接排序算法。当然了，每个人打扑克的习惯都不一样啊，有的人习惯抓进一张牌就调整牌堆顺序了，而有些人习惯先把牌摸完，然后一起调整牌堆顺序。无论是哪一种，我们都可以统一思想。例如这个例子：

这就是直接插入排序的基本思想，用简单的说法就是：从第二个数开始依次往前面比较，碰到了特定条件就插入。了解了核心思想，现在就是考研我们打代码的人的素养了，将思路转换为代码。

#include 
#include 
#include 
#include 

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

//插入排序
void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;//记录从后向前比较的开始位置
		int tmp = a[end + 1];
		//当 end<0 时数组越界
		while (end >= 0)
		{
			//如果tmp比比较的数字小，那么数组就进行覆盖调整
			//我们的画图是让tmp移动，但是我们的代码是让数组移动
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//插入
		a[end + 1] = tmp;
	}
}

int main()
{
	//定义数组的大小
	int size = 10;
	int* arr = (int*)malloc(sizeof(int) * size);
	assert(arr);

	//给数组随机赋值
	srand((unsigned int)time(NULL));
	for (int i = 0; i < size; i++)
	{
		arr[i] = rand();
	}

	InsertSort(arr, size);
	Print(arr, size);
	return 0;
}
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

那么我们对随机的 10 个数字进行排序，可以看一下效果。实现了我们的排序功能。

那么我们可以在这里做一个总结：

• 如果数组是有序数组或者是接近有序数组，那么这个算法的效率会非常高
• 此排序算法的时间复杂度是 O(N^2)
• 空间复杂度是 O(1)

正因为这个算法的时间复杂度太高了，处理百万、千万往上的数据时效率是有明显的降低的。大家可以把上面的代码拷贝一份，修改一下主函数中的 size 变量的初始化值，观察效率。

而正式因为效率不够，就在直接插入排序的基础上，研究出了希尔排序算法。

3.希尔排序

希尔排序的思想非常简单，我们细细的想一下直接插入排序，每次比较都是挨个比较，那么我们如果不是挨个比较呢？我们以画图的形式来描述这个算法：

可以看到，希尔排序就是分段的直接插入排序。即分批次的进行直接插入排序。那么我们尝试用代码描述这个算法：

#include 
#include 
#include 
#include 

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

void ShellSort(int* a, int n)
{
	assert(a);
	int gap = n;//默认第一次的gap为n
	while (gap > 1)
	{
		gap /= 2;//依次减小区间，最后一次gap一定为 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;
		}
	}
}
int main()
{
	//定义数组的大小
	int size = 1000000;
	int* arr = (int*)malloc(sizeof(int) * size);
	assert(arr);

	//给数组随机赋值
	srand((unsigned int)time(NULL));
	for (int i = 0; i < size; i++)
	{
		arr[i] = rand();
	}

	//InsertSort(arr, size);
	ShellSort(arr, size);
	Print(arr, size);
	return 0;
}
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

可以看到我们要处理的数据很大，但是希尔排序能够处理这些庞大的数据。那么希尔排序一直有一个难题，那就是它的时间复杂度。希望有数学大佬能够把它计算出来。

所以希尔排序的效率是很高的，是效率跟堆排序差不多的排序算法。

4.直接选择排序

直接选择排序，我们选择什么呢？我们要选择最小、最大的数字放在指定的位置。我们看图来理解这个算法：

那么我们用代码来描述它也非常简单：

#include 
#include 
#include 
#include 

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


void Swap(int* p1, int* p2)
{
	assert(p1 && p2);
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	int maxi = begin;
	int mini = end;
	while (begin < end)
	{
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);

		//如果begin位置上放的是最大的数
		//那么就要改变一下maxi的位置
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}
int main()
{
	//定义数组的大小
	int size = 10;
	int* arr = (int*)malloc(sizeof(int) * size);
	assert(arr);

	//给数组随机赋值
	srand((unsigned int)time(NULL));
	for (int i = 0; i < size; i++)
	{
		arr[i] = rand();
	}

	//InsertSort(arr, size);
	//ShellSort(arr, size);
	SelectSort(arr, size);
	Print(arr, size);
	return 0;
}
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

选择排序可以称之为效率最差的排序排序算法之一了，因为它与直接插入排序不同的是，无论是否有序，选择排序的时间复杂度恒为 O(N^2)。

5.堆排序

堆排序这个算法是介绍过的，那这里就不做介绍了，单纯贴一份代码。

#include 
#include 
#include 
#include 

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


void Swap(int* p1, int* p2)
{
	assert(p1 && p2);
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(int* heap, int n, int parent)
{
	assert(heap);
	int minchild = parent * 2 + 1;
	while (minchild < n)
	{
		if (minchild + 1 < n && heap[minchild + 1] > heap[minchild])
		{
			minchild++;
		}
		if (heap[minchild] > heap[parent])
		{
			Swap(&heap[minchild], &heap[parent]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	assert(a);
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	while (n)
	{
		Swap(&a[0], &a[n - 1]);
		AdjustDown(a, n-1, 0);
		n--;
	}
}
int main()
{
	//定义数组的大小
	int size = 1000000;
	int* arr = (int*)malloc(sizeof(int) * size);
	assert(arr);

	//给数组随机赋值
	srand((unsigned int)time(NULL));
	for (int i = 0; i < size; i++)
	{
		arr[i] = rand();
	}

	//InsertSort(arr, size);
	//ShellSort(arr, size);
	//SelectSort(arr, size);
	HeapSort(arr, size);
	Print(arr, size);
	return 0;
}
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