【初阶数据结构篇】归并排序、计数排序

熬夜学编程的小王

发布于 2024-11-20 20:36:40

2310

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

1. 归并排序

基本思想

归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divide andConquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。归并排序核⼼步骤：

1.1 分析

。归并排序：先递归，再合并的排序算法（分治法）

。对数组中第一个元素的下标和最后一个元素的下标进行分解，直至为最后一个元素，再进行合并

。合并思想：对两个数组的元素进行合并

注意：我们应另外创建一个数组存储排序后的结果，会覆盖原始数值。

1.2 代码：

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	//[left,mid] [mid+1,right]
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);


	//合并
	//[left,mid] [mid+1,right]
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else {
			tmp[index++] = arr[begin2++];
		}
	}
	//要么begin1越界但begin2没有越界  要么begin2越界但begin1没有越界
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}
	//[left,mid] [mid+1,right]
	//把tmp中的数据拷贝回arr中
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

复杂度分析时间复杂度：递归深度logn，对于每一层来说都是会把所有元素遍历一次，例如在递归第一层（二叉树第一层的函数栈桢）把原区间分为了两个区间，最后回归的时候就是合并两个有序数组，会把其中元素都遍历一次；其他层都同理为n，总计O(nlogn)。空间复杂度：递归深度logn，开辟n个元素的空间，为O(n)。

排序稳定性：很稳定

2. 计数排序（非比较排序）

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤

哈希直接定址法

取关键字的某个线性函数值作为散列地址：

直接定址法获取得到的散列函数有点就是简单，均匀也不会产生冲突 但问题是这需要事先知道关键字的分布情况 适合查找表较小且连续的情况 由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用

2.1 分析

步骤：

第一步，确定数组最大值和最小值，遍历
第二步，申请空间并初始化
第三步，统计每个数据出现的个数
根据申请的数组下标递增依次往原数组放数据

将对应下标加上min就是原始数据，数组下标对应的值出现几次就说明该数出现几次。

2.2 代码：

void CountSort(int* arr, int n)
{
	//根据最大值最小值确定数组大小
	int max = arr[0], min = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//初始化range数组中所有的数据为0
	memset(count, 0, range * sizeof(int));

	//统计数组中每个数据出现的次数
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	//取count中的数据，往arr中放
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}
}

复杂度分析
时间复杂度：找最大和最小值为N，统计个数也是遍历原数组为N，最后往原数组放数据，相当于遍历一次新数组为range，加上把N个数据放到原数组，所以总时间复杂度O(N+range)
空间复杂度：O(range)

特点：

计数排序在数据范围集中时，效率很⾼，但是适⽤范围及场景有限。

比如只能用来排整数数据。

3. 各排序性能比较

// 测试排序的性能对⽐
void TestOP()
{
	srand(time(0));
	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);

	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];
	}

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

	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();
	QuickSort(a5, 0, N - 1);
	//QuickSortNonR(a5, 0, N - 1);
	int end5 = clock();

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

	int begin8 = clock();
	CountSort(a8, N);
	int end8 = 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("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);
	printf("CountSort:%d\n", end8 - begin8);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
}