题解 | #成绩排序#Java归并稳定排序，内部类存数据

为啥排序题这么多人用sort啊？个人感觉这类题考的就是对排序算法的掌握。比如这个题一个考点就是哪些排序是稳定排序（冒泡、插入、归并、计数）。冒泡插入就是基本的O(n^2)，归并就是进阶的O(nlogn)。然后数据用内部类存储（用二维数组也可），然后在类里面写一个比较器用来应对正序逆序排序。

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int count=in.nextInt();
        int order=in.nextInt();
        ArrayList<Student> rank=new ArrayList<>();
        Main main=new Main();
        for(int i=0; i<count; i++){
            String name=in.next();
            Integer grade=in.nextInt();
            rank.add(main.new Student(name,grade));
        }
        if(rank.size()>1){
            main.mergeSort(rank,0,count-1,order);
        }
        for(Main.Student student: rank){
            System.out.println(student.name+" "+student.grade);
        }
    }

    void mergeSort(ArrayList<Student> seq, int left, int right, int order){
        if(left>=right){
            return;
        }
        int mid=(left+right)>>1;
        mergeSort(seq,left,mid,order);
        mergeSort(seq,mid+1,right,order);
        merge(seq,left,mid,right,order);
    }

    void merge(ArrayList<Student> seq, int left, int mid, int right, int order){
        ArrayList<Student> copy=new ArrayList<>(right-left+1);
        int i=left;
        int j=mid+1;
        while(i<=mid&&j<=right){
            if(seq.get(i).compareTo(seq.get(j),order))
                copy.add(seq.get(i++));
            else
                copy.add(seq.get(j++));
        }
        while(i<=mid){
            copy.add(seq.get(i++));
        }
        while(j<=right){
            copy.add(seq.get(j++));
        }
        for(Student student: copy){
            seq.set(left++,student);
        }
    }

    class Student{
        String name;
        Integer grade;

        Student(String name, Integer grade){
            this.name=name;
            this.grade=grade;
        }

        boolean compareTo(Student def, int order){
            if(order==1) return grade<=def.grade;
            return grade>=def.grade;
        }
    }
}