排序算法—归并排序【附代码】

小婷同学_4650

小婷同学_4650

2019-08-22

2034人浏览

转载

什么是归并排序?

  归并排序简单来讲,就是将两个有序的序列整合到一起。

推荐教程:PHP视频教程

如何将两个有序的序列整合到一起呢?

  那么我们假设,现在有 M={m1 ,m2,m3,....,mx}序列和 N = {n1,n2,n3,....,ny}序列,这两个序列已经是有序的序列,首先创建一个空序列 K = {},那么接着将 m1 和 n1 进行比较,加入 m1 

既然归并排序是整合有序序列,那么岂不是不能排序无序序列,这条件也太苛刻了点吧?

  归并排序是建立在分治法的基础上进行操作的,也就是可以将一个完全无序的序列进行无线分割以达到有序序列,比如:现在有 M={m1 ,m2,m3,....,mx},M序列是完全无序的序列,那么此时可以将 M 序列分成若干个小序列——{m1,m2},{m3,m4}....{mx-1,mx};此时这些序列就是有序的,那么就可以通过归并操作进行排序,所以归并排序也可以排序无序序列,且速度仅次于快速排序,属于稳定排序。

如何分割序列?

  上个问题已经提过,归并排序是建立在分治的基础上进行操作的,其中分治的体现就体现在分割序列上,比如:现在有M={m1 ,m2,m3,....,mx},第一次分割:M1 = {m1,m2,...,m(x+1)/2},M2 = {m(x+1)/2 +1,m(x+1)/2 +2,...,mx},第一次分割之后得到 M1 和 M2 序列,然后再分割 M1 和 M2 ,分割若干次之后得到 x/2 + x%2 个序列,然后再逐一进行归并操作。

该算法具体步骤:

  1、规定首指针 left 和mid(left指向序列1的首元素,right 指向序列2的首元素)

  2、比较 left 和 mid 的大小,将小的元素放入新建的空间中

  3、重复步骤2,直到其中一个序列遍历完毕

  4、将剩下的未加入新建空间中的元素直接复制粘贴进新建空间

千问输入法
千问输入法

一款将语音输入与AI文字润色结合的智能输入法。

下载

该算法的核心步骤:

  1、使用分治法(递归)分割序列

  2、比较 left 和 mid 的大小 , 将小的元素的添加进入新建空间

讲述完毕,贴上代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 排序__归并排序
{
    class 归并
    {

        public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000};
        static void Main(string[] args)
        {
            Sort(arr, 0, arr.Length -1);
            foreach (var item in arr)
            {
                Console.Write(item + "  ");
            }
            Console.ReadKey();
        }

        public static void Sort(int []a,int left,int right)
        {
            if (left >= right) return;
            else
            {
                int mid = (left + right) / 2;                //@1
                Sort(a, left, mid);
                Sort(a, mid + 1, right);
                MergeSort(a, left, mid, right);
            }
        }

        public static void MergeSort(int []a,int left,int mid,int right)
        {
            int[] Arr = new int[right - left + 1];
            int l = left, m = mid +1 , k = 0;           //@2
            while ( m  a[m]) Arr[k++] = a[m++];
                else Arr[k++] = a[l++];
            }
            while (m <p><span style="font-size: 18px;"><strong>代码解读:</strong></span><span style="font-size: 18px;"></span><br></p><p><span style="font-size: 18px;"></span></p><p>  @1 :Sort()函数完成了序列的分割,每一次递归都将序列分成两半,直到不能分隔为止。</p><p>  @2 :l 代表序列1的首元素,m 代表序列2的首元素,k代表新建数组Arr的已有元素个数</p><p>  @3 :序列1的首元素和序列2的首元素进行比较,将小的放入 Arr 中,且序列游标后移,直到其中一个序列的元素遍比较完毕</p><p>  @4 :在序列1 和序列2的比较过程中,可能出现序列1已经全部添加进了 Arr 中,但是序列2还没有,则将剩下的未比较的元素直接复制进入 Arr 中</p><p><span style="font-size: 18px;"><strong>总结:</strong></span></p><p>  以上代码并不是真正意义上的分割数组,只是做了一个逻辑分割,没有像其他代码一样将分割后的数组填入一个新的数组,那样做的话会对速度和内存产生一点影响,虽然微乎其微,但是总归是没这么好的,在归并操作上,需要注意的是参数不要越界(我当时就想了很久为什么 @2 上面的 m 要等于 mid +1 而不是 mid ,其实道理很简单,因为mid是属于左序列,从 mid+1 开始才属于右序列,将m = mid +1  改成 m = mid 不是不行,只是后面的代码也需要改,但是没有必要多做一次无用比较,这个问题我当时真是想了半天...),其实只要理清楚其中的逻辑关系,这样代码就能做到信手拈来。</p>

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

排序算法

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

20

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

60

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

60

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

20

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

60

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

40

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

180

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

140

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

160

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习