归并排序算法

1、基本思想

        归并排序是建立在归并操作上的一种有效的排序算法,它采用分治法的策略。其基本思想是将一个待排序的数组分成两个或多个子数组,先对每个子数组进行排序,然后再将已排序的子数组合并成一个最终的排序数组。

        对于两个有序的数组,很容易做到合并之后仍然有序。归并排序就是利用这一点,将待排序数组分成两个有序数组(如何保证分成的两个数组都有序:不停拆分,直到每个数组中只剩一个数,那么一定有序。)。待得到有序数组后,往回进行不停的合并操作。

2、算法步骤

2.1、算法步骤描述:

        1、分解:将待排序的数组不断地拆分成左右两个子数组,直到每个子数组只包含一个元素为止。这一步是通过不断地计算数组的中间位置来实现的,例如对于数组 arr,中间位置 mid = (left + right) / 2(这里假设 left 是数组起始索引,right 是数组结束索引),从而将数组 arr 拆分成 arr[left...mid] 和 arr[mid + 1...right] 两个子数组。

        2、排序与合并:对拆分后的子数组递归地调用归并排序算法,使其各自有序。然后将两个已经有序的子数组合并成一个更大的有序数组。合并操作是通过比较两个子数组的首元素,将较小的元素依次放入一个临时数组中,直到其中一个子数组的元素全部放入临时数组,再将另一个子数组剩余的元素全部放入临时数组,最后将临时数组中的元素复制回原数组对应的位置。

2.2、归并排序算法过程演示图:

2.3、归并排序算法动态演示图:

动态演示图来源网站URL:​​​​​​https://visualgo.net

3、代码实现

c语言代码实现如下:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define N 10
void add(int arr[], int *left, int leftlen, int *right, int rightlen)
{int i = 0, j = 0, k = 0;//分别代表左数组下标,右数组下标,合并后数组下标while(i < leftlen && j < rightlen)//两个子数组都没合并完{if(left[i] <= right[j])//每次将两子数组中最小值填入arr[k++] = left[i++];elsearr[k++] = right[j++];}//两个子数组可能不会同时完成填入//当左子数组没有完成while(i < leftlen){arr[k++] = left[i++];}//当右子数组没有完成while(j < rightlen){arr[k++] = right[j++];}
}
void sort(int arr[], int len)
{//设定递归终止条件,拆分到数组长度为一时,一定有序if(1 == len)return;int i;int mid = len/2;//确定中间位置int *left = (int *)malloc(mid * sizeof(int));//分配左数组空间int *right = (int *)malloc((len-mid) * sizeof(int));//分配右数组空间for(i = 0; i < mid ; i++)//存值到左数组中{left[i] = arr[i];}for(i = 0; i < len - mid; i++)//存值到右数组中{right[i] = arr[mid + i];}sort(left,mid);//对左右数组再进行拆分sort(right,len - mid);add(arr,left,mid,right,len - mid);//合并有序数组free(left);//回收空间free(right);
}
int main(int argc, char *argv[])
{srand(time(NULL));int a[N];int i;puts("排序前数组为:");for(i = 0; i < N; i++){a[i] = rand()%100;//为数组随机赋值printf("%d ",a[i]);//输出排序之前数组值}puts("");sort(a,N);//排序puts("排序后的数组为:");for(i = 0; i < N; i++){printf("%d ",a[i]);//输出排序之后的数组值}puts("");return 0;
}

4、时间复杂度和空间复杂度

平均时间复杂度:O(nlogn)

空间复杂度:O(n)

稳定性:稳定

5、适用情况

        1、处理大规模数据排序:其时间复杂度为O(nlogn),处理大规模数据时,能够在相对较短的时间内完成排序任务。

        2、有稳定排序的需求时:归并排序是一个稳定的排序算法,当有相等元素进行排序时,相等元素的相对顺序不会改变。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Mysql、Dm8达梦数据库通过脚本导出指定库所有表的结构详情信息到

目录 前言二、Mysql三、达梦8 前言 在当今复杂多变的数据环境中&#xff0c;数据库作为信息存储与管理的核心&#xff0c;其重要性不言而喻。随着业务的不断拓展和深化&#xff0c;对于数据库表结构的理解与管理成为了确保数据一致性和准确性的关键。特别是在跨数据库系统的场…

Android OpenGL ES详解——纹理过滤GL_NEAREST和GL_LINEAR的区别

目录 一、概念 1、纹理过滤 2、邻近过滤 3、线性过滤 二、邻近过滤和线性过滤的区别 三、源码下载 一、概念 1、纹理过滤 纹理坐标不依赖于分辨率(Resolution)&#xff0c;它可以是任意浮点值&#xff0c;所以OpenGL需要知道怎样将纹理像素(Texture Pixel&#xff0c;也…

在vscode中开发运行uni-app项目

确保电脑已经安装配置好了node、vue等相关环境依赖 进行项目的创建 vue create -p dcloudio/uni-preset-vue 项目名 vue create -p dcloudio/uni-preset-vue uni-app 选择模版 这里选择【默认模版】 项目创建成功后在vscode中打开 第一次打开项目 pages.json 文件会报错&a…

算法详解——链表的归并排序非递归解法

算法详解——链表的归并排序非递归解法 本文使用倍增法加上归并排序操作实现了对链表的快速排序&#xff0c;比起一般的递归式归并排序要节省空间并且实现要简单的多&#xff0c;比起一般的迭代式归并排序实现也要简单。 1. 题目假设 给定链表的头结点 head &#xff0c;请将其…

基于 SSM(Spring + Spring MVC + MyBatis)框架构建电器网上订购系统

基于 SSM&#xff08;Spring Spring MVC MyBatis&#xff09;框架构建电器网上订购系统可以为用户提供一个方便快捷的购物平台。以下将详细介绍该系统的开发流程&#xff0c;包括需求分析、技术选型、数据库设计、项目结构搭建、主要功能实现以及前端页面设计。 需求分析 …

Vue Element-UI 选择隐藏表格中的局部字段信息

一、功能需求分析 为什么需要这个功能&#xff1f; &#xff08;1&#xff09;简化信息&#xff0c;减少混乱&#xff1a; 就像整理抽屉&#xff0c;只留下常用的东西&#xff0c;这样找起来更快&#xff0c;看起来也更整洁。在表格中&#xff0c;只展示需要的字段&#xff…

【CANOE】【学习】【诊断功能】正响应抑制

文章目录 一、正响应抑制是什么&#xff1f;二.什么背景下产生三.作用四.如何实现五.capl代码如何实现总结diagGetSuppressRes 相关函数**Function Description****Syntax****Method (Dynamic)****Functionality****Parameters****Return Values****Availability****Example***…

纯血鸿蒙系统 HarmonyOS NEXT自动化测试实践

1、测试框架选择 hdc&#xff1a;类似 android 系统的 adb 命令&#xff0c;提供设备信息查询&#xff0c;包管理&#xff0c;调试相关的命令ohos.UiTest&#xff1a;鸿蒙 sdk 的一部分&#xff0c;类似 android sdk 里的uiautomator&#xff0c;基于 Accessibility 服务&…

基于vue3实现的聊天机器人前端(附代码)

<template><div class"container"><!-- 页面头部 --><header><h1>跟它说说话吧&#xff01;</h1><p>一个活泼的伙伴&#xff0c;为你提供情感支持&#xff01;</p></header><!-- 聊天容器 --><div c…

【赵渝强老师】Redis的RDB数据持久化

Redis 是内存数据库&#xff0c;如果不将内存中的数据库状态保存到磁盘&#xff0c;那么一旦服务器进程退出会造成服务器中的数据库状态也会消失。所以 Redis 提供了数据持久化功能。Redis支持两种方式的持久化&#xff0c;一种是RDB方式&#xff1b;另一种是AOF&#xff08;ap…

qt QFileSystemModel详解

1、概述 QFileSystemModel是Qt框架中的一个关键类&#xff0c;它继承自QAbstractItemModel&#xff0c;专门用于在Qt应用程序中展示文件系统的数据。这个模型提供了一个方便的接口&#xff0c;使得开发者可以轻松地在应用程序中集成文件和目录的树形结构&#xff0c;并通过视图…

ThingsBoard规则链节点:Push to Edge节点详解

引言 1. Push to Edge 节点简介 2. 节点配置 2.1 基本配置示例 3. 使用场景 3.1 边缘计算 3.2 本地数据处理 3.3 实时响应 4. 实际项目中的应用 4.1 项目背景 4.2 项目需求 4.3 实现步骤 5. 总结 引言 ThingsBoard 是一个开源的物联网平台&#xff0c;提供了设备管…

JavaScript 实现文本转语音功能

全篇大概2000 字&#xff08;含代码&#xff09;&#xff0c;建议阅读时间10分钟。 引言 我将向大家展示如何使用 JavaScript 和 Web Speech API 快速实现一个“文本转语音”的 Web 应用。通过这个教程&#xff0c;你将了解如何让浏览器将输入的文本朗读出来。 预览效果 一、…

动态规划理论基础和习题【力扣】【算法学习day.25】

前言 ###我做这类文档一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非常非常高滴&am…

Linux的基本指令(一)

1.ls指令 功能&#xff1a;对于目录&#xff0c;该命令列出该目录下的所有子目录与文件。对于文件&#xff0c;将列出文件名以及信息。 常用选项&#xff1a; -a列出目录下的所有文件&#xff0c;包括以 . 开头的隐含文件。 -l列出文件的详细信息 举例&#xff1a; rooti…

智能化健身房管理:Spring Boot与Vue的创新解决方案

作者介绍&#xff1a;✌️大厂全栈码农|毕设实战开发&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 &#x1f345;获取源码联系方式请查看文末&#x1f345; 推荐订阅精彩专栏 &#x1f447;&#x1f3fb; 避免错过下次更新 Springboot项目精选实战案例 更多项目…

【Vue】简易博客项目跟做

项目框架搭建 1.使用vue create快速搭建vue项目 2.使用VC Code打开新生成的项目 端口号简单配置 修改vue.config.js文件&#xff0c;内容修改如下 所需库安装 npm install vue-resource --save --no-fund npm install vue-router3 --save --no-fund npm install axios --save …

Hadoop简介及单点伪分布式安装

目录 1. 大数据2. Hadoop简介3. Hadoop伪分布式安装4. Hadoop启动参考 1. 大数据 大数据的定义&#xff1a;一种规模大到在获取、存储、管理、分析方面大大超出传统数据库软件工具能力范围的数据集合。   特征&#xff1a;   1.海量的数据规模   2.快速的数据流转   3.…

windows server2019下载docker拉取redis等镜像并运行项目

一、基本概念 1、windows server 指由微软公司开发的“Windows”系列中的“服务器”版本。这意味着它是基于Windows操作系统的&#xff0c;但专门设计用于服务器环境&#xff0c;而不是普通的桌面或个人用户使用。主要用途包括服务器功能、用户和资源管理、虚拟化等 2、dock…

使用最新版的wvp和ZLMediaKit搭建Gb28181测试服务器

文章目录 说明安装1.安装nodejs简介安装步骤 2.安装java环境3.安装mysql安装修改密码 4.安装redis5.安装编译器6.安装cmake7.安装依赖库8.编译ZLMediaKit9.编译wvp-GB28181-pro 配置1.ZLMediaKit配置2.wvp-GB28181-pro配置2.1.配置ZLMediaKit连接信息2.2.28181服务器的配置2.3.…