数据结构——计数与归并非递归

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

数据结构——计数与归并非递归,数据结构,数据结构


前言

重要的事说三遍!
学习!学习!学习!
努力!努力!努力!


一、归并的非递归实现

数据结构——计数与归并非递归,数据结构,数据结构
数据结构——计数与归并非递归,数据结构,数据结构

代码实现:

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)
	{
		for (int 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] 归并
			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}

			// 拷贝回原数组
			memcpy(a + i, tmp + i, (2 * gap) * sizeof(int));
		}
		gap *= 2;
	}

	free(tmp);
}

二、计数排序

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

数据结构——计数与归并非递归,数据结构,数据结构

代码实现:

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (size_t i = 0; 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*)malloc(sizeof(int) * range);
	
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}
	memset(count, 0, sizeof(int) * range);

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

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

计数排序的特性总结:

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

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

数据结构——计数与归并非递归,数据结构,数据结构
数据结构——计数与归并非递归,数据结构,数据结构


总结

重要的事说三遍!
成功!成功!成功!
加油吧!从现在开始~文章来源地址https://www.toymoban.com/news/detail-716244.html

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

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

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

相关文章

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

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

    2024年01月17日
    浏览(48)
  • 数据结构——lesson13排序之计数排序

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、排序算法合集 💥对于数据结构顺序表、链表、堆以及排序有疑问的都可以在上面数据结构专栏和排序合集专栏进行

    2024年04月10日
    浏览(42)
  • 数据结构——归并排序和计数排序的介绍

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

    2024年02月11日
    浏览(55)
  • 数据结构--递归与分治

    汉诺塔分析: 以三层进行分析,大于三层分析情况是一样的。    八皇后问题:

    2024年02月11日
    浏览(31)
  • <数据结构>NO11.归并排序|递归|非递归|优化

    思路: 如果给出两个有序数组,我们很容易可以将它们合并为一个有序数组。 因此当给出一个无序数组时,我们先将它们均分为两组有序数组,在将这两组有序数组合并为一个有序数组;而将原数组分成2组 有序数组的思路又是归并排序 。 递归的结束条件是什么? 当递归区间

    2024年02月16日
    浏览(42)
  • 算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

    1. 插入排序(insertion-sort):                                           是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入     算法稳定性:                  

    2024年02月09日
    浏览(53)
  • 数据结构与算法(小议递归)

    递归是一种常用的算法设计,递归就是一种循环推理。简单来说就是调用原算法本身的算法。 这里主要探讨递归的使用, 用一个简单的例子来看: 这是一个很流行的裴波那契数列计算函数,很多编程书籍喜欢拿这个数列做例子。当然一般不会这么写~ 这函数看上去很优雅,

    2024年02月01日
    浏览(51)
  • 【数据结构】二叉树(遍历,递归)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​​ 目录 二叉树遍历规则 前序遍历 ​ 中序遍历  后序遍历 递归结构遍历 前序 中序  求节点个数 求叶子节点个数  求树

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

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

    2024年02月03日
    浏览(128)
  • 数据结构与算法之排序: 计数排序 (Javascript版)

    排序 排序:把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例) 计数排序 核心思想 :通过计数而非比较来进行排序,借助数组下标本身就是有序的原理实现 适用范围:较小的非负整数序列和最小值和最大值之间的数字范围比较合适 基数排序需要新增一个计数数

    2024年02月06日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包