1. Toy模板网首页
  2. > Toy博客

【数据结构】排序之归并排序与计数排序

8月前 作者：zxctsclrjjjcph 分类：Toy博客 阅读(32) 违法举报

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

个人主页 ： zxctsclrjjjcph
文章封面来自：艺术家–贤海林
如有转载请先通知

1. 前言

在前面的文章中介绍了 插入排序和交换排序，今天来分享的是归并排序和计数排序。
话不多说，正文开始。

2. 归并排序

归并排序既是内排序也是外排序。

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

【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
归并排序的特性总结：

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

2.1 递归实现

2.1.1 分析

左边和右边都无序，先分割，8个分为4个，4个分为两个，两个分为1个，一个可以认为它有序了。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
一个和一个归为2个有序，2个和2个归为4个有序，4个4个归为有序。这里用的就是后序递归。
用一个临时数组tmp来进行排序后再拷贝回原数组，不可能每次调用数组自己就再开辟一次空间。
在递归的时候必须是一段区间，所以这里重新写一个子函数_MergeSort()来实现递归。
直接分割区间mid = (begin + end) / 2，然后分割左区间再分割右区间，当只有一个值时，已经有序了。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
归并时，将左右区间里面的值进行比较，取小的尾插在tmp临时数组中。一个一个插入，最后肯定还剩下一组，如果剩下第一个区间就直接尾插tmp[i++] = a[begin1++]；同样剩下第二个区间也直接尾插tmp[i++] = a[begin2++]，最后拷贝回原数组memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1))。

2.1.2 代码实现

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

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

	// [begin, mid][mid+1, end]归并
	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);
}

来个例子测试一下。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法

2.2 非递归实现

如果用栈模拟实现，是不合适的，栈适合前序遍历，而归并排序是后序遍历。可以在栈里面对区间进行分割，但是栈空了，已经没有区间了，实现不了归并。

2.2.1 分析

归并分割是为了实现有序，直接到过来，一个和一个归并就实现有序。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
同样要先开一个临时数组tmp，先归第一组区间[begin1, end1][begin2, end2]实现归并，谁小谁尾插，归并逻辑和上面递归是一样的。
gap为每一组数据个数，第一个区间就是int begin1 = i, end1 = i + gap - 1;
第二个区间就是int begin2 = i + gap, end2 = i + 2 * gap - 1。（这里算的是下标，所以end得减1）。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
这里实现完一组gap，要实现下一个gap，用一个for 循环实现for(size_t i = 0; i < n; i += 2 * gap)。那么结束条件就是gap > n。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法

代码写出来就是

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		printf("gap:%2d->", gap);
		for (size_t i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			// [begin1, end1][begin2, end2] 归并
			printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);
			int j = begin1;
			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) * 2 * gap);
		}
		printf("\n");
		gap *= 2;
	}
	free(tmp);
}

举个例子实现代码，发现结果出不来。为什么呢？
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
说明区间越界了，得对区间进行处理。
区间[begin1, end1][begin2, end2]中begin1不存在越界，i是一直小于n。
end1，begin2, end2都会存在越界情况。
对end1如果它大于n，不需要归并了，就直接break；
对begin2如果它大于n，说明第二个区间越界了，也不需要归并，就直接break；
对end2如果它大于n，这里的第二个区间还存在一些值，将区间修改为n-1(end2 = n - 1)。

            if (end1 >= n || begin2 >= n)
			{
				break;
			}

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

【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
这里得注意拷贝，在使用memcpy时，归一组就拷贝一组，如果全部归并之后再拷贝，就会出现随机值。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
放在外面，如果后面区间出现越界，直接break,就没有就行归并，它本身就是有序的，会把之前有序的数据覆盖。

2.2.2 代码实现

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

	int gap = 1;
	while (gap < n)
	{
		printf("gap:%2d->", gap);
		for (size_t i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			// [begin1, end1][begin2, end2] 归并
			// 边界的处理
			if (end1 >= n || begin2 >= n)
			{
				break;
			}

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

			int j = begin1;
			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));
		}

		printf("\n");

		gap *= 2;
	}
	free(tmp);
}

举个例子：
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法

3. 计数排序

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

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

【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
计数排序的特性总结：

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

局限性：

  1. 不适合分散的数据，更适合集中数据；
  2. 不适合浮点数、字符串、结构体数据排序，只适合整数。

3.1 分析

【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法

代码核心就是：
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
a[i]是多少就对多少进行计数，出现几次就加几次。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
1这个位置出现3次就在原数组中写3个1，2的位置出现一次就在原数组中写一个2。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
这里不可能每一次都从0开始进行排序，每一次都是几对于几
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法

如果是这样，那么就浪费了1000个空间。
这里使用相对映射而不是绝对映射。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法
找最小值1000，最大值1999。
然后用calloc开一个计数数组，因为calloc会初始化为0。
这里1000就在0的位置，1999就在999的位置。
统计次数：对相对映射位置进计数。

    for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

这里怎么还原呢？
加回去就行j + min。
后置减减，返回的减减之前的值，往回写。

    for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}

这里负数也能使用计数排序。
【数据结构】排序之归并排序与计数排序,数据结构,数据结构,排序算法,算法

3.2 代码实现

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		printf("calloc fail\n");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

	// 排序
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
}

4. 附代码

4.1 Sort.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

void PrintArray(int* a, int n);

void MergeSort(int* a, int n);
void MergeSortNonR(int* a, int n);
void CountSort(int* a, int n);

4.2 Sort.c

#include"Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

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

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

	// [begin, mid][mid+1, end]归并
	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);
}

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

	int gap = 1;
	while (gap < n)
	{
		/*printf("gap:%2d->", gap);*/
		for (size_t i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			// [begin1, end1][begin2, end2] 归并
			/*printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);*/

			// 边界的处理
			if (end1 >= n || begin2 >= n)
			{
				break;
			}

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

			/*printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);*/

			int j = begin1;
			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));
		}

		/*printf("\n");*/

		gap *= 2;
	}


	free(tmp);
}

// 基数排序/桶排序

// 计数排序
// 时间：O(N+range)
// 空间：O(range)
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		printf("calloc fail\n");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

	// 排序
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
}

4.3 Test.c

#include"Sort.h"

void TestMergeSort()
{
	
	int a[] = {10,8,7,1,3,9,4,2,9,10 };
	PrintArray(a, sizeof(a) / sizeof(int));
	/*MergeSort(a, sizeof(a) / sizeof(int));*/
	MergeSortNonR(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}

void TestCountSort()
{
	int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };
	PrintArray(a, sizeof(a) / sizeof(int));

	CountSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}



int main()
{
	
	/*TestMergeSort();*/
	TestCountSort();

	return 0;
}

有问题请指出，大家一起进步！文章来源地址https://www.toymoban.com/news/detail-798899.html

到了这里，关于【数据结构】排序之归并排序与计数排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】排序之归并排序与计数排序

    【数据结构】排序之归并排序与计数排序

    个人主页 ： zxctsclrjjjcph 文章封面来自：艺术家–贤海林 如有转载请先通知 在前面的文章中介绍了 插入排序和交换排序，今天来分享的是归并排序和计数排序。 话不多说，正文开始。 归并排序既是内排序也是外排序。 基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的

    2024年01月17日
    浏览(32)
  • 数据结构——归并排序和计数排序的介绍

    数据结构——归并排序和计数排序的介绍

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

    2024年02月11日
    浏览(46)
  • 【数据结构初阶】八大排序(三)——归并排序&&计数排序

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

    大家好我是沐曦希💕 往期博客：【数据结构初阶】八大排序(一)——希尔排序堆排序直接插入排序直接选择排序 【数据结构初阶】八大排序(二)——快速排序冒泡排序 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一

    2024年02月03日
    浏览(58)
  • 【C语言】数据结构——排序三（归并与计数排序）

    【C语言】数据结构——排序三（归并与计数排序）

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了排序，包括直接插入排序，希尔排序，选择排序，堆排序，冒泡排序和快排。 今天我们来讲一讲归并排序和计数排序。 关注博主或是订阅专栏，掌握第一消息。 归并排序的

    2024年01月19日
    浏览(29)
  • 【数据结构】归并排序的两种实现方式与计数排序

    【数据结构】归并排序的两种实现方式与计数排序

    前言：在前面我们讲了各种常见的排序，今天我们就来对排序部分收个尾，再来对归并排序通过递归和非递归的方法进行实现，与对计数排序进行简单的学习。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博

    2024年01月18日
    浏览(33)
  • 【数据结构】一文带你全面了解排序（下）——冒泡排序、快速排序、归并排序、计数排序

    【数据结构】一文带你全面了解排序（下）——冒泡排序、快速排序、归并排序、计数排序

      目录 一、常见排序算法的实现   1.1 交换排序 1.1.1 基本思想 1.1.2 冒泡排序  1.1.3 快速排序 1.2 归并排序 1.3 非比较排序 二、排序算法复杂度及稳定性分析  人总得为过去的懒惰而付出点代价！ 1.1.1 基本思想 基本思想：所谓交换，就是根据序列中两个记录键值的比较结

    2024年02月16日
    浏览(35)
  • 数据结构：直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序(C实现)

    数据结构：直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，计数排序(C实现)

    个人主页 ： 个人主页 个人专栏 ： 《数据结构》 《C语言》 排序：使一串数据，按照其中的某个或某些的大小，递增或递减的排列起来的操作。 插入排序的思路：把待排序数组，逐个插入到已经排好序的有序数组中，直到所有待排序数组插入完成，的到一个新的有序

    2024年02月11日
    浏览(32)
  • 【数据结构与算法】归并排序详解：归并排序算法，归并排序非递归实现

    【数据结构与算法】归并排序详解：归并排序算法，归并排序非递归实现

    归并排序是一种经典的排序算法，它使用了分治法的思想。下面是归并排序的算法思想： 递归地将数组划分成较小的子数组，直到每个子数组的长度为1或者0。 将相邻的子数组合并，形成更大的已排序的数组，直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(52)
  • 数据结构——排序算法——归并排序

    数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中，由于第二个列表已经有序，所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中，每次插入时，只需要从上次插入的位置开始，继续向后寻找插入位置即可。这样一来，我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(27)
  • 数据结构和算法笔记4：排序算法-归并排序

    数据结构和算法笔记4：排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下： 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决：使用归并排序递归地排序两个子序列。 合并：合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程，下面是要排序

    2024年01月21日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包