前言

数据结构的最后一部分了，排序也是在前面的数据结构的基础上来解决实际问题的。

排序

排序算法可以根据数据量的大小分为：

  • 内部排序：数据都在内存中
  • 外部排序：数据太多，无法全部存放在内存中

关于下述的各种排序算法是基于如下的方法结构来实现的：

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
#include <stdio.h>
#include <stdbool.h>
#define _CRT_SECURE_NO_WARNINGS
#define ElemType int	//存放的数据类型
#define MaxSize 10	//最大数组容量

//定义了新的List类型
typedef struct list {
	ElemType data[MaxSize];	//数据数组
	int num;	//数组的实际大小，即实际存放数据数量
}List;

//遍历输出List
void PrintList(List l) {
	printf("List数据为：");
	for (int i = 0; i < l.num; i++)
	{
		printf("%d ", l.data[i]);
	}
	printf("\n");
}

//创建List
bool CreatList(List* l) {
	printf("请输入数据：");
	int data, i = 0;
	scanf("%d",&data);
	while (data!=-999)
	{
		if (i>MaxSize-1)
		{
			printf("超出最大数组长度\n");
			return false;
		}
		l->data[i] = data;
		i++;
		scanf("%d", &data);
	}
	l->num = i;
	printf("List创建完成\n");
	return true;
}

内部排序

插入排序

插入排序算法的思想是对于某个要排序的序列，假定第一个元素已经是排完序的序列中，从第二个元素开始扫描，如果第二个元素大于第一个元素（升序），则不移动，反之则第一个和第二个元素交换位置，保证前面的比后面的小，依次类推，直到所有元素排序完成。代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//插入排序——升序
void InsertSort(List* l) {
	int j,temp = 0;	//j是移动前指针，temp用来存放正在比较的元素
	for (int i = 1; i < l->num; i++)
	{
		j = i-1;	
		temp = l->data[i];	//当前扫描到的要排序元素的值
		//如果扫描到的值比它前面的值小或者等于
		while(temp < l->data[j])
		{
			//则将其前面值向后移动一位
			l->data[j+1] = l->data[j];
			//直到前面的值没有比他大的了
			j--;
		}
		//将正在比较的元素放到新的位置
		l->data[j + 1] = temp;
	}
}

测试代码：

1
2
3
4
5
6
7
int main() {
	List l;	//声明List
	CreatList(&l);	//创建List
	PrintList(l);	//输出List现在的内容（未排序）
	InsertSort(&l);	//进行插入排序
	PrintList(l);	//输出排序后的List内容
}

运行结果：

image-20220905110158101

稳定性：稳定

希尔排序

希尔排序是插入排序的优化版本，它通过引入增量来减少插入排序遍历的次数。如下图所示：

image-20220906190855924

上图采用增量 4 ，则意味着第一轮将序号 (0,4),(1,5)等每个括号看成一个单独的序列采用插入排序，即增量 4 这轮，排序结果为下图所示：

image-20220906191115941

然后再对增量不断做 $d(增量) = \frac{d(增量)}{2}$ 直到增量为 1，也就是变成了普通的插入排序。

其代码实现如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//希尔排序——升序(递归) inc表示增量
void ShellSort(List* l,int inc) {
	int tempdata,j;	//临时数据变量，临时标识
	//只要增量大于1就一直执行
	while (inc>=1)
	{
		for (int i = 0; i < l->num-inc; i++)
		{
			j = i;	
			tempdata = l->data[i + inc];
			//当标识大于0并且后面增量数据小于前面的数据
			while (l->data[j]> l->data[j + inc]&& j>0)
			{
				//交换数据
				l->data[j + inc] = l->data[j];
				l->data[j] = tempdata;
				//向前比较到小于0就标识前面同一个增量内的比较完了
				j = j - inc;
			}
		}
		inc = inc / 2;	//每次增量减半
	}
}

运行测试：

1
2
3
4
5
6
7
int main() {
	List l;	//声明List
	CreatList(&l);	//创建List
	PrintList(l);	//输出List现在的内容（未排序）
	ShellSort(&l,4);	//希尔排序
	PrintList(l);	//输出排序后的List内容
}

运行结果：

image-20220906200537472

稳定性：不稳定

冒泡排序

冒泡排序故名思意，通过将两个数据两个数据的比较，每次将一个最大/最小值“运送”到排序队列的队头，依次“运送”，直到所有的数都被“运送”完成了；在这个过程中，将一个最大/最小值“运送”就类似于冒泡一样，一步一步上升。代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//冒泡排序——升序
void BubbleSort(List* l) {
	int tempdata, j = 0;
	while (j<l->num-1)
	{
		for (int i = l->num-1; i > j; i--)
		{
			tempdata = l->data[i];
			if (tempdata<l->data[i-1])
			{
				l->data[i] = l->data[i - 1];
				l->data[i - 1] = tempdata;
			}
		}
		j++;
	}
}

运行测试：

1
2
3
4
5
6
7
int main() {
	List l;	//声明List
	CreatList(&l);	//创建List
	PrintList(l);	//输出List现在的内容（未排序）
	BubbleSort(&l);	//冒泡排序
	PrintList(l);	//输出排序后的List内容
}

运行结果：

image-20220906200315949

稳定性：稳定

快速排序

快速排序顾名思义，是排序算法中最快的排序方式。

快速排序通过选择一个基准元素（默认第一个元素），使用两个指针low和high分别指向数组最低位和最高位，分别和基准元素进行比较，向中间靠拢，直到low大于等于high表示一次排序结束。再使用分好的左右两列，再次进行快速排序，最后完成排序。

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
//序列划分
int Partition(List* l, int low, int high) {
	int tempdata = l->data[low];	//tempdata作为基准元素
	while (low < high)
	{
		while (low < high && l->data[high] >= tempdata)
		{
			high--;
		}
		l->data[low] = l->data[high];
		while (low < high && l->data[low] < tempdata)
		{
			low++;
		}
		l->data[high] = l->data[low];
	}
	l->data[low] = tempdata;
	return low;
}

//快速排序——升序
void QuickSort(List* l,int low,int high) {
	int pivotops;
	if (low<high)
	{
		pivotops = Partition(l, low, high);
		QuickSort(l, low, pivotops - 1);
		QuickSort(l, pivotops + 1,high);
	}
}

运行测试：

1
2
3
4
5
6
7
int main() {
	List l;	//声明List
	CreatList(&l);	//创建List
	PrintList(l);	//输出List现在的内容（未排序）
	QuickSort(&l,0,l.num-1);	//快速排序
	PrintList(l);	//输出排序后的List内容
}

运行结果：

image-20220906213631740

稳定性：不稳定

简单选择排序

简单选择排序，也就是我们最简单常用的排序，即遍历获得最小值存入排序序列，然后再遍历最小值存入，依次反复，直到所有关键字都被排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//简单选择排序——升序
void SelectSort(List* l) {
	int tempdata,index, j=0;
	for (int i = 0; i < l->num-1; i++)
	{
		tempdata = l->data[i];
		index = i;
		j = i + 1;
		for (j; j < l->num; j++)
		{
			if (l->data[j]<tempdata)
			{
				tempdata = l->data[j];
				index = j;
			}
		}
		l->data[index] = l->data[i];
		l->data[i] = tempdata;
	}
}

测试代码：

1
2
3
4
5
6
7
int main() {
	List l;	//声明List
	CreatList(&l);	//创建List
	PrintList(l);	//输出List现在的内容（未排序）
	SelectSort(&l);	//快速排序
	PrintList(l);	//输出排序后的List内容
}

运行结果：

image-20220906221059999

稳定性：不稳定

堆排序

堆

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete[1] tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.[2] The node at the “top” of the heap (with no parents) is called the root node.

内容来源：【Wiki百科】Heap (data structure)

堆（Heap），是一种树类型的数据结构，根据其排序特性可以分为：

  • 大根堆：若满足 $L(i) \geq L(2i)$ 且 $L(i) \geq L(2i+1)$ （$1 \leq i \leq \frac{n}{2}$）
  • 小根堆：若满足 $L(i) \leq L(2i)$ 且 $L(i) \leq L(2i+1)$ （$1 \leq i \leq \frac{n}{2}$）

大根堆的建立

image-20220907170111338

大根堆的示例如上所示，其代码实现如下：

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
//其存储结构和排序的List是同一个，只是我多给它命名了一个名称用来区分
typedef struct list {
	ElemType data[MaxSize];
	int num;
}List,Heap;

//建立大根堆（根据传入的List数组再调整大根堆）
void CreatHeap(Heap* h) {
	int tempdata;	//临时最大值变量位置
	for (int i = (h->num/2)-1; i >= 0 ; i--)
	{
		tempdata = 2 * i + 1;
		//如果存在右子树，判断右子树和左子树哪个大
		if (2*i + 2 <= h->num-1)
		{
			if (h->data[2*i+1]<h->data[2*i+2])
			{
				tempdata = 2 * i + 2;
			}
		}
		//根结点小于子结点
		if (h->data[i]<h->data[tempdata])
		{
			if (2*i+2==tempdata)
			{
				tempdata = h->data[2 * i + 2];
				h->data[2 * i + 2] = h->data[i];
			}
			else
			{
				tempdata = h->data[2 * i + 1];
				h->data[2 * i + 1] = h->data[i];
			}
			h->data[i] = tempdata;
		}
	}
	//PrintList(*h);	//这行代码实际执行过程不必执行，只是调试的时候查看实时的调整过程
}

堆排序

现在利用上面建立好的大根堆来排序，每次将最开始的元素（即大根堆的根）和大根堆最后一个元素互换位置，然后再对更换位置后除了最后一个元素，进行大根堆建立，建立成新的大根堆后，其新的根一定是最大值，也通之前一样，将其换到新大根堆的最后（实际数组的导数第二个），依次类推，直到完成整个大根堆的排序。代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//堆排序——升序
void HeapSort(Heap* h) {
	int tempdata,j=0,num = h->num-1;
	while (j<num)
	{
		tempdata = h->data[0];	//获取堆顶值，即最大值
		h->data[0] = h->data[h->num -1];	//将最后一位元素换到堆顶
		h->data[h->num - 1] = tempdata;;	//最大值，即原来堆顶换到最后
		h->num--;	//将堆的长度-1
		CreatHeap(h);	//将置换后的堆重新整理成堆
		j++;
	}
	h->num = j+1;	//最后将堆的实际数量复原，因为后序遍历显示堆排序结果的方法需要使用堆的数量
	printf("堆排序完成\n");
}

测试代码：

1
2
3
4
5
6
7
8
9
int main() {
	List l;	//声明List
	CreatList(&l);	//创建List
	PrintList(l);	//输出List现在的内容（未排序）
	CreatHeap(&l);	//建立大根堆
	PrintList(l);	//输出List现在的内容（未排序）
	HeapSort(&l);	//进行堆排序
	PrintList(l);	//输出排序后的List内容
}

测试结果：

image-20220907171009211

稳定性：不稳定

归并排序

归并排序是可以将多个数组（排序好的）来合并成一个排序的新数组，根据合并的数组数目可以分为：二路归并，三路归并等，一般情况下我们都以二路归并为默认。因为归并其递归特性，所以我们在对数组进行排序的时候，可以数组看作又每个单个元素组成的“单个元素数组”，然后对其使用并归排序，这样就完成了整个并归排序。其过程如下图所示：

image-20220907171530940

图片来源：王道《数据结构》

代码示例：

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
//归并排序——升序
void Merge(List* l,int low,int mid,int high) {
	int* copy[MaxSize];	//创建辅助数组
	int i, j, k;	//i表示辅助数组的low指针，j表示辅助数组的mid下一个指针即两路合并的第二路开始指针，K表示要将最小的数放在原排序序列的哪里
	for (int i = 0; i < l->num; i++)
	{
		copy[i] = l->data[i];	//将要排序的数组复制一份给辅助数组
	}
	for (i = low,j=mid+1,k=low; i <= mid && j<=high; k++)
	{
		if (copy[i]<copy[j])
		{
			l->data[k] = copy[i];	//最小值的放回原数组
			i++;
		}
		else
		{
			l->data[k] = copy[j];	//最小值的放回原数组
			j++;
		}
	}
	/// 如果最后发现两路数组其中剩下一组没有比较完，则按顺序一次放入即可
	while (i<=mid)
	{
		l->data[k] = copy[i];
		k++;
		i++;
	}
	while (j <= high)
	{
		l->data[k] = copy[j];
		k++;
		j++;
	}
}

//归并排序——升序
void MergeSort(List* l, int low, int high) {
	if (low < high)
	{
		int mid = (low + high) / 2;	//求Mid值	
		MergeSort(l, low, mid);	//先排序并并归左半边
		MergeSort(l, mid + 1, high);	//再排序并并归右半边
		Merge(l, low, mid, high);	//最后完成并归
	}
}

测试代码：

1
2
3
4
5
6
7
int main() {
	List l;	//声明List
	CreatList(&l);	//创建List
	PrintList(l);	//输出List现在的内容（未排序）
	MergeSort(&l, 0, l.num);	//并归排序
	PrintList(l);	//输出List现在的内容（未排序）
}

运行结果：

image-20220908105037724

稳定性：稳定

基数排序

例如下图的序列进行排序，我们可以通过先进行个位排序，再进行十分位排序，再进行百分位排序，完成最终的排序。有点迭代的思想，个位的排序可以让其在个位有先后，十分位排序在个位有序的基础上让其十分位有序，然后百分位在个位和十分位有序的基础上，再让百分位有序就完成整个排序。

image-20220908105411196

图片来源：王道《数据结构》

外部排序

外部排序，是因为我们有时候处理的数据量太大而导致不可能一次性将其装入内存进行处理，这个时候就要利用内存和外存的交换来完成排序，这个过程就是外部排序。

外部排序逻辑如下所示，通过将每一块磁盘块或者说数据块从一块一块开始利用归并排序，排序好一块就写入外存，直到完成整个外存的排序。

image-20220908145249849

图片来源：王道《数据结构》

优化外部排序

因为归并排序的特性可以知道，随着开辟的内存缓冲区越多，即归并段同时归并的越多，对磁盘的读写越少，同时就减少了排序时间。需要注意的是这个归并段并不是可以无线增大的，因为内存缓冲区开辟的越多，对于内存的开销也就越大。内存中排序所需要消耗的时间也会增加。如下图所示：

image-20220908145824801

图片来源：王道《数据结构》

即优化方向：

  • 增加归并路数
  • 减少初始归并段数量

败者树

因为增加归并路数可以一定程度优化排序所消耗的时间，但是带来的问题是：K路的归并，意味着每次取得最小值/最大值就需要进行 $K-1$ 次的对比。

image-20220908150304017

图片来源：王道《数据结构》

败者树就是我们常规所理解的比赛的层级方式，通过败者树可以缩短比较关键词的次数，进而缩短排序时间。

如下图所示，在第一次归并的时候进行 $K-1$ 次归并计算出败者树，在非叶子结点其数值指向归并段的位置，即第一次归并得到其最小值来自归并段3号，其中的第一个元素 1 是最小值，写入排序序列即可。

image-20220908150632953

图片来源：王道《数据结构》

接下来，再从归并段冠军中获取下一个元素，进行比较，如下图所示：

因为第一次的时候就已经得到败者树，所以新元素只需要根据败者树路径比较即可，不必要和每个元素再次进行比较，这样可以有限的缩短比较次数。一次类推。知道所有元素比较完成。

image-20220908150951704

图片来源：王道《数据结构》

置换-选择排序

通过置换置换-选择排序可以利用有限的内存空间，构建更长的归并段，其实现过程如下：

如下图，内存只能开辟如下三个数据的空间，通过每次将其中的最小值写入归并段1，并记录其值在变量MiniMax中，然后从外存中将新的数值填充到内存中替代换出去的位置，再从中选择比变量MiniMax大但是又是其中最小的值，并写入归并段，再将变量MiniMax记录为新的值，如此反复。

image-20220908151443421

图片来源：王道《数据结构》

直到内存工作区的三个记录值都小于MiniMAX的值，则意味着第一个归并段完成了，再从此记录第二个归并段，一次就可以记录完成所有的排序序列分成长度不等的归并段。

image-20220908152020828

最佳归并树

我们通过置换-选择排序，最终利用有限的内存，获得了不同长度的归并段，如下图，因为长度不同的归并段，每次需要读写磁盘的次数不同，造成其消耗的时间不同，下图中的R1,R2,R3...表示归并段，其结点数据表示读写磁盘次数，因为结点带有权值，不难想到前面树的部分的哈夫曼树，构建最优带权路径长度，来减少对磁盘的读写，最终减少排序时间。

image-20220908153452400

End

路漫漫其修远兮，所以，开摆！！！

image-20220908154157719