决战排序之巅(二)

这篇具有很好参考价值的文章主要介绍了决战排序之巅(二)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

欢迎来到决战排序之巅栏目,
本期给大家带来的是归并排序与计数排序的实现与比较。
在上期决战排序之巅(一)中,给大家带来了插入排序(希尔) 与 选择排序(堆排) 的实现与比较,感兴趣的可以看看。

决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治

排序测试函数 void verify(int* arr, int n)

主要功能:测试arr数组中的顺序是否全为非升序的顺序。
代码如下:

void verify(int* arr, int n)
{
	for (int i = 1; i < n; i++)
	{
		assert(arr[i] >= arr[i - 1]);
	}
}

如果arr数组中顺序不全为非升序,则assert()直接终止程序;
若全为非升序,则程序可通过该函数。

归并排序

基本思想:采用分治算法,将已有的有序子序列进行合并,得到完全有序的序列;即先使每个子序列有序,再使子序列所合并的序列有序。
归并排序的核心步骤就是:分解与合并。

递归方案

如下图所示:我们可以先将一组数据由大到小逐个分开,再依次合并。
下图绿线为分解,蓝线为合并。我们可以看到,排序数据分解时,当子序列内个数为1 时,不再分解;随后进行依次的合并,"1" "9" 合并为"1 9"的子序列,"5" "6"合并成"5 6"的体序列,同理可得"3 8" "2 7",再让子序列合并,"1 9 6 5"合并成"1 5 6 9""3 8""2 7"合并成"2 3 7 8"。最后两个字序列合并成"1 2 3 5 6 7 8 9"
至此,归并排序完毕。
决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治
具体代码,如下:

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);

	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

void MergeSort(int* a, int n)是我们排序的调用函数,因为他的参数形式不宜用递归实现,所以我们可以写一个子函数void _MergeSort(int* a,int begin,int end ,int* tmp)来实现主要程序的编写,如下:

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 left1 = begin, right1 = mid;
	int left2 = mid + 1, right2 = end;
	int i = 0;
	while (left1 <= right1 && left2 <= right2)
	{
		if (a[left1] > a[left2])
			tmp[i++] = a[left2++];
		else
			tmp[i++] = a[left1++];
	}

	while (left1 <= right1)
	{
		tmp[i++] = a[left1++];
	}

	while (left2 <= right2)
	{
		tmp[i++] = a[left2++];
	}

	memcpy(a + begin, tmp, i * sizeof(int));
}

我们先通过以下代码进行归并排序“分解”的实现

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

当子序列内个数为1 时,return 返回;当子序列内个数大于1 时,进行以下编写:
有递归可知,此时的小标区间为[begin , mid] 与 [mid + 1 , end]是排好序的子区间,所有此时我们只要将其合并好就可以了。

	int left1 = begin, right1 = mid;
	int left2 = mid + 1, right2 = end;
	int i = 0;
	while (left1 <= right1 && left2 <= right2)
	{
		if (a[left1] > a[left2])
			tmp[i++] = a[left2++];
		else
			tmp[i++] = a[left1++];
	}

	while (left1 <= right1)
	{
		tmp[i++] = a[left1++];
	}

	while (left2 <= right2)
	{
		tmp[i++] = a[left2++];
	}

	memcpy(a + begin, tmp, i * sizeof(int));

最后将tmp上的数据拷贝到a的[begin , end]区间即可。

代码可行性测试
void _test()
{
	int n = 100000000;
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		arr[i] = rand();
	}
	MergeSort(arr, n);
	verify(arr, n);
	free(arr);
}

运行结果如下 :
决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治
程序通过verify(int* arr int n)函数,且成功运行,代码无误。

非递归方案

在非递归方案中我们可以利用循环来实现,主要实现过程如下视频所示:

归并排序思想

我们可以定义一个gap并且gap的初始置为1,用来表示子序列的最小个数为1,随后在整体排完相邻两个子序列后,gap乘以2,此时数组内小标区间为 [ n ∗ g a p , n ∗ ( g a p ∗ 2 − 1 ) ] ∪ [ 0 , g a p − 1 ] , n ∈ N + [n * gap , n * (gap * 2-1)]\cup[0 , gap-1] ,n\in N^+ [ngap,n(gap21)][0,gap1],nN+是有序的,如此循环直到, n ≤ g a p n\leq gap ngap时跳出循环,代码如下:

void MergeSortNonR(int* a,int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);

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

			int j = begin1;

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

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

我们先看如何分解,利用gap来确定子序列的元数个数,再利用for循环来实现两个相邻子序列的排序(即下标区间[begin1,end1] , [begin2,end2]的排序)
注意:在分配完区间[begin1,end1] ,和[begin2,end2]后,我们要对区间范围的有效性进行检查,因为非递归的方案通过比较相邻的子序列,gap2的幂次方所增长,适用的数组长度也为2的幂次方,所以我们要对end1 , begin2 , end2进行检查,如果end1 , begin2 大于数组总个数n时,直接break即可,因为此时的[begin1,n-1]已经是有序的了;如果end2大于n则,令end2=n-1,此时我们只要排好[begin1,end2] , [begin2,n-1]即可,具体过程如下:

		for (int i = 0; i < n; i += gap * 2)
		{
				int begin1 = i, end1 = i + gap - 1;
				int begin2 = i + gap, end2 = i + gap * 2 - 1;
	
				int j = begin1;
	
				if (end1 >= n && begin2 >= n)
				{
					break;
				}
				if (end2 >= n)
				{
					end2 = n - 1;
				}

				//合并过程
		}

合并过程与递归方案相同,但需要注意的是数组拷贝的时候,for循环依次拷贝一次。

代码可行性测试

决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治

程序通过verify(int* arr int n)函数,且成功运行,代码无误。

特点分析

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

计数排序

基本思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。

代码实现

实现步骤:

  1. 选出要排序数组a中的最值,再相减求出数组的相对范围 n = m a x − m i n + 1 n = max - min + 1 n=maxmin+1
  2. 用calloc开辟n个空间为tmp
  3. 利用i遍历a,让数组tmp[ a [ i ] − m i n a[i] - min a[i]min]++
  4. 最后,再遍历tmp , 此时tmp数组下标 + min就表示数据的大小,tmp[数组下标]表示该数据的个数,所以在此时为a直接赋值即可。
    具体代码如下:
void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	int i = 0;
	for (i = 0; i < n; i++)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}
	int* tmp = (int*)calloc((max - min + 1), sizeof(int));
	assert(tmp);

	for (i = 0; i < n; i++)
	{
		tmp[a[i] - min]++;
	}
	int j = 0;
	for (i = 0; i < max - min + 1; i++)
	{
		int count = tmp[i];
		while (count--)
		{
			a[j++] = i + min;
		}
	}
	free(tmp);
}
代码可行性测试

决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治
程序通过verify(int* arr int n)函数,且成功运行,代码无误。

特点分析

特点分析:计数排序在数据范围集中时,效率很高,但是适用范围及场景有限(例如:小数,结构体,字符串无法比较)
时间复杂度:O(MAX(N,范围))
空间复杂度:O(范围)

归并排序 VS 计数排序(Release版本)

说明

以下会分别对1w,10w,100w,1000w的数据进行100次的排序比较,并计算出排一趟的平均值。

下面是用来生成随机数的代码,可以确保正数与负数的随机分布。

	for (i = 0; i < n; i++)
	{
		if (rand() % 2)
		{
			arr3[i] = arr2[i] = arr1[i] = -rand() + i;
		}
		else
		{
			arr3[i] = arr2[i] = arr1[i] = rand() - i;
		}
	}

介绍就到这里了,让我们来看看这100次排序中,谁才是你心目中的排序呢?
PS:100次只是一个小小的测试数据,有兴趣的朋友可以在自己电脑上测试更多的来比较哦。

1w rand( ) 数据测试

决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治

10w rand( ) 数据测试

决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治

100w rand( ) 数据测试

决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治

1000w rand( ) 数据测试

决战排序之巅(二),数据结构,排序算法,算法,数据结构,c语言,哈希算法,分治

测试代码

void Test_MergeSort_CountSort()
{
	int n = 10000000;
	int count = 100;
	int* arr1 = numcreate(n);
	int* arr2 = numcreate(n);
	int* arr3 = numcreate(n);
	int time1 = 0, time2 = 0, time3 = 0;
	int tmp = count;
	while (tmp--)
	{

		int i = 0;
		for (i = 0; i < n; i++)
		{
			if (rand() % 2)
			{
				arr3[i] = arr2[i] = arr1[i] = -rand() + i;
			}
			else
			{
				arr3[i] = arr2[i] = arr1[i] = rand() - i;
			}
		}

		int begin1 = clock();
		MergeSort(arr1, n);
		int end1 = clock();

		int begin2 = clock();
		MergeSortNonR(arr2, n);
		int end2 = clock();

		int begin3 = clock();
		CountSort(arr3, n);
		int end3 = clock();

		time1 += end1 - begin1;
		time2 += end2 - begin2;
		time3 += end3 - begin3;

	}
	printf("MergeSort: %.2f\n", (float)time1/count);
	printf("MergeSortNonR: %.2f\n", (float)time2 / count);
	printf("CountSort: %.2f\n", (float)time3 / count);
	free(arr1);
	free(arr2);
	free(arr3);
}

从结果来看,计数排序快于归并排序,但它的局限性无法比较小数,结构体与字符串;
再看归并排序,非递归类的要略胜一筹哦。

结语

看完之后,谁才是你心目中的排序呢?
欢迎留言,让我们一起来期待在下一期 《决战排序之巅(三)》。

以上就是本期的全部内容喜欢请多多关注吧!!!文章来源地址https://www.toymoban.com/news/detail-797817.html

到了这里,关于决战排序之巅(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 第11章:C语言数据结构与算法初阶之排序

    排序是一种非常重要的算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,

    2024年02月12日
    浏览(44)
  • 数据结构(C语言实现)——常见排序算法的基本思想及实现(快速排序的三种方法和优化及非递归实现快速排序)

    生活中几乎处处都会用到排序,比如:网购时的店铺顺序,学生成绩的排名等,今天我们就来学习数据结构中常见的几种排序算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列

    2023年04月24日
    浏览(60)
  • 数据结构——排序算法——归并排序

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

    2024年02月09日
    浏览(42)
  • 【排序算法】数据结构排序详解

    前言: 今天我们将讲解我们数据结构初阶的最后一部分知识的学习,也是最为“炸裂”的知识---------排序算法的讲解!!!! 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,

    2023年04月08日
    浏览(49)
  • 数据结构和算法笔记4:排序算法-归并排序

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

    2024年01月21日
    浏览(62)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(75)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(69)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(62)
  • 数据结构——排序算法之快速排序

        个人主页: 日刷百题 系列专栏 : 〖C/C++小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想: 任取待排序元素序列中 的某元素作为基准值,按照

    2024年01月21日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包