数据结构-C语言-排序(4)

代码位置:   

         test-c-2024: 对C语言习题代码的练习 (gitee.com)

一、前言:

1.1-排序定义:

        排序就是将一组杂乱无章的数据按照一定的规律(升序或降序)组织起来。(注:我们这里的排序采用的都为升序)

1.2-排序分类:

常见的排序算法:

  • 插入排序
    a. 直接插入排序
    b. 希尔排序

  • 选择排序
    a. 选择排序
    b. 堆排序
  • 交换排序
    a. 冒泡排序
    b. 快速排序
  • 归并排序
    a. 归并排序
  • 非比较排序
    a.计数排序
    b.基数排序

1.3-算法比较:

1.4-目的:

        今天,我们这里要实现的是归并排序、计数排序

二、归并排序-递归:

2.1-定义:

        归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

2.2-思路:

归并排序两个基本过程:

        1、分:将原数组分割成两个平分子数组的过程。

        2、治:将分割后的数组两两结合成一个有序的数组的过程。

归并排序两个基本操作:

  1. 将待排序的线性表不断地切分成若干个子表,直到每个子表只包含一个元素,这时,可以认为只包含一个元素的子表是有序表。
  2. 将子表两两合并,每合并一次,就会产生一个新的且更长的有序表,重复这一步骤,直到最后只剩下一个子表,这个子表就是排好序的线性表。

2.3-过程图:

2.4-代码实现:

void _MagerSort(int* a, int begin,int end,int*tem)
{if (begin >= end)return;int mid = (begin + end) / 2;//子区间递归_MagerSort(a, begin, mid, tem);_MagerSort(a, mid+1, end, tem);//归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while(begin1<=end1&&begin2<=end2){if (a[begin1] >= a[begin2]){tem[i++] = a[begin2++];}else{tem[i++] = a[begin1++];}}while (begin1 <= end1){tem[i++] = a[begin1++];}while (begin2 <= end2){tem[i++] = a[begin2++];}memcpy(a + begin, tem + begin, sizeof(int) * (end - begin + 1));
}//递归实现
void MagerSort(int* a, int n)				//归并排序---时间复杂度(O(N*logN))
{int* tem = (int*)malloc(sizeof(int) * n);if (tem == NULL){perror("malloc MagerSort");return;}_MagerSort(a, 0, n - 1, tem);free(tem);
}

2.5-效果图:

三、归并排序-非递归:

3.1-定义:

        归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

3.2-思路:

        我们知道,递归实现的缺点就是会一直调用栈,而栈内存往往是很小的,如果调用次数过多就会出现栈溢出的现象。所以,我们尝试着用循环的办法去实现归并排序。

        我们可以通过间距值gap=1来实现将数组分割若干个只含一个数的子数组的操作,然后通过改变gap的值来实现两两合并的操作。

        注意:在循环过程中我们需要考虑是否有越界的问题,如果有的话我们可以通过改变begin和end的值的方式来调整范围,修正路线。

        拷贝时我们有两种拷贝方式:一种是全部拷贝(梭哈),另一种是部分拷贝。

3.3-过程图:

3.4-代码实现:


//非递归实现
//全部拷贝(梭哈)
void MergeSortNonR1(int* a, int n)		//归并排序---时间复杂度(O(N*logN))
{int* tem = (int*)malloc(sizeof(int) * n);if (tem == NULL){perror("malloc fail\n");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;//修正路线if (end1 >= n){end1 = n-1;begin2 = n;end2 = n-1;}else if (begin2 >= n){begin2 = n;end2 = n-1;}else if (end2 >= n){end2 = n-1;}//归并int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] >= a[begin2]){tem[j++] = a[begin2++];}else{tem[j++] = a[begin1++];}}while (begin1 <= end1){tem[j++] = a[begin1++];}while (begin2 <= end2){tem[j++] = a[begin2++];}	}memcpy(a, tem, sizeof(int) * n);gap *= 2;}free(tem);
}//部份拷贝
void MergeSortNonR2(int* a, int n)		//归并排序---时间复杂度(O(N*logN))
{int* tem = (int*)malloc(sizeof(int) * n);if (tem == NULL){perror("malloc fail\n");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;//修正路线if (end1 >= n){break;}else if (begin2 >= n){break;}else if (end2 >= n){end2 = n - 1;}//归并int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] >= a[begin2]){tem[j++] = a[begin2++];}else{tem[j++] = a[begin1++];}}while (begin1 <= end1){tem[j++] = a[begin1++];}while (begin2 <= end2){tem[j++] = a[begin2++];}memcpy(a+i, tem+i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tem);
}

3.5-效果图:

四、计数排序:

4.1-定义:

        计数排序是一种非比较排序算法。 它通过计算每个唯一元素的出现次数对数组进行排序。 它对唯一元素的计数进行部分哈希处理,然后执行计算以找到最终排序数组中每个元素的索引。 它是一个相当快的算法,但不适合大型数据集。 它作为基数排序中的一个子程序使用。

4.2-思路:

        1.开辟计数数组:如果数据为:(100,102,106,110,107)的话这里从0开始开辟的话就会开辟一个长度111个的数组其中有100个是浪费的,这样的话如果数据过大的话这个排序的效率就会非常的低。所以,这里我们数组长度的开辟采用最大值-最小值的方式,这样就避免了上述情况。

        2.出计数数组:出数组时我们是从计数数组的第一个下标中统计的个数依次往后出,出数组时我们需要下标加上最小值min,这样就实现排序啦!

4.3-过程图:

4.4-代码实现:


// 时间复杂度:O(N+range)
// 空间复杂度:O(range)
void CountSort(int* a, int n)					// 计数排序
{int max = a[0];int min = a[0];for (int i = 1; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min+1;int* tem = (int*)malloc(sizeof(int) * range);if (tem == NULL){perror("malloc");return;}//开辟的数组初始化为0for (int i = 0; i < range; i++){tem[i] = 0;}for (int i = 0; i < n; i++){int j = a[i] - min;tem[j]++;}int m = 0;for (int i = 0; i < range; i++){while(tem[i]>0){if (tem[i] != 0){a[m++] = i + min;tem[i]--;}}}
}

4.5-效果图:

五、结语:

        上述内容,即是我个人对数据结构排序中归并排序、计数排序的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位uu们的点赞,关注,收藏,我会更加努力的学习编程语言,还望各位多多关照,让我们一起进步吧!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1486896.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

如何借助生成式人工智能引领未来的科技狂潮

如何借助生成式人工智能引领未来的科技狂潮 1. 生成式AI的现状1.1 技术基础1.1.1 深度学习1.1.2 生成对抗网络&#xff08;GANs&#xff09;1.1.3 变分自编码器&#xff08;VAEs&#xff09; 1.2 主要应用1.2.1 语言模型1.2.2 图像生成1.2.3 音频与视频生成 2. 未来的发展趋势2…

Windows下帆软BI(finebi)单机部署移植(Tomcat)攻略

一、基础环境 操作系统&#xff1a;Windows 10 64bit 帆软BI 版本&#xff1a;V9.0/V10.0 HTTP工具&#xff1a;Tomcat 外置数据库&#xff1a;Oracle 11g 实验内容&#xff1a;将已经部署好的帆软BI从一台电脑移植到另一台电脑 二、前期准备 1、做好外置数据库移植&…

<数据集>苹果腐烂识别数据集<目标检测>

数据集格式&#xff1a;VOCYOLO格式 图片数量&#xff1a;978张 标注数量(xml文件个数)&#xff1a;978 标注数量(txt文件个数)&#xff1a;978 标注类别数&#xff1a;2 标注类别名称&#xff1a;[fresh_apple, rotten_apple] 序号类别名称图片数框数1fresh_apple520922…

2022 年中高职组“网络安全”赛项-海南省省竞赛任务书-1-B模块-B-4Web渗透测试

前言 本章节我将尝试操作B-4模块的渗透测试&#xff0c;搭建环境很难&#xff0c;还望大家点点赞多多支持&#xff01; 任务概览 最后4、5、6有一定的难度。 环境要求 kali Linux192.168.41.2Web服务器&#xff08;假设为PYsystem 2020 模拟平台&#xff09;192.168.41.7交换…

日常开发记录分享——C#控件ToolTip实现分栏显示内容

文章目录 需求来源实现思路实施请看VCR等等别走&#xff0c;有优化 需求来源 需要在鼠标浮动到指定位置后提示出详细的信息&#xff0c;一开始使用的tooltip实现&#xff0c;但是里面的内容效果并不理想&#xff0c;需要有条理性&#xff0c;于是就想到能不能将展示的东西分列…

代理协议解析:如何根据需求选择HTTP、HTTPS或SOCKS5?

代理IP协议是一种网络代理技术&#xff0c;可以实现隐藏客户端IP地址、加速网站访问、过滤网络内容、访问内网资源等功能。常用的IP代理协议主要有Socks5代理、HTTP代理、HTTPS代理这三种。代理IP协议主要用于分组交换计算机通信网络的互联系统中使用&#xff0c;只负责数据的路…

Linux(CentOS)的“应用商城” —— yum

Linux&#xff08;CentOS&#xff09;的“应用商城” —— yum 关于 yum 和软件包Linux 系统&#xff08;CentOS&#xff09;的生态yum 相关操作yum 本地配置yum 安装 lrzsz.x86_64 关于 yum 和软件包 首先 yum 是软件下载安装管理的客户端&#xff0c;类似各种手机里的“应用…

面试场景题系列--(1)如果系统的 QPS 突然提升 10 倍该怎么设计?--xunznux

1. 如果系统的 QPS 突然提升 10 倍该怎么设计&#xff1f; 1.1 硬件的扩展微服务的拆分 如果所有的业务包括交易系统、会员信息、库存、商品等等都夹杂在一起&#xff0c;当流量一旦起来之后&#xff0c;单体架构的问题就暴露出来了&#xff0c;机器挂了所有的业务就全部无法…

【机器学习】Jupyter Notebook如何使用之基本步骤和进阶操作

引言 Jupyter Notebook 是一个交互式计算环境&#xff0c;它允许创建包含代码、文本和可视化内容的文档 文章目录 引言一、基本步骤1.1 启动 Jupyter Notebook1.2 使用 Jupyter Notebook 仪表板1.3 在笔记本中工作1.4 常用快捷键1.5 导出和分享笔记本 二、进阶用法2.1 组织笔…

“微软蓝屏”事件,给IT行业带来的宝贵经验和教训

“微软蓝屏”事件是指2024年7月19日发生的一次全球性技术故障&#xff0c;主要涉及微软视窗&#xff08;Windows&#xff09;操作系统及其相关应用和服务。 以下是对该事件的详细解析&#xff1a; 一、事件概述 发生时间&#xff1a;2024年7月19日事件影响&#xff1a;全球多个…

暑期c++ 命名空间

今天是暑期第一天开始写c笔记&#xff0c;新起点&#xff0c;新开始加油 我们先来看两串代码 这串代码编译没有问题 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int rand 14; int main(void) {int rand 14;printf("%d\n", rand);return 0; }但是…

鸽哒IM即时通讯安卓+苹果双系统源码20240723(反编译+二次开发版)

功能特点&#xff1a; 1、该软件支持加好友、消息私聊、消息群聊、朋友圈、红包、语音、视频、表情包&#xff0c;定位等。 2、此外&#xff0c;该软件还支持阅后即焚、消息过期自动销毁、支持3DES加密传输、支持端到端传输&#xff0c;保护消息隐私。 3、后台使用的是酷信的…

Java面试八股之详细阐述Spring的DI和IOC

详细阐述Spring的DI和IOC Spring框架的两大核心特性之一就是控制反转&#xff08;Inversion of Control, IoC&#xff09;&#xff0c;另一个密切相关的是依赖注入&#xff08;Dependency Injection, DI&#xff09;。这两个概念是Spring实现松耦合、可测试和可管理软件组件的…

JMeter:BeanShell到JSR223迁移中的注意事项

前言 在之前的文章JMeter&#xff1a;BeanShell向JSR223迁移过程遭遇的java标准库不可用问题-如何切换JDK版本中引用了一段使用BeanShell对入参进行加密的脚本&#xff0c;迁移到JSR223&#xff0c;虽然更换JDK后编译通过&#xff0c;看似也可以执行了&#xff0c;但是其实那段…

强化数字科技基石:深化基础理论研究

加强数字科技基础理论研究并增加对其的资金投入&#xff0c;对于推动科技进步、培养创新人才以及构建具有国际竞争力的科技创新体系都具有深远意义。同时为了加强数字科技基础理论研究并推动产业园的发展&#xff0c;我们可以从以下几个方面进行&#xff1a; 一、加强数字科技…

【vue前端项目实战案例】Vue3仿今日头条App

本文将开发一款仿“今日头条”的新闻App。该案例是基于 Vue3.0 Vue Router webpack TypeScript 等技术栈实现的一款新闻资讯类App&#xff0c;适合有一定Vue框架使用经验的开发者进行学习。 项目源码在文章末尾 1 项目概述 该项目是一款“今日头条”的新闻资讯App&#xf…

P6 优化篇 - 数据折线图可视化步骤

增加新页面, 则需要在 page.json里面增加页面信息 2.添加目录, 和路径 同时也要添加目录了 , 新建目录LineChart , 添加文件LineChart.vue 4.LineChart.vue 直接复制黏贴 <template><view class"container"><!-- 图表显示区域 --><view cla…

如何做校园圈子小程序,需要哪些功能?可打包APP小程序H5,源码交付,支持二开!

独立学校首页 支持每个学校独立首页!每个学校都可以拥有专属首页&#xff0c;打造不同风格的学校首页展示效果 多业务覆盖 可实现校园内外卖、跑腿、超市、药店水果、快餐店等业务全覆盖!所有配送业务平台都可开展 多站点运营 支持多学校多站点运营&#xff0c;各分站管理员可独…

Java面试八股之简述spring boot的目录结构

简述spring boot的目录结构 Spring Boot 项目遵循标准的 Maven 或 Gradle 项目布局&#xff0c;并且有一些约定的目录用于组织不同的项目组件。下面是一个典型的 Spring Boot 项目目录结构&#xff1a; src/main/java&#xff1a;包含所有的 Java 源代码&#xff0c;通常按包组…

【计算机毕业设计】基于微信小程序的传染病防控宣传系统【源码+lw+部署文档】

包含论文源码的压缩包较大&#xff0c;请私信或者加我的绿色小软件获取 免责声明&#xff1a;资料部分来源于合法的互联网渠道收集和整理&#xff0c;部分自己学习积累成果&#xff0c;供大家学习参考与交流。收取的费用仅用于收集和整理资料耗费时间的酬劳。 本人尊重原创作者…