念心卓

用户名：uq_80412005216

访问量：2762

签　名：

人不自渡，天也难助

等　　级
排　　名	1591
经　　验	2767
参赛次数	2
文章发表	24
年　　龄	0
在职情况	学生
学　　校	哔哩哔哩大学
专　　业	软件工程

　　自我简介：

TA的其他文章

链表的基本操作（C语言版）
浏览：88

链表的删除练习(C语言版)
浏览：319

双向循环链表(C语言版)
浏览：69

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

归并排序（Java代码）

　　作者: 念心卓　　　　发表时间：2021-08-18 15:33:25 浏览：139　|　评论：0　

原题链接：数据结构-归并排序

```java
package datastrutures;

import java.util.Scanner;

/*
 * 题目 1719: 数据结构-归并排序
 */
public class P_1719 {

public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = scanner.nextInt();
		}
		int[] temp = new int[arr.length];//临时数组
		mergeSort(arr, 0,arr.length-1, temp);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		scanner.close();
	}
	//编写归并排序
	
	//1. 首先编写子序列合并算法
	/**
	 * 
	 * @param arr 待排序的原始数组
	 * @param left 左索引
	 * @param mid 中间索引
	 * @param right 右索引
	 * @param temp 中转数组
	 * 因为是合并，即是说arr[left..mid],arr[mid+1..right]；所以要一个mid
	 */
	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		int l = left;//用来表示左子序列的初始下标
		int m = mid+1;//用来表示右子序列的初始下标
		int t = 0;//用来表示临时数组的下标
		while(l <= mid && m <= right) {
			//如果左边的有序序列当前元素小于等于右边的有序序列当前元素
			//就将左边的当前元素放到临时数组中
			//然后两者的索引分别后移
			if(arr[l] <= arr[m]) {
				temp[t] = arr[l];
				l++;
				t++;
			}else {
				temp[t] = arr[m];
				t++;
				m++;
			}
		}
		//当还有剩余，就把剩余的直接放入临时数组temp中
		while(l <= mid) {
			temp[t] = arr[l];
			l++;
			t++;
		}
		while(m <= right) {
			temp[t] = arr[m];
			m++;
			t++;
		}
		//再将临时数组中的元素放回到原数组中
		t = 0;
		int tempLeft = left;
		while(tempLeft <= right) {
			arr[tempLeft] = temp[t];
			t++;
			tempLeft++;
		}
	}
	//2. 编写2-路归并的递归算法
	public static void mergeSort(int[] arr,int left, int right, int[] temp) {
		if(left < right) {
			int mid = (left+right)/2;
			mergeSort(arr, left, mid, temp);//左归并递归
			mergeSort(arr, mid+1, right, temp);//右归并递归
			//最后再将两个数组合并
			merge(arr, left, mid, right, temp);
		}
	}
}

```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

念心卓

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

【计算两点间的距离】（C语言代码）

C语言训练-求函数值（C语言代码）

校门外的树（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

归并排序（Java代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

淘淘的名单（C语言代码）

简单的a+b （C语言代码）

字符串输入输出函数（C语言代码）

C语言训练-自守数问题（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （用指针求解）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）(一般方法：辗转相除法)

念心卓

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

【计算两点间的距离】 （C语言代码）

C语言训练-求函数值 （C语言代码）

校门外的树 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

归并排序（Java代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

淘淘的名单 （C语言代码）

简单的a+b （C语言代码）

字符串输入输出函数 （C语言代码）

C语言训练-自守数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （用指针求解）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）(一般方法：辗转相除法)

【计算两点间的距离】（C语言代码）

C语言训练-求函数值（C语言代码）

校门外的树（C语言代码）

　　评论区

淘淘的名单（C语言代码）

字符串输入输出函数（C语言代码）

C语言训练-自守数问题（C语言代码）