【数据结构】排序算法---归并排序

在这里插入图片描述

文章目录

  • 1. 定义
  • 2. 算法步骤
  • 3. 动图演示
  • 4. 性质
  • 5. 算法分析
  • 6. 代码实现
    • C语言——迭代版
    • C语言——递归版
    • Python
    • Java
    • C++——迭代版
    • C++——递归版
    • Go
  • 结语

1. 定义

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

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代；

2. 算法步骤

  • 把长度为n的输入序列分成两个长度为n/2的子序列；
  • 对这两个子序列分别采用归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列。

在这里插入图片描述

3. 动图演示

在这里插入图片描述

4. 性质

稳定性：

归并排序是高效的基于比较的稳定排序算法。

空间复杂度：

归并排序可以只使用 O ( 1 ) O(1) O(1)大小的辅助空间，但为便捷通常使用与原数组等长的辅助数组。所以通常情况下空间复杂度为 O ( n ) O(n) O(n)

时间复杂度：

归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 O ( n l o g n ) O(nlogn) O(nlogn)。

5. 算法分析

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O ( n l o g n ) O(nlogn) O(nlogn)的时间复杂度。代价是需要额外的内存空间。

6. 代码实现

C语言——迭代版

int min(int x, int y) {return x < y ? x : y;
}
void merge_sort(int arr[], int len) {int *a = arr;int *b = (int *) malloc(len * sizeof(int));int seg, start;for (seg = 1; seg < len; seg += seg) {for (start = 0; start < len; start += seg * 2) {int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++];}int *temp = a;a = b;b = temp;}if (a != arr) {int i;for (i = 0; i < len; i++)b[i] = a[i];b = a;}free(b);
}

C语言——递归版

void merge_sort_recursive(int arr[], int reg[], int start, int end) {if (start >= end)return;int len = end - start, mid = (len >> 1) + start;int start1 = start, end1 = mid;int start2 = mid + 1, end2 = end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k = start;while (start1 <= end1 && start2 <= end2)reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];while (start1 <= end1)reg[k++] = arr[start1++];while (start2 <= end2)reg[k++] = arr[start2++];for (k = start; k <= end; k++)arr[k] = reg[k];
}void merge_sort(int arr[], const int len) {int reg[len];merge_sort_recursive(arr, reg, 0, len - 1);
}

Python

def mergeSort(arr):import mathif(len(arr)<2):return arrmiddle = math.floor(len(arr)/2)left, right = arr[0:middle], arr[middle:]return merge(mergeSort(left), mergeSort(right))def merge(left,right):result = []while left and right:if left[0] <= right[0]:result.append(left.pop(0))else:result.append(right.pop(0));while left:result.append(left.pop(0))while right:result.append(right.pop(0));return result

Java

public class MergeSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);if (arr.length < 2) {return arr;}int middle = (int) Math.floor(arr.length / 2);int[] left = Arrays.copyOfRange(arr, 0, middle);int[] right = Arrays.copyOfRange(arr, middle, arr.length);return merge(sort(left), sort(right));}protected int[] merge(int[] left, int[] right) {int[] result = new int[left.length + right.length];int i = 0;while (left.length > 0 && right.length > 0) {if (left[0] <= right[0]) {result[i++] = left[0];left = Arrays.copyOfRange(left, 1, left.length);} else {result[i++] = right[0];right = Arrays.copyOfRange(right, 1, right.length);}}while (left.length > 0) {result[i++] = left[0];left = Arrays.copyOfRange(left, 1, left.length);}while (right.length > 0) {result[i++] = right[0];right = Arrays.copyOfRange(right, 1, right.length);}return result;}}

C++——迭代版

template<typename T> // 整数或浮点数皆可使用,若要使用物件(class)时必须设定"小与"(<)的运算子功能
void merge_sort(T arr[], int len) {T *a = arr;T *b = new T[len];for (int seg = 1; seg < len; seg += seg) {for (int start = 0; start < len; start += seg + seg) {int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++];}T *temp = a;a = b;b = temp;}if (a != arr) {for (int i = 0; i < len; i++)b[i] = a[i];b = a;}delete[] b;
}

C++——递归版

void Merge(vector<int> &Array, int front, int mid, int end) {// preconditions:// Array[front...mid] is sorted// Array[mid+1 ... end] is sorted// Copy Array[front ... mid] to LeftSubArray// Copy Array[mid+1 ... end] to RightSubArrayvector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);int idxLeft = 0, idxRight = 0;LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]for (int i = front; i <= end; i++) {if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {Array[i] = LeftSubArray[idxLeft];idxLeft++;} else {Array[i] = RightSubArray[idxRight];idxRight++;}}
}void MergeSort(vector<int> &Array, int front, int end) {if (front >= end)return;int mid = (front + end) / 2;MergeSort(Array, front, mid);MergeSort(Array, mid + 1, end);Merge(Array, front, mid, end);
}

Go

func mergeSort(arr []int) []int {length := len(arr)if length < 2 {return arr}middle := length / 2left := arr[0:middle]right := arr[middle:]return merge(mergeSort(left), mergeSort(right))
}func merge(left []int, right []int) []int {var result []intfor len(left) != 0 && len(right) != 0 {if left[0] <= right[0] {result = append(result, left[0])left = left[1:]} else {result = append(result, right[0])right = right[1:]}}for len(left) != 0 {result = append(result, left[0])left = left[1:]}for len(right) != 0 {result = append(result, right[0])right = right[1:]}return result
}

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！

带你初步了解排序算法：https://blog.csdn.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.csdn.net/2301_80191662/article/details/142300973
希尔排序：https://blog.csdn.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.csdn.net/2301_80191662/article/details/142312028
堆排序：https://blog.csdn.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.csdn.net/2301_80191662/article/details/142324131
快速排序：https://blog.csdn.net/2301_80191662/article/details/142324307
归并排序：https://blog.csdn.net/2301_80191662/article/details/142350640
计数排序：https://blog.csdn.net/2301_80191662/article/details/142350741
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564

在这里插入图片描述

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

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

相关文章

CentOS7.9环境上NFS搭建及使用

CentOS7.9环境上NFS搭建及使用

Linux环境NFS搭建及使用 1. 服务器规划2. NFS服务器配置2.1 主机名设置2.2 nfs安装2.2.1 repo文件替换2.2.2 NFS服务安装 2.3 nfs配置2.4 服务查看2.5 资源发布2.6 配置nfs服务开机自启2.7 端口开放 3.应用服务器配置3.1 主机名设置3.2 nfs安装3.2.1 repo文件替换3.2.2 NFS服务…
阅读更多...
你真的需要理解Diffusion（扩散模型），它在视觉领域具有无与伦比的美丽！

你真的需要理解Diffusion（扩散模型），它在视觉领域具有无与伦比的美丽！

【Vision结合Diffusion】模型的研究方向&#xff0c;探索了如何利用扩散模型在数据空间中模拟随机游走的特性&#xff0c;以生成高质量和逼真的图像。这一领域的研究&#xff0c;通过结合视觉感知和文本描述&#xff0c;推动了图像合成技术的发展&#xff0c;尤其是在个性化图像…
阅读更多...
对人像图添加指定光源，再进行二次扩图

对人像图添加指定光源，再进行二次扩图

在一些业务场景中&#xff0c;需要对人像图片添加特定光源&#xff0c;来增加氛围感&#xff0c;例如赛博朋克科技、海边夕阳余晖、以及红蓝相间的高冷&#xff1b;但实现这个功能的难点是&#xff1a;如何将光源与原图片融合&#xff0c;在图片上产生正常光的镜面反射&#xf…
阅读更多...
从数据仓库到数据中台再到数据飞轮：我了解的数据技术进化史

从数据仓库到数据中台再到数据飞轮：我了解的数据技术进化史

这里写目录标题 前言数据仓库&#xff1a;数据整合的起点数据中台&#xff1a;数据共享的桥梁数据飞轮&#xff1a;业务与数据的双向驱动结语 前言 在当今这个数据驱动的时代&#xff0c;企业发展离不开对数据的深度挖掘和高效利用。从最初的数据仓库&#xff0c;到后来的数据…
阅读更多...
工业一体机在汽车零部件工厂ESOP系统中的关键作用

工业一体机在汽车零部件工厂ESOP系统中的关键作用

在当今竞争激烈的汽车市场中&#xff0c;汽车零部件工厂的高效生产和严格质量控制至关重要。而工业一体机在汽车零部件工厂的 ESOP&#xff08;电子标准化作业程序&#xff09;系统中发挥着关键作用。 一、汽车零部件工厂面临的挑战 汽车零部件的生产过程复杂且要求严格&#…
阅读更多...
【sgCreateCallAPIFunctionParam】自定义小工具：敏捷开发→调用接口方法参数生成工具

【sgCreateCallAPIFunctionParam】自定义小工具：敏捷开发→调用接口方法参数生成工具

<template><div :class"$options.name" class"sgDevTool"><sgHead /><div class"sg-container"><div class"sg-start"><div style"margin-bottom: 10px">参数列表[逗号模式]<el-too…
阅读更多...
soc及其相关概念

soc及其相关概念

用户无法直接操作内存&#xff0c;只能让内存映射到用户空间然后操作 1. 内存映射&#xff08;Memory-Mapped Files&#xff09;内存映射文件是一种方法&#xff0c;它允许一个或多个进程将一个文件或者一个匿名区域映射到它们各自的虚拟地址空间中。当文件被映射到内存后&…
阅读更多...
Android WebView H5 Hybrid 混和开发

Android WebView H5 Hybrid 混和开发

对于故乡&#xff0c;我忽然有了新的理解&#xff1a;人的故乡&#xff0c;并不止于一块特定的土地&#xff0c;而是一种辽阔无比的心情&#xff0c;不受空间和时间的限制&#xff1b;这心情一经唤起&#xff0c;就是你已经回到了故乡。——《记忆与印象》 前言 移动互联网发展…
阅读更多...
前端开发之迭代器模式

前端开发之迭代器模式

在前端开发中&#xff0c;设计模式是提升代码可读性、可扩展性和可维护性的关键。迭代器模式&#xff08;Iterator Pattern&#xff09;是行为型设计模式中的一种&#xff0c;能够让我们顺序访问一个集合中的元素&#xff0c;而不暴露其底层的结构。在 TypeScript 这样具有类型…
阅读更多...
Golang | Leetcode Golang题解之第406题根据身高重建队列

Golang | Leetcode Golang题解之第406题根据身高重建队列

题目&#xff1a; 题解&#xff1a; func reconstructQueue(people [][]int) (ans [][]int) {sort.Slice(people, func(i, j int) bool {a, b : people[i], people[j]return a[0] > b[0] || a[0] b[0] && a[1] < b[1]})for _, person : range people {idx : pe…
阅读更多...
element-ui 日期选择器设置禁用日期

element-ui 日期选择器设置禁用日期

element-ui 日期选择器设置禁用日期 效果图如下&#xff1a; 2024-09-01 到2024-09-18之间的日期都不可选 2024-01-01之前的日期都不可选 官方文档中 picker-options 相关的介绍 实现功能&#xff1a; ​ 某仓库有限制最大可放置资产数量&#xff0c;且资产出借和存放都有…
阅读更多...
高端论坛报告分享 | 李维森：中国地理信息产业发展报告（2024）

高端论坛报告分享 | 李维森：中国地理信息产业发展报告（2024）

本报告为中国地理信息产业协会会长李维森在“2024中国地理信息产业大会”所作报告《中国地理信息产业发展报告&#xff08;2024&#xff09;》。转载请注明来源于中国地理信息产业协会。 本报告为中国地理信息产业协会会长李维森在“2024中国地理信息产业大会”所作报告《中国地…
阅读更多...
Linux系统应用之知识补充——OpenEuler（欧拉）的安装和基础配置

Linux系统应用之知识补充——OpenEuler（欧拉）的安装和基础配置

前言 这篇文章将会对OpenEuler的安装进行详解&#xff0c;一步一步跟着走下去就可以成功 注意 &#xff1a;以下的指令操作最好在root权限下进行&#xff08;即su - root&#xff09; ☀️工贵其久&#xff0c;业贵其专&#xff01; 1、OpenEuler的安装 这里我不过多介绍&a…
阅读更多...
GPT-4-Turbo 和 Claude-3.5-Sonnet 图片识别出答题的是否正确 进行比较

GPT-4-Turbo 和 Claude-3.5-Sonnet 图片识别出答题的是否正确 进行比较

1、比较的图片&#xff1a; 使用GPT-4-Turbo 输入的 提问&#xff1a; 识别图片中的印刷字和手写字&#xff0c;如果写错的给一个正确答案 图片 回复&#xff1a; 在图片中&#xff0c;印刷字显示的是一系列的英语填空练习题&#xff0c;而手写字则是填入空白处的答案。以…
阅读更多...
运行容器应用

运行容器应用

kubernetes通过各种controller来管理pod的生命周期&#xff0c;为了满足不同的业务场景&#xff0c;kubernetes开发了Deployment&#xff0c;ReplicaSet&#xff0c;DaemonSet&#xff0c;StatefulSet&#xff0c;Job等多种ControllerDeployment&#xff1a; kubectl run nginx…
阅读更多...
WebSocket 协议

WebSocket 协议

原文地址&#xff1a;xupengboo WebSocket WebSocket 是 HTML5 开始提供的一种在单个 TCP 连接上进行全双工通讯的协议。 在 WebSocket API 中&#xff0c;浏览器和服务器只需要完成一次握手&#xff0c;两者之间就直接可以创建持久性的连接&#xff0c;并进行双向数据传输。…
阅读更多...
MYSQL出现“mysql不是内部或外部命令，也不是可运行的程序”

MYSQL出现“mysql不是内部或外部命令，也不是可运行的程序”

目录 1.配置环境变量 2.重新打开cmd测试 1.配置环境变量 进入mysql目录下的bin文件夹 复制目录 我们按下win&#xff0c;然后搜索“环境” 粘贴刚刚复制的目录 2.重新打开cmd测试 可以看到此时mysql正常
阅读更多...
基于web的工作管理系统设计与实现

基于web的工作管理系统设计与实现

博主介绍&#xff1a;专注于Java vue .net php phython 小程序 等诸多技术领域和毕业项目实战、企业信息化系统建设&#xff0c;从业十五余年开发设计教学工作 ☆☆☆ 精彩专栏推荐订阅☆☆☆☆☆不然下次找不到哟 我的博客空间发布了1000毕设题目 方便大家学习使用 感兴趣的…
阅读更多...
【Redis】Redis 典型应用 - 分布式锁原理与实现

【Redis】Redis 典型应用 - 分布式锁原理与实现

目录 Redis 典型应⽤ - 分布式锁什么是分布式锁分布式锁的基础实现引⼊过期时间引⼊校验 id引⼊ lua引⼊ watch dog (看⻔狗)引⼊ Redlock 算法其他功能 Redis 典型应⽤ - 分布式锁 什么是分布式锁 在⼀个分布式的系统中&#xff0c; 也会涉及到多个节点访问同⼀个公共资源的…
阅读更多...
飞书项目管理使用攻略

飞书项目管理使用攻略

文章目录 项目管理项目管理的方法和工具项目管理方法&#xff1a;项目管理工具 飞书项目管理平台 创建空间需求管理缺陷管理人员排期飞书也可以创建敏捷开发管理.删除空间 参考文章 项目管理 项目管理是指在项目活动中运用专门的知识、技能、工具和方法&#xff0c;使项目能够…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发