Kou

用户名：Kou

访问量：1689

签　名：

一个小白。

等　　级
排　　名	1667
经　　验	2718
参赛次数	0
文章发表	7
年　　龄	22
在职情况	学生
学　　校	南京传媒学院
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

题解 1716：快速排序
浏览：245

题解 1719: 数据结构-归并排序[Java]
浏览：216

数据结构-二叉排序树的基本操作(Java代码)
浏览：99

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

题解 1719: 数据结构-归并排序[Java]

　　作者: Kou　　　　发表时间：2021-03-25 19:12:12 浏览：216　|　评论：0　

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

```java
import java.util.Scanner;

public class Main {
    private static Comparable[] aux;
	
	//自底向上的归并排序
    private static void sort(Comparable[] arr) {
        int N = arr.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int lo = 0; lo < N - sz; lo = lo + sz + sz) {
                merge(arr, lo, lo + sz - 1, Math.min(N - 1, lo + sz + sz - 1));
            }
        }
    }

private static void merge(Comparable[] arr, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        if (hi + 1 - lo >= 0) {
            System.arraycopy(arr, lo, aux, lo, hi - lo + 1);
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {  //左边耗尽取右边
                arr[k] = aux[j++];
            } else if (j > hi) {    //右边耗尽取左边
                arr[k] = aux[i++];
            } else if (less(aux[j], aux[i])) {    //左边比右边大取右边
                arr[k] = aux[j++];
            } else { //右边比左边大取左边
                arr[k] = aux[i++];
            }
        }
    }

private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

private static void show(Comparable[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (i != arr.length - 1) {
                System.out.print(arr[i] + " ");
            } else {
                System.out.println(arr[i]);
            }
        }
    }

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Comparable[] arr = new Comparable[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.nextInt();
        }
        sort(arr);
        show(arr);
    }
}

```

0.0分

1 人评分

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

Kou

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

字符串输入输出函数（Java代码）

1065

人民币问题（C语言代码）

题解 1719: 数据结构-归并排序[Java]

评论区

精彩推荐

Minesweeper （C语言代码）

三进制小数（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

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

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

Wu-求圆的面积（C++代码）

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

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

Kou

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

字符串输入输出函数 （Java代码）

1065

人民币问题 （C语言代码）

题解 1719: 数据结构-归并排序[Java]

评论区

精彩推荐

Minesweeper （C语言代码）

三进制小数 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

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

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

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

Wu-求圆的面积 （C++代码）

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

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

字符串输入输出函数（Java代码）

人民币问题（C语言代码）

　　评论区

三进制小数（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

Wu-求圆的面积（C++代码）