【数据结构初阶】八大排序(三)——归并排序&&计数排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构初阶】八大排序(三)——归并排序&&计数排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

大家好我是沐曦希💕

往期博客：【数据结构初阶】八大排序(一)——希尔排序&&堆排序&&直接插入排序&&直接选择排序
【数据结构初阶】八大排序(二)——快速排序&&冒泡排序

1.归并排序(递归)

1.1 基本思想

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

1.2 具体思路

第一步：递归分解数组。通过递归将数组a分解成n个数组，其中每个数组只有一个元素，类似与二叉树。那么此时每个数组都是有序的，那么就可以进行归并。例如:
【数据结构初阶】八大排序(三)——归并排序&&计数排序
第二步：将上述的n个数组，进行相邻两两数组的全部元素进行比较，创建一个新的数组tmp，数组tmp大小和数组a的大小相同。取小的尾插进数组tmp,将两个数组中剩余元素尾插进入数组tmp。
(当数组元素不为奇数)进行一次归并后，每个数组的元素为两个，那么继续相邻的两个数组进行元素比较，取小的尾插到tmp，最后将两个数组中剩余元素尾插进入数组tmp。
(当数组元素个数为2^n)此时每个数组的元素个数为四个，继续按照上面步骤直到数组有序。
【数据结构初阶】八大排序(三)——归并排序&&计数排序

第三步，最后将数组tmp的元素拷贝回原数组a–归并哪了部分就拷贝哪部分回原数组a。

memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));

归并排序的动图
【数据结构初阶】八大排序(三)——归并排序&&计数排序
因为需要分解和比较元素大小，那么可以创建三个变量left,mid,right。将数组分解成[left,mid] [mid+1,right]继续进行递归直到每个数组元素只有一个。

此时要解决边界的问题：即数组一的left1是left,right1是mid。
数组二的left2是mid+1,right2是right。

比较大小

while (left1 <= right1 && left2 <= right2)
{
	if (a[left1] <= a[left2])
			tmp[i++] = a[left1++];
	else
			tmp[i++] = a[left2++];
}
while (left1 <= right1)
	tmp[i++] = a[left1++];
while (left2 <= right2)
	tmp[i++] = a[left2++];

1.2 代码

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (right - left) / 2 + left;
	//[left,mid] [mid+1,right]
	//递归将数组分成n个数组--类似二叉树
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);
	//归并一趟
	int left1 = left, right1 = mid;
	int left2 = mid + 1, right2 = right;
	int i = left;
	while (left1 <= right1 && left2 <= right2)
	{
		if (a[left1] <= a[left2])
			tmp[i++] = a[left1++];
		else
			tmp[i++] = a[left2++];
	}
	while (left1 <= right1)
		tmp[i++] = a[left1++];
	while (left2 <= right2)
		tmp[i++] = a[left2++];
	//拷贝回原数组--归并哪部分就拷贝哪部分回原数组
	memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);
}

1.3 特性总结

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

时间复杂度：O(N*logN)

空间复杂度：O(N)

稳定性：稳定

排序性能对比

void testOp()
{
	srand((unsigned int)time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	assert(a1);
	int* a2 = (int*)malloc(sizeof(int) * N);
	assert(a2);
	int* a3 = (int*)malloc(sizeof(int) * N);
	assert(a3);
	int* a4 = (int*)malloc(sizeof(int) * N);
	assert(a4);
	int* a5 = (int*)malloc(sizeof(int) * N);
	assert(a5);
	int* a6 = (int*)malloc(sizeof(int) * N);
	assert(a6);
	int* a7 = (int*)malloc(sizeof(int) * N);
	assert(a7);
	
	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];
	}
	
	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();
	//BubbleSort(a5, N);
	int end5 = clock();
	
	int begin6 = clock();
	QuickSort(a6, 0, N - 1);
	int end6 = clock();
	
	int begin7 = clock();
	MergeSort(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", end5 - begin5);
	printf("QuickSort:%d\n", end6 - begin6);
	printf("MergeSort:%d\n", end7 - begin7);
	
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
	a1 = NULL;
	a2 = NULL;
	a3 = NULL;
	a4 = NULL;
	a5 = NULL;
	a6 = NULL;
	a7 = NULL;
}

【数据结构初阶】八大排序(三)——归并排序&&计数排序
当N为1000000时

2.归并排序(非递归)

2.1 具体思路

非递归的基本思路和递归类似，不同的是非递归通过创建一个新变量gap来进行分解数组。
gap可以从1或者2开始分解数组，当每个数组元素都为1或者2时，进行归并。此时数组元素个数变成2或者4，gap就增大一倍，继续归并。
重复以上步骤直到数组有序。
【数据结构初阶】八大排序(三)——归并排序&&计数排序
要注意的是：
1.数组个数不一定是整数倍，上面计算时候直接按照整数倍算的，存在数组越界的情况，需要我们修正一下数组边界。

//第一组部分越界
if (end1 >= n)
	break;
//第一组不越界，第二组全部越界
if (begin2 >= n)
	break;
//第二组部分越界
if (end2 >= n)
	end2 = n - 1;

2.因为有奇数情况，所以要归并完哪部分数组就拷贝回哪部分数组回原数组。

2.3 代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void MergeSortNOR(int* a, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	int j = 0;
	while (gap < n)
	{
		for (j = 0; j < n; j += 2 * gap)
		{
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = j + 2 * gap - 1;
			//需要调整边界
			//第一组部分越界
			if (end1 >= n)
				break;
			//第一组不越界，第二组全部越界
			if (begin2 >= n)
				break;
			//第二组部分越界
			if (end2 >= n)
				end2 = n - 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 + j, tmp + j, (end2 - j + 1) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
	tmp = NULL;
}
int main()
{
	int a[] = { 10,6,7,1,3,9,4,2,8 };
	int sz = sizeof(a) / sizeof(a[0]);
	MergeSortNOR(a, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

【数据结构初阶】八大排序(三)——归并排序&&计数排序

3.非比较排序——计数排序

3.1 基本思想

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

统计相同元素出现次数

根据统计的结果将序列回收到原来的序列中

【数据结构初阶】八大排序(三)——归并排序&&计数排序
优化：可以采用相对映射，即遍历一遍数组，找最小和最大的，开辟最大-最小+1个int空间。(由此可见计数排序不适合浮点数)，然后每次元素计数时候，用该元素-最小的所得的数即为该元素的下标，该下标进行++。排序时候，用下标加上最小值。
负数也可以采用计数排序。

计数排序的动图：
【数据结构初阶】八大排序(三)——归并排序&&计数排序

代码

void CountSort(int* a, int n)
{
	int i = 0;
	int min = a[0];
	int max = a[0];
	for (i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int* count = (int*)calloc(max - min + 1, sizeof(int));
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}
	for (i = 0; i < n; i++)
	{
		int tmp = a[i] - min;
		count[tmp]++;
	}
	int flag = 0;
	for (i = 0; i < max - min + 1; i++)
	{
		if (flag < n)
		{
			while (count[i] > 0)
			{
				a[flag++] = i + min;
				count[i]--;
			}
		}
	}
}

特性总结

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

时间复杂度：O(MAX(N,范围))

空间复杂度：O(范围)

稳定性：稳定

排序性能对比

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

5.选择题练习

5.1 选择题一

1. 快速排序算法是基于（ ）的一个排序算法。
A分治法
B贪心法
C递归法
D动态规划法

答案:A

5.2 选择题二

2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，
当把第8个记录45插入到有序表时，为找到插入位置需比较（ ）次？
（采用从后往前比较）
A 3
B 4
C 5
D 6

答案:C

5.3 选择题三

3.以下排序方式中占用O（n）辅助存储空间的是（ ）
A 简单排序
B 快速排序
C 堆排序
D 归并排序

答案：D

5.4 选择题四

4.下列排序算法中稳定且时间复杂度为O(n^2)的是（ ）
A 快速排序
B 冒泡排序
C 直接选择排序
D 归并排序

答案：B

5.5 选择题五

5.关于排序，下面说法不正确的是（ ）
A 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B 归并排序是一种稳定的排序,堆排序和快排均不稳定
C 序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)

答案：D

5.6 选择题六

6.下列排序法中，最坏情况下时间复杂度最小的是（ ）
A 堆排序
B 快速排序
C 希尔排序
D 冒泡排序

答案:A

5.7 选择题七

7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，
则以第一个关键字65为基准而得到的一趟快速排序结果是（）
A 34，56，25，65，86，99，72，66
B 25，34，56，65，99，86，72，66
C 34，56，25，65，66，99，86，72
D 34，56，25，65，99，86，72，66