归并排序之确定递归层数

题目

给定一维int型数组a[0,1,…,n-1], 使用归并排序方法, 对其进行从小到大排序, 请输出递归过程中自顶自下第三层的排序结果, 其中最顶层为第一层, 即最终的排序结果层.
归并排序划分请按a[0,mid=(0+n-1)/2], a[(0+n-1)/2+1, n-1]进行划分子问题.

Input

输入第1行有一个int型正整数m (m<100), 表示有m行输入.
每行输入的第一个数为int型正整数n (8<n<1000), 后面接着输入n个int型整数.

Output

输出m行, 每行为排好序的输出.

Sample Input

2
9 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1 0

Sample Output

7 8 9 5 6 3 4 1 2
7 8 9 5 6 2 3 4 0 1

代码实现:

#include<iostream>
#include<vector>
using namespace std;


// 将两个子数组合并成一个有序数组
void merge(vector<int> &arr,int left,int mid,int right){
    // 两个数组的长度
    int len1 = mid-left+1, len2 = right-mid;

    vector<int> a(len1),b(len2);

    // 对两个数组分别赋值
    for(int i = 0;i<len1;i++){
        a[i] = arr[left+i];
    } 
    for(int i = 0;i<len2;i++){
        b[i] = arr[mid+1+i];
    }

    // 对两个数组进行比较,结果放入arr数组
    int i = 0,j = 0,k = left;
    while(i<len1 && j<len2){
        if(a[i]<=b[j]){
            arr[k++] = a[i++];
        }else {
            arr[k++] = b[j++];
        }
    }

    // 其中一个数组没还遍历完,直接拷贝到arr数组后面
    while(i<len1){
        arr[k++] = a[i++];
    }
    while(j<len2){
        arr[k++] = b[j++];
    }
}


// 归并排序
void mergeSort(vector<int> &arr, int left, int right,int depth){
    if(left<right){
        int mid = left+(right-left)/2;

        // 分别对左右两半进行排序
        mergeSort(arr,left,mid,depth+1);
        mergeSort(arr,mid+1,right,depth+1);

        // 归并
        if(depth>=3){
            merge(arr,left,mid,right);
        }
        
    }
}



int main(){
    int m;
    //cout<< "请输入m, 表示m行:";
    cin >> m;
    cin.ignore();

    vector<vector<int> > res;

    for(int i = 0;i<m;i++){
        // 输入元素个数
        int n;
        cin >> n;
        // 输入n个元素
        vector<int> arr(n);
        for(int i = 0;i<n;i++){
            cin >> arr[i];
        }

        // 输入完元素之后,进行排序
        mergeSort(arr,0,n-1,1);

        res.push_back(arr);
    }

    // 打印
    for(int i = 0;i<m;i++){
        for(int j = 0;j<res[i].size();j++){
            cout << res[i][j] << " ";
        }
        cout<< endl;
    }
    return 0;
}

我觉得主要的难点是如何返回第三层这个中间排序结果,看了一些别人的解答后,我自己对着程序画了一个大概的思维流程图,能够理解为什么是要设置depth>=3才进行合并。

图示如下:
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

OLED透明屏的应用场景有哪些

OLED透明屏在其他领域的应用包括&#xff1a; 商业展示&#xff1a;在商业展示中&#xff0c;OLED透明屏可以作为展示窗口&#xff0c;展示产品信息、广告宣传和品牌形象。通过将透明屏幕安装在展柜、货架或商业窗口中&#xff0c;可以吸引顾客的注意力并提供引人注目的展示效…

霍尔电流传感器如何进行可靠性测试?主要应用在哪些领域?

霍尔电流传感器广泛应用于航空航天、电源监测、飞行器状态监测、变速驱动设备、焊接设备供电电源、新能源汽车蓄电池管理系统等领域&#xff0c;在电流检测领域中有着重要地位和实用价值&#xff0c;在电驱系统中被称为新能源汽车的动力“心脏”。因此&#xff0c;霍尔电流传感…

QML9、输入元素

1、输入元素(Input Element) 我们已经使用过MouseArea(鼠标区域)作为鼠标输入元素。这里我们将更多的介绍关于键盘输入的一些东西。我们开始介绍文本编辑的元素:TextInput(文本输入)和TextEdit(文本编辑)。 2、文本输入(TextInput) 文本输入允许用户输入一行文本…

WorkPlus定制化的沟通协作平台,助您实现企业级完全掌控

在企业沟通协作的领域&#xff0c;一种高度定制化的平台是至关重要的。WorkPlus作为一款领先的沟通协作平台&#xff0c;具备高度定制化的特点&#xff0c;能够满足企业各项需求。通过平台级定制扩展和上下游完全掌控&#xff0c;WorkPlus成为了企业实现定制化和完全掌控的理想…

excel如何加密(excel加密的三种方法)

Excel是一款广泛使用的办公软件&#xff0c;有时候我们需要对一些重要的Excel文件进行加密&#xff0c;以保证文件的安全性。下面将介绍3种常用的Excel加密方法。 方法一&#xff1a;通过路径文件-另存为-工具-常规选项-设置打开或修改权限密码&#xff08;密码只可以使数字、字…

虚幻引擎:如何进行关卡切换?

一丶非无缝切换 在切换的时候会先断开连接,等创建好后才会链接,造成体验差 蓝图中用到的节点是 Execute Console Command 二丶无缝切换 链接的时候不会断开连接,中间不会出现卡顿,携带数据转换地图 1.需要在gamemode里面开启无缝漫游,开启之后使用上面的切换方式就可以做到无缝…

矩阵起源加入 OpenCloudOS 操作系统开源社区,完成技术兼容互认证

近日&#xff0c;超融合异构云原生数据库 MatrixOne企业版软件 V1.0 完成了与 OpenCloudOS 的相互兼容认证&#xff0c;测试期间&#xff0c;整体运行稳定&#xff0c;在功能、性能及兼容性方面表现良好。 一、产品简介 矩阵起源 MatrixOrigin 致力于建设开放的技术开源社区和…

企业安全—三保一评

0x00 前言 本篇主要是讲解三保一评的基础知识&#xff0c;以及对为什么要进行这些内容的原因进行总结。 0x01 整体 1.概述 三保分别是&#xff0c;分保&#xff0c;等保&#xff0c;关保。 分保就是指涉密信息系统的建设使用单位根据分级保护管理办法和有关标准&#xff0c…

LeetCode【78. 子集】

78. 子集 中等 2.2K 相关企业 给你一个整数数组 nums &#xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集&#xff08;幂集&#xff09;。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&…

Vue框架项目,给容器添加水印watermark

1、在/utils下新增一个名为waterMark.js的脚本 具体水印样式可以在代码里自行调节style 参数 - 水印内容, 加水印的容器, 是否显示时间 let watermark {};function getCurrentDateTime() {const now new Date();const year now.getFullYear();const month String(now.ge…

Flink之SQL查询操作

SQL查询 基本SELECT查询生成测试数据WITHWHEREDISTINCTORDER BYLIMIT 窗口函数概述创建数据表滚动窗口 TUMBLE滑动窗口 HOP累积窗口 CUMULATE窗口偏移 聚合窗口聚合分组聚合OVER聚合 TOP-N普通Top-N窗口Top-N 联结Join查询内部等连接外部等连接间隔联结 集合操作UNION 和 UNION…

界面控件DevExtreme图表和仪表(v23.1) - 新功能(Angular,React,Vue,jQuery)

本文将为大家总结下DevExtreme在v23.1版本中发布的一些与图表和仪表盘相关的功能。 DevExtreme拥有高性能的HTML5 / JavaScript小部件集合&#xff0c;使您可以利用现代Web开发堆栈&#xff08;包括React&#xff0c;Angular&#xff0c;ASP.NET Core&#xff0c;jQuery&#…

数据结构(c语言版) 队列

链队列 要求&#xff1a;实现链队列的创建、初始化、入队、出队 &#xff08;先进先出&#xff09; 代码 // // Created by My.cy on 2023/10/19. // //链队列 创建、初始化、入队、出队 先进先出#include <stdio.h> #include <malloc.h>//定义结构体 struct…

“探秘!根据关键词搜索商品列表的虾皮API大揭露!“

要使用虾皮API根据关键词获取商品列表&#xff0c;您需要使用虾皮API的搜索功能。以下是使用Python和虾皮API根据关键词获取商品列表的基本步骤&#xff1a; 注册虾皮API账号并获取API凭证&#xff08;访问虾皮开放平台并创建应用以获取API凭证&#xff09;。安装必要的Python…

SPRINGBOOT整合CXF发布WEB SERVICE和客户端调用(用户和密码验证)

主要分为客户端和服务端 服务端 pom配置 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.4.3</version><relativePath/> <!-- lookup parent fro…

使用电脑上自带的软件进行远程连接

使用电脑上自带的软件进行远程连接 首先需要让你远程的电脑设置成允许远程连接 Windows R打开运行面板&#xff0c;然后输入sysdm.cpl命令&#xff0c;如下图&#xff1a; 选择“远程”选项卡&#xff0c;确保选中“允许远程连接到这台计算机”&#xff0c;如下图&#xff1…

如何在 Vue.js 中引入原子设计?

前言 原子设计是一种创建设计系统的方法&#xff0c;它将用户界面分解为可重用的小组件&#xff0c;即&#xff1a; Atoms 原子Molecules 分子Organisms 生物体Templates 模板Pages 页面 通过遵循模块化设计方法&#xff0c;原子设计可帮助团队创建一致、可缩放且可维护的 …

阻容降压电阻应用

公式&#xff1a;Xc1/2πfC 电流&#xff1a;IU/Xc 举例&#xff1a;1uf金属化聚丙烯膜电容的容抗是3184欧姆。电流是70ma。 实际应用中根据工作电流去倒推算电容。

Ionic组件 ion-avatar ion-icon ion-img ion-thumbnail

1 ion-avatar Avatars 是通常包裹 image or icon的圆形组件。它们可以用来表示一个person or an object。 Avatars 可以自己使用&#xff0c;也可以在任何元素内部使用。如果放置在ion-chip or ion-item内部&#xff0c;avatar 将调整大小以适应父组件。要将avatar 定位在item…

Ceph文件存储

1、存储基础 //单机存储设备 ●DAS&#xff08;直接附加存储&#xff0c;是直接接到计算机的主板总线上去的存储&#xff09; IDE、SATA、SCSI、SAS、USB 接口的磁盘 所谓接口就是一种存储设备驱动下的磁盘设备&#xff0c;提供块级别的存储 ●NAS&#xff08;网络附加存储&…