• 归并排序与计数排序

    文章目录

    稳定性

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

    简单来说就是：两个数据的相对顺序排序完之后没有发生变化，排序算法就是稳定的；反之，则不稳定

    一、归并排序

    基本思想：

    归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
    Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有
    序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

    简单来说就是：取小的数据尾插到新数组，再将新数组数据对应拷贝回原来数组

    至于为什么不用链表尾插我们等下写出代码来就知道了

    归并排序核心步骤：
    在这里插入图片描述

    上图是为了我们更容易理解归并排序而画出来的，真正的过程应该是下面的图：
    在这里插入图片描述
    解析：tmp就是我们新开辟的数组。我们要将数据进行排序，归并排序的前提是原数据左半部分和右半部分都是有序的。如果没有序就进行递归处理，每次在中间位置截取开来，分为左子区间和右子区间两个部分（函数栈帧销毁后可以重复调用，所以不会栈溢出，所以空间复杂度最大为O(N)），依次递归下去。当递归到区间只有一个元素的时候（一次递归的左右区间相同），该元素就是有序的，递归返回有序数据到上一层之后开始进行归并

    递归方法

    按照上面解析我们通过递归展开图来看看

    代码：

    void _MergeSort(int* a, int begin, int end, int* tmp)//子函数
{
	if (begin >= end)
		return;
	int mid = (end + begin) / 2;//这里就是不用链表的原因，链表求这个mid中间值比较麻烦
	_MergeSort(a, begin, mid, tmp);//左区间递归
	_MergeSort(a, mid + 1, end, tmp);//右区间递归

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    数据：
    在这里插入图片描述
    递归展开图：
    在这里插入图片描述
    当我们到达最后一层都只有一个数据的时候，返回开始归并：

    if (begin >= end)
		return;
	int mid = (end + begin) / 2;//这里就是不用链表的原因，链表求这个mid中间值比较麻烦
	_MergeSort(a, begin, mid, tmp);//左区间递归
	_MergeSort(a, mid + 1, end, tmp);//右区间递归
	//进行归并
	int begin1 = begin;    int end1 = mid;
	int begin2 = mid + 1;  int 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, (end - begin + 1) * sizeof(int));
	//直接memcpy拷贝回原来数组，因为是递归完之后进行归并，所以目标位置和原位置要加上一个begin进行对应；记得乘以sizeof(int)

    • 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

    归并排序动图

    在这里插入图片描述

    特性

    归并排序的特性总结：

    1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
    2. 时间复杂度：O(N*logN)
    3. 空间复杂度：O(N)
    4. 稳定性：稳定

    有了上面的了解，再深入研究归并排序的非递归方法

    归并排序非递归方法

    我们先来看看情况1：给出的数据个数是2的整数倍
    这种情况我们先来解决，然后再来看看其他的情况
    在这里插入图片描述

    那么我们可以定义一个gap，gap依次翻倍增加。 每次两组两组比较，每组gap个数据。

    在这里插入图片描述
    代码：

    void MergeSortNonR(int* a, int n)//归并排序（非递归）
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)//下标不能越界
	{
		for (int j = 0; j < n; j += 2 * gap)//2*gap是因为每次两组两组归并，每组gap个数据，所以比完一次是处理完了2*gap个数据
		{
			int begin1 = j;        int end1 = j + gap - 1;//下标作为闭区间要减一
			int begin2 = j + gap;  int end2 = j + 2 * gap - 1;
			int i = j;
			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, tmp, (n) * sizeof(int));
			gap *= 2;//gap每次都翻一倍
		}
	}
	free(tmp);
	tmp = NULL;
}

    • 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

    在这里插入图片描述
    可以看到当数据个数是2的整数倍的时候，我们可以通过归并排序非递归的方法完成排序

    但是如果数据个数是奇数或者不是2的整数倍呢？
    如下图：

    在这里插入图片描述
    因为我们是按整数倍去算的，所以这两种情况下下标会越界：

    在这里插入图片描述
    所以我们在遇到这种情况是一定要就行判断的，然后采取修改措施

    我们来看看情况分为哪一些：
    在这里插入图片描述
    这里begin1不可能越界，因为begin1=j 在这里插入图片描述
    所以只用考虑三种情况：

    特殊的三种情况

    这里就是为什么不推荐使用整体拷贝，因为每一种特殊情况都要进行修改边界。所以我们每归并一个边界就拷贝回去一个边界

    情况1：end1越界

    if (end1 >= n)
{
	break;
}


    • 1
    • 2
    • 3
    • 4
    • 5

    如果end1越界了，那么就将begin1不进行归并了，直接拷贝回原数组

    情况2：begin2和end2越界

    if (begin2 >= n)
{
	break;
}


    • 1
    • 2
    • 3
    • 4
    • 5

    如果begin2和end2越界了，那么就将begin1和end1不进行归并了，直接拷贝回原数组

    情况3：end2越界

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

    • 1
    • 2
    • 3
    • 4

    如果end2越界了，那么让end2与begin2相等，也就是使右区间只有一个元素

    注意 !!!

    这里不能直接将边界全部修改为 n-1
    如果下标原本是【8，11】【12，15】
    现在被修改成为【8，8】【8，8】

    本来是【12，15】是越界不存在的空间，结果修改成【8，8】就表示区间存在了，平白无故多出来数据与前面数据就行归并。所以不能全部修改为n-1，要修改为一个不存在的区间，比如【9，8】这样的

    归并排序的完整代码

    void _MergeSort(int* a, int begin, int end, int* tmp)//子函数
{
	if (begin >= end)
		return;
	int mid = (end + begin) / 2;//这里就是不用链表的原因，链表求这个mid中间值比较麻烦
	_MergeSort(a, begin, mid, tmp);//左区间递归
	_MergeSort(a, mid + 1, end, tmp);//右区间递归
	//进行归并
	int begin1 = begin;    int end1 = mid;
	int begin2 = mid + 1;  int 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, (end - begin + 1) * sizeof(int));
	//直接memcpy拷贝回原来数组，因为是递归完之后进行归并，所以目标位置和原位置要加上一个begin进行对应；记得乘以sizeof(int)
}

void MergeSort(int* a, int n)//归并排序（递归）
{
	int* tmp = (int*)malloc(sizeof(int) * n);//写一个子函数进行递归，不然递归原函数会一直malloc开辟tmp
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}


void MergeSortNonR(int* a, int n)//归并排序（非递归）
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)//下标不能越界
	{
		for (int j = 0; j < n; j += 2 * gap)//2*gap是因为每次两组两组归并，每组gap个数据，所以比完一次是处理完了2*gap个数据
		{
			int begin1 = j;        int end1 = j + gap - 1;//下标作为闭区间要减一
			int begin2 = j + gap;  int end2 = j + 2 * gap - 1;
			if (end1 >= n)
			{
				break;
			}
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			printf("[%d,%d] [%d,%d]", begin1, end1, begin2, end2);
			int i = j;
			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 + j, tmp + j, (end2 - j + 1) * sizeof(int));//begin1改变了，所以减j
			
		}
		//memcpy(a, tmp, n * sizeof(int));//tmp = {6,10,1,7,3,9,2,4};这里归并完一整次把tmp中的数据拷贝回原数组
		//不推荐这种全部归并之后一起拷贝回去，因为遇到特殊情况都要修改边界，而归并一部分，拷贝
		//回去一部分可以减少修改边界的操作，更加方便
		gap *= 2;//gap每次都翻一倍
		printf("\n");//这里换行便于观看每次下标归并之后的情况
	}
	free(tmp);
	tmp = NULL;
}


    • 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
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109

    二、计数排序

    思想

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

    操作步骤：

    1. 统计相同元素出现次数
    2. 根据统计的结果将序列回收到原来的序列中

    在这里插入图片描述

    在这里插入图片描述

    特殊情况处理：相对映射
    在这里插入图片描述

    应用场景

    适合范围相对集中的数据就行处理

    我们来看看代码：

    void CountSort(int* a, int n)//计数排序
{
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (max < a[i])
			max = a[i];//找到最大值
		if (min > a[i])
			min = a[i];//找到最小值
	}
	int range = max - min + 1;//决定开辟多少个动态内存空间
	int* p = (int*)malloc(sizeof(int) * range);
	if (p == NULL)
	{
		perror("malloc fail\n");
	}
	memset(p, 0, sizeof(int) * range);
	for (int i = 0; i < n; ++i)
	{
		p[a[i] - min]++;//数据的出现次数存放在对应的动态开辟数组
	}
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		while (p[i]--)
		{
			a[j++] = i + min;//将记录的次数加上min就是原数据，依次打印出来
		}
	}
}


    • 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

    计数排序的特性总结

    1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
    2. 时间复杂度：O(MAX(N,范围))
    3. 空间复杂度：O(范围)
    4. .稳定性：稳定

    排序算法复杂度及稳定性分析

    在这里插入图片描述
    在这里插入图片描述

    总结

    其实排序算法还有很多的，比如：基数排序，桶排序，鸡尾酒排序…我们学不完的，所以只需要掌握主要使用的排序方法和思维即可。到目前为止，初阶数据结构就结束了，接下来我会慢慢更新c++的内容，包括后面的高阶数据结构和stl之类的内容。希望大家多多支持！我们下期见！

  • 相关阅读:
    Windows 下Tomcat监测重启
    datax扩展vertica插件
    求一个网页设计作业——个人博客(HTML+CSS)
    SpringBoot项目中只执行一次的任务写法
    八、【React-Router5】路由组件传参
    计算神经科学和人工智能,人工智能神经网络算法
    ant-design-vue Table pagination分页实现
    Matlab图像处理-Lab模型
    SQL引擎子系统的工作原理
    JS调用MetaMask调用启动转账
  • 原文地址：https://blog.csdn.net/kdjjdjdjjejje128/article/details/126782872