【初阶数据结构】星河中的光影 “排” 象：排序（下）

DARLING Zero two

发布于 2025-02-26 08:53:54

4900

代码可运行

文章被收录于专栏：C语言C语言

运行总次数：0

代码可运行

接上一篇，解决掉剩余的排序方法，本篇有些许难度，建议巩固好上一篇再来进行本篇的学习

传送门：【初阶数据结构】星河中的光影 “排” 象：排序（上）

4.交换排序

4.1 冒泡排序（BubbleSort）

基本思想： 所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

冒泡排序在C语言部分进行过详细的解析，这里就不过多赘述

传送门：关于我、重生到500年前凭借C语言改变世界科技vlog.14——常见C语言算法

4.2 快速排序（QuickSort）

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

4.2.1 hoare版本

动图理解：

💻排序实现：

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left, end = right;

	//随机选key
	int randi = left + (rand() % (right - left + 1));
	Swap(&a[left], &a[randi]);

	//三数取中
	//int midi = GetMidNumi(a, left, right);
	//Swap(&a[midi], &a[left]);

	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
			--right;

		//左边找大
		while (left < right && a[left] <= a[keyi])
			++left;

		Swap(&a[left], &a[right]);
	}
		Swap(&a[keyi], &a[left]);
		keyi = left;

		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
}

⌨️代码解读：

if (left >= right)，如果左边界大于等于右边界，说明子数组已经有序或为空，直接返回
随机选 key
当左边界小于右边界时，继续分区操作。右边找小，从右向左找到第一个小于基准元素的元素；左边找大，从左向右找到第一个大于基准元素的元素。交换左右找到的元素
最后将基准元素放到正确的位置，更新基准元素的索引
此时基准元素所放置的位置就是正确的排序位置，基准元素左右两边任然无序，所以对左右两边进行循环操作，每循环一次就确定一个数的位置

🔥值得注意的是：

选取 key 的方式有三种

选第一个数为 key
三数取中值

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[left] > a[right])
			return left;
		else if (a[mid] < a[right])
			return mid;
		else
			return right;
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])
			return left;
		else
			return right;
	}
}

随机选 key，经过算法研究发现该选 key 方式是最有效的

4.2.2 挖坑法

动图理解：

💻排序实现：

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left, end = right;

	//随机选key
	int randi = left + (rand() % (right - left + 1));
	Swap(&a[left], &a[randi]);

	//三数取中
	//int midi = GetMidNumi(a, left, right);
	//Swap(&a[midi], &a[left]);

	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= key)
			--right;

		a[hole] = a[right];
		hole = right;

		//左边找大
		while (left < right && a[left] <= key)
			++left;

		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;

	QuickSort2(a, begin, hole - 1);
	QuickSort2(a, hole + 1, end);
}

⌨️代码解读：

选择左边界元素作为基准元素 key，并将其位置标记为 hole（坑）
从右向左扫描，找到第一个小于 key 的元素，将其填入 hole 位置，并更新 hole 为该元素的位置。
从左向右扫描，找到第一个大于 key 的元素，将其填入 hole 位置，并更新 hole 为该元素的位置。
不断重复上述两个步骤，直到 left 和 right 相遇。
最后将基准元素 key 填入最终的 hole 位置

🔥值得注意的是： 在从右向左查找小于 key 的元素时，right 指针会不断向左移动。如果不添加 left < right 这个条件，right 指针可能会一直向左移动，越过 left 指针，导致访问到数组范围之外的元素，从而引发越界错误。例如，当数组中的元素都大于等于 key 时，如果没有 left < right 的限制，right 指针会一直向左移动，最终可能访问到数组的负索引位置，这是不合法的。从左向右查找大于 key 的元素也是同理

4.2.3 前后指针法

动图理解：

💻排序实现：

void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;

	int randi = left + (rand() % (right - left + 1));
	Swap(&a[left], &a[randi]);

	//定义基准值以及cur和dest
	int keyi = left;
	int dest = left, cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++dest != cur)
		{
			Swap(&a[cur], &a[dest]);
		}
		//无论cur位置的值是否小于基准值，cur都要++，所以留到这里做调整
		cur++;
	}
	Swap(&a[keyi], &a[dest]);
	QuickSort3(a, left, dest - 1);
	QuickSort3(a, dest + 1, right);
}

⌨️代码解读：

keyi 是基准元素的索引，初始化为左边界 left，dest 指针用于标记小于基准元素的元素应该放置的位置，初始化为左边界 left，cur 指针用于遍历数组，初始化为 left + 1
如果 cur 位置的值小于基准值，要和 dest 后面的元素进行交换，但是有可能 dest 后面就是 cur，所以我们可以让 dest 先 ++ ，再和 cur 比较，如果 ++dest == cur，说明它们暂时指向同一个元素，无需交换；如果 ++dest != cur，说明它们不指向同一个元素，直接交换

🖱️复杂度分析：

• 时间复杂度：

○ 最好情况： 当每次选择的基准元素都能将数组均匀地分成两部分时，递归树的深度为 log n ，每层需要处理的元素总数为 n，因此总的时间复杂度为 O(n * log n)

○ 最坏情况： 最坏情况下，快速排序的时间复杂度会退化为 O(n²)

○ 平均情况： 时间复杂度为 O(n * log n)

• 空间复杂度： 时间复杂度为 O(log n)

总结： 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

4.2.4 非递归实现

因为上面的三种方法均涉及递归，考虑到递归太多数据会导致栈溢出的风险，所以非递归实现快排也很重要

那么根据我们学过的栈发现其原理：先进后出，比较符合我们排序的效果

这里我们引入栈的头文件和源文件

传送门：【初阶数据结构】先来后到的秩序：栈和队列

💻排序实现：

int PartSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int randi = left + (rand() % (right - left + 1));
	Swap(&a[left], &a[randi]);

	int keyi = left;
	int dest = left, cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++dest != cur)
		{
			Swap(&a[cur], &a[dest]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[dest]);
	return dest;
}

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort(a, begin, end);

		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

⌨️代码解读：

将初始的排序区间 [left, right] 压入栈中。注意，先压入右边界 right，再压入左边界 left，后续出栈时会先得到左边界，符合后续处理逻辑
从栈中弹出一个区间 [begin, end]，先弹出的是左边界 begin，再弹出右边界 end
调用 PartSort 函数对当前区间 [begin, end] 进行分区操作，得到基准元素的最终位置 keyi
根据基准元素的位置 keyi，将左右子区间压入栈中。如果基准元素右边还有元素（keyi + 1 < end），则将右子区间 [keyi + 1, end] 压入栈；如果基准元素左边还有元素（begin < keyi - 1），则将左子区间 [begin, keyi - 1] 压入栈。这样后续会继续对这些子区间进行排序

🔥值得注意的是： 非递归的方式本质上就是借助栈来存区间，然后 PartSort(a, begin, end) 会对数进行交换排序，进行实质的交换

5.归并排序（MergeSort）

5.1 递归实现

动图理解：

假设有这么个区间，两个有序区间，就是不断对两个移动指针比较，把较小的数插入到新空间，形成新的有序序列，然后再赋值回原来的空间

💻排序实现：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

⌨️代码解读：

计算中间索引 mid，将当前数组分成两个子数组，分别递归调用 _MergeSort 函数对左右子数组进行排序，从最下面的子数组依次往上归并
初始化两个指针 begin1 和 begin2 分别指向左右子数组的起始位置，end1 和 end2 指向左右子数组的结束位置
比较 a[begin1] 和 a[begin2] 的大小，将较小的元素放入临时数组 tmp 中，并将相应的指针后移
当其中一个子数组遍历完后，将另一个子数组中剩余的元素依次放入临时数组 tmp 中
使用 memcpy 函数将临时数组 tmp 中排好序的元素复制回原数组 a 中

🔥值得注意的是： memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1))，而不是 memcpy(a, tmp, sizeof(int) * (end - begin + 1))，为了在临时数组中准确找到当前子数组合并结果的起始位置，以便将排好序的数据正确地复制回原数组

5.2 非递归实现

同理，为了避免栈溢出，归并排序也有非递归实现

为什么不用栈处理？

栈的非递归实现其实是类似于前序遍历的，而归并的非递归实现类似于后序遍历

💻排序实现：

5.2.1 一次性全部拷贝回去：memcpy(a, tmp, sizeof(int) * n)

void MergeSortNonR1(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			if (end1 >= n)
			{
				end1 = n - 1;
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a, tmp, sizeof(int) * n);
		}
		gap *= 2;
	}
	free(tmp);
}

⌨️代码解读：

gap 表示一组有多少个数据，gap = 1 时一个一个归并，gap = 2 时两个两个归并，依次向后推，不断扩大 gap 实现有序

根据规律写出 int begin1 = i, end1 = i + gap - 1；int begin2 = i + gap, end2 = i + 2 * gap - 1；

但是我们发现这套规律只适用于偶数个数的归并，当为奇数时会出现`多出来一个数无法进行归并的情况，所以我们要针对这种情况进行修正

end1 越界示例 假设我们有一个长度 n = 5 的数组 arr = [1, 2, 3, 4, 5]，当 gap = 4 时，开始进行合并操作

计算过程：

当 i = 0 时：begin1 = i = 0，end1 = i + gap - 1 = 0 + 4 - 1 = 3，这是正常的，因为数组索引 3 在有效范围内（数组索引范围是 0 到 4）

当 i = 4 时：begin1 = i = 4，end1 = i + gap - 1 = 4 + 4 - 1 = 7，而数组的最大有效索引是 4，此时 end1 超出了数组的边界，出现越界情况

修正方法： end1 = n - 1，begin2 = n，end2 = n - 1，因为是整体赋值，让有效的数据按原路返回，后面的修正为一个不存在的区间，也就不会归并了，那么就有个问题，后面的数不就无序了吗？其实前面的排序保证了其有序性，在 gap 进一步扩大的过程中会将其逐步变为有序

begin2 越界示例 同样使用长度 n = 5 的数组 arr = [1, 2, 3, 4, 5]，当 gap = 3 时进行分析

计算过程：

当 i = 2 时：begin1 = i = 2，end1 = i + gap - 1 = 2 + 3 - 1 = 4，这是正常的，begin2 = i + gap = 2 + 3 = 5，数组的最大有效索引是 4，所以 begin2 超出了数组的边界，出现越界情况

修正方法： 同 end1 越界处理情况相同

end2 越界示例

还是以长度 n = 5 的数组 arr = [1, 2, 3, 4, 5] 为例，当 gap = 3 时进行分析

计算过程：

当 i = 0 时：begin1 = i = 0，end1 = i + gap - 1 = 0 + 3 - 1 = 2，begin2 = i + gap = 0 + 3 = 3，end2 = i + 2 * gap - 1 = 0 + 2 * 3 - 1 = 5，数组的最大有效索引是 4，所以 end2 超出了数组的边界，出现越界情况

修正方法： end2 = n - 1，将有效数据纳入进行排序，剩余的数在 gap 扩大时会得到处理

5.2.2 分批次拷贝回去：memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1))

void MergeSortNonR2(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}

⌨️代码解读：

一次性拷贝回去需要调整 end1、begin1 等边界：

一次性拷贝回去意味着我们要把合并好的结果一次性从临时数组 tmp 复制回原数组 a。在这个过程中，如果出现越界情况，比如 end1 或 end2 超出了数组长度，我们需要调整这些边界，以确保只处理有效的数组元素，避免访问非法内存

分批次拷贝回去直接 break：

分批次拷贝回去通常是指在发现越界情况时，由于后续没有有效的子数组可供合并，直接终止当前的合并操作，等待下一轮更大的 gap 再处理剩余元素。这种方式简化了越界处理逻辑，因为不需要对越界的边界进行复杂的调整

end1、begin2 越界： break，等待 gap 增大时处理未处理的数据

end2 越界： 和一次性拷贝的处理相同

🔥值得注意的是： memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)) 不能写成 memcpy(a + begin1, tmp + begin1, sizeof(int) * (end2 - begin1 + 1))，因为 begin1 被移动了，i 才是原来的初始位置

6.排序复杂度及效率对比

💻测试代码：

void TestOP()
{
	srand(time(NULL));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);
	int* a9 = (int*)malloc(sizeof(int) * N);
	int* a10 = (int*)malloc(sizeof(int) * N);
	int* a11 = (int*)malloc(sizeof(int) * N);
	int* a12 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
		a9[i] = a1[i];
		a10[i] = a1[i];
		a11[i] = a1[i];
		a12[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort1(a5, 0, N - 1);
	int end5 = clock();

	int begin8 = clock();
	QuickSort2(a8, 0, N - 1);
	int end8 = clock();

	int begin9 = clock();
	QuickSort3(a9, 0, N - 1);
	int end9 = clock();

	int begin10 = clock();
	QuickSortNonR(a9, 0, N - 1);
	int end10 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	int begin11 = clock();
	MergeSortNonR1(a11, N);
	int end11 = clock();

	int begin12 = clock();
	MergeSortNonR1(a12, N);
	int end12 = clock();

	int begin7 = clock();
	BubbleSort(a7, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("BubbleSort:%d\n", end7 - begin7);
	printf("QuickSort1:%d\n", end5 - begin5);
	printf("QuickSort2:%d\n", end8 - begin8);
	printf("QuickSort3:%d\n", end9 - begin9);
	printf("QuickSortNonR:%d\n", end10 - begin10);
	printf("MergeSort:%d\n", end6 - begin6);	
	printf("MergeSortNonR1:%d\n", end11 - begin11);
	printf("MergeSortNonR2:%d\n", end12 - begin12);


	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
	free(a9);
	free(a10);
	free(a11);
	free(a12);
}

⌨️测试结果：