当前位置:首页 » 《休闲阅读》 » 正文

AcWing算法基础课-787归并排序-Java题解

10 人参与  2024年09月10日 10:41  分类 : 《休闲阅读》  评论

点击全文阅读


heweilai-bolg-title-image-of-the-article

大家好,我是何未来,本篇文章给大家讲解《AcWing算法基础课》787 题——归并排序。本文详细介绍了归并排序的算法思路,包括分解、合并和递归排序三个主要步骤。通过 Java 代码实现,展示了如何将数组递归分解至单个元素,再逐步合并成有序数组。

文章目录

❓题目描述?算法思路✅Java代码?参考

❓题目描述

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行,第一行包含整数 n。

第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整个数列。

输出格式

输出共一行,包含 n 个整数,表示排好序的数列。

数据范围

1≤n≤100000

输入样例:

53 1 2 4 5

输出样例:

1 2 3 4 5

?算法思路

分解:将数组从中间分成两个子数组,直到每个子数组只包含一个元素。这一步通过递归实现,确保每个子数组都是有序的(单个元素自然是有序的)。合并:将两个有序的子数组合并成一个有序的数组。这一步是归并排序的关键。合并过程中,程序会比较两个子数组中的元素,按顺序将较小的元素放入临时数组中,直到所有元素都被合并。递归排序:在递归的每一层,程序都会对分解后的子数组进行排序,然后合并结果。最终,整个数组会被排序。

具体实现步骤:

基本检查:首先,检查传入的数组部分是否只有一个元素或为空。如果是,则不需要进一步排序,直接返回。计算中间位置:计算当前数组部分的中间位置,这个中间位置将用于将数组分成两部分。递归排序左半部分:对数组的左半部分(从左边界到中间位置)进行递归排序。递归排序右半部分:对数组的右半部分(从中间位置的下一个位置到右边界)进行递归排序。初始化合并变量:初始化三个变量:k用于跟踪临时数组的索引,i用于遍历左半部分的数组,j用于遍历右半部分的数组。合并两个有序数组:比较左半部分和右半部分的元素,将较小的元素放入临时数组tmp中,直到其中一个部分的元素全部放入临时数组。处理左半部分剩余元素:如果左半部分还有剩余元素,将它们全部放入临时数组。处理右半部分剩余元素:如果右半部分还有剩余元素,将它们全部放入临时数组。将临时数组复制回原数组:将临时数组tmp中的元素复制回原数组a的相应位置,完成合并排序。

时间复杂度:O(n log n)
空间复杂度:O(n)
稳定排序:在合并过程中,相等元素的次序保持不变。

✅Java代码

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.StreamTokenizer;public class Aw787 {// 创建一个StreamTokenizer用于读取输入static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));// 读取下一个整数的方法static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}static int n; // 存储数组的大小static int[] nums = new int[100000 + 10]; // 存储输入的数组,预留一些额外的空间static int[] tmp = new int[100000 + 10]; // 临时数组,用于合并排序public static void main(String[] args) throws IOException {n = nextInt(); // 读取数组的大小for (int i = 0; i < n; i++) {nums[i] = nextInt(); // 读取数组的每个元素}mergeSort(0, n - 1, nums); // 调用归并排序方法对数组进行排序for (int i = 0; i < n; i++) {System.out.print(nums[i] + " "); // 输出排序后的数组}}// 归并排序方法,参数为数组的起始和结束索引,以及数组本身static void mergeSort(int l, int r, int[] a) {if (l >= r) { // 如果起始索引大于或等于结束索引,则直接返回return;}int mid = l + r >> 1; // 计算中间索引mergeSort(l, mid, a); // 递归排序左半部分mergeSort(mid + 1, r, a); // 递归排序右半部分// i表示左子数组的起始位置,j表示右子数组的起始位置// k表示tmp的结束位置int k = 0, i = l, j = mid + 1; // 初始化指针k, i, jwhile (i <= mid && j <= r) { // 合并两个有序子数组if (a[i] <= a[j]) { // 如果左半部分的元素小于或等于右半部分的元素tmp[k++] = a[i++]; // 将左半部分的元素放入临时数组} else {tmp[k++] = a[j++]; // 否则将右半部分的元素放入临时数组}}while (i <= mid) { // 如果左半部分还有剩余元素tmp[k++] = a[i++]; // 将剩余元素放入临时数组}while (j <= r) { // 如果右半部分还有剩余元素tmp[k++] = a[j++]; // 将剩余元素放入临时数组}for (i = l, j = 0; i <= r; i++, j++) { // 将临时数组中的元素复制回原数组a[i] = tmp[j];}}}

?参考

https://www.acwing.com/problem/content/789/https://www.hello-algo.com/chapter_sorting/merge_sort/

作者:程序员何未来-heweilai.com


?推荐阅读

AcWing算法基础课-786第k个数-Java题解AcWing算法基础课-785快速排序-Java题解【七夕节实践】把爱心代码放在自己的网站上是什么体验?

欢迎关注我的博客:@程序员何未来,持续为你输出有价值的技术文章~
你们的点赞? 收藏⭐ 留言?️ 关注✅
是我持续创作,输出优质内容的最大动力!谢谢!

文章关键词:算法,计算机算法,算法题解,算法竞赛,Java,数据结构,AcWing算法基础课


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/157656.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 纪君范,亓霏霏小说完本章节前文+全篇阅读(被小三的反击战)连载中
  • 陈春花,池言(重生后,摆脱吸血鬼老公一家)前文+全本完整阅读预售作品抢先看
  • 错认皇太女后,三个皇夫悔疯了后续结局_春桃长青魏昭看点十足_小说后续在线阅读_无删减免费完结_
  • (重生后,恶毒女配拿稳白月光剧本)江朝华燕景最终篇章(江朝华燕景)全书在线无广告高口碑小说
  • 女儿遇险命悬一线,我却见死不救后续+完结_小姑娘雷达安静读者推荐_小说后续在线阅读_无删减免费完结_
  • 黎夏林意深:结局+番外新上热文新章速递京港缠绵,他独宠娇梅:结局+番外评价五颗星
  • 陈春花,池言小说全文免费阅读(重生后,摆脱吸血鬼老公一家)全文免费阅读无弹窗_陈春花,池言小说全文免费阅读_笔趣阁
  • 女帝采补八百年:出世无敌怎么了?隐藏剧情_苏玄沐禹竹最新阅读_小说后续在线阅读_无删减免费完结_
  • 最新章节(重生后,恶毒女配拿稳白月光剧本)江朝华燕景:结局+番外精品选集附加章节列表
  • 云舒霍骞小说章节目录+章节前文(乡下真千金,带飞全国不装了)TXT清爽版在线
  • 陆晏周岁岁七零:首长娶了全村最懒的婆娘后续(陆晏周岁岁)(七零:首长娶了全村最懒的婆娘)完整章节列表_笔趣阁
  • 毕业告别旅⾏高分言情_姜雪高中毕业白月光每日分享_小说后续在线阅读_无删减免费完结_

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1