doclist 阅读(13) 评论(0)

刷题过程中常常遇到排序问题,Java中自带的sort方法可以非常方便的帮助我们进行排序。

常见的排序问题有两种情形:

1.对一个数组进行排序。

2.对自定义类型的类进行排序。

一,对数组进行排序:

通常情况下我们可以使用Array.sort()来对数组进行排序,有以下3种情况:

1.Array.sort(int[] a)

 

直接对数组进行升序排序

2.Array.sort(int[] a , int fromIndex, int toIndex)

 

对数组的从fromIndex到toIndex进行升序排序

3.新建一个comparator从而实现自定义比较

具体方法如下:

 

import java.util.*;
public class no {
    public static void main(String []args)
    {
        int[] ints=new int[]{2,324,4,57,1};

        System.out.println("增序排序后顺序");
        Arrays.sort(ints);
        for (int i=0;i<ints.length;i++)
        {
            System.out.print(ints[i]+" ");
        }


        System.out.println("\n减序排序后顺序");
        //要实现减序排序,得通过包装类型数组,基本类型数组是不行滴
        Integer[] integers=new Integer[]{2,324,4,4,6,1};
        Arrays.sort(integers, new Comparator<Integer>()
        {
            public int compare(Integer o1, Integer o2)
            {
                return o2-o1;
            }


            public boolean equals(Object obj)
            {
                return false;
            }
        });
        for (Integer integer:integers)
        {
            System.out.print(integer+" ");
        }



        System.out.println("\n对部分排序后顺序");
        int[] ints2=new int[]{212,43,2,324,4,4,57,1};
        //对数组的[2,6)位进行排序

        Arrays.sort(ints2,2,6);
        for (int i=0;i<ints2.length;i++)
        {
            System.out.print(ints2[i]+" ");
        }

    }
}

 

二,对自定义类进行排序

当我们处理自定义类型的排序时,一般将自定义类放在List种,之后再进行排序

一般我们对自定义类型数据进行重写Comparator来进行对数据进行比较

具体方法如下:

public static class Adam
{
    int ID ;
    int val ;
    String name ;
    Adam(int ID , String name , int val)
    {
    this.ID = ID ;
    this.name = name ;
    this.val = val ;
      }
}
Collections.sort(list, new Comparator<Object>(){      //我们希望对自定义Adam中的ID进行排序
    public int compare(Object a , Object b)
    {
        Adam student1 = (Adam)a ;
        Adam student2 = (Adam)b ;
        return student1.ID - student2.ID ;
    }
});

下面来分析两道题目:

1028 List Sorting (25 分)

Excel can sort records according to any column. Now you are supposed to imitate this function.

Input Specification:

Each input file contains one test case. For each case, the first line contains two integers N (105​​) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, each contains a record of a student. A student's record consists of his or her distinct ID (a 6-digit number), name (a string with no more than 8 characters without space), and grade (an integer between 0 and 100, inclusive).

Output Specification:

For each test case, output the sorting result in N lines. That is, if C = 1 then the records must be sorted in increasing order according to ID's; if C = 2 then the records must be sorted in non-decreasing order according to names; and if C = 3 then the records must be sorted in non-decreasing order according to grades. If there are several students who have the same name or grade, they must be sorted according to their ID's in increasing order.

Sample Input 1:

3 1
000007 James 85
000010 Amy 90
000001 Zoe 60

Sample Output 1:

000001 Zoe 60
000007 James 85
000010 Amy 90

Sample Input 2:

4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98

Sample Output 2:

000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60

Sample Input 3:

4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90

Sample Output 3:

000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90

显然我们新建的类中应该包含ID,name,val(成绩) ,之后我们新建三种比较器便可以完成这三种比较方式了,代码如下:
import java.util.*;
public class ListSorting2 {
    public static void main(String args[])
    {
        Scanner scanner = new Scanner(System.in) ;
        int nums = scanner.nextInt() ;
        int choose = scanner.nextInt() ;
        scanner.nextLine() ;
        List<Adam> list = new ArrayList<>() ;
        for(int i = 0 ; i < nums ; i ++)
        {
            String s = scanner.nextLine() ;
            String[] s1 = s.split(" ") ;
            Adam student = new Adam(Integer.parseInt(s1[0]),s1[1],Integer.parseInt(s1[2])) ;
            list.add(student) ;
        }
        scanner.close();
        if(choose == 1)
            Collections.sort(list, new Comparator<Object>(){
                public int compare(Object a , Object b)
                {
                    Adam student1 = (Adam)a ;
                    Adam student2 = (Adam)b ;
                    return student1.ID - student2.ID ;
                }
            });
        else if(choose == 2)
            Collections.sort(list,new Comparator<Object>(){
                public int compare(Object a , Object b)
                {
                    Adam student1 = (Adam)a ;
                    Adam student2 = (Adam)b ;
                    int n = student1.name.compareTo(student2.name) ;
                    if(n == 0)
                    {
                        return student1.ID - student2.ID ;
                    }
                    else return n ;
                }
            });
        else
        {
            Collections.sort(list,new Comparator<Object>(){
                public int compare(Object a , Object b)
                {
                    Adam student1 = (Adam)a ;
                    Adam student2 = (Adam)b ;
                    int n = student1.val - student2.val ;
                    if(n == 0) return student1.ID - student2.ID ;
                    else
                        return n ;
                }
            });
        }
        for(int i = 0 ; i < list.size() ; i ++)
        {
            System.out.printf("%06d",list.get(i).ID);
            System.out.println(" "+list.get(i).name+" "+list.get(i).val);
        }
    }
    public static class Adam
    {
        int ID ;
        int val ;
        String name ;
        Adam(int ID , String name , int val)
        {
            this.ID = ID ;
            this.name = name ;
            this.val = val ;
        }
    }
}

再看一道题目:

1025 PAT Ranking (25 分)

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (300), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:

registration_number final_rank location_number local_rank

The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

Sample Input:

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85

Sample Output:

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

这到题目需要加入两种排序方式——考试地点的排名,以及总排名,所以这里我在每一个考场都建立了一个list进行排序,还有一个总的ranking对所有考生进行排序。
代码如下:
import java.util.*;
public class PATRanking {
    public static void main(String args[])
    {
        Scanner scanner = new Scanner(System.in) ;
        int locals = scanner.nextInt() ;
        int sum = 0 ;
        @SuppressWarnings("unchecked")
        List<Adam>[] list = new List[locals] ;
        List<Adam> ranking = new ArrayList<>() ;
        for(int i = 0 ; i < locals ; i ++)
        {
            list[i] = new ArrayList<>() ;
            int nums = scanner.nextInt() ;
            sum += nums ;
            scanner.nextLine() ;
            for(int j = 0 ; j < nums ; j ++)
            {
                String s = scanner.nextLine() ;
                String[] s1 = s.split(" ") ;
                Adam a = new Adam(s1[0],Integer.parseInt(s1[1]),i+1) ;
                list[i].add(a) ;
                ranking.add(a) ;
            }
        }
        scanner.close();
        for(int i = 0 ; i < locals ; i ++)
        {
            Collections.sort(list[i], new Comparator<Object>(){
                public int compare(Object a , Object b)
                {
                    Adam student1 = (Adam)a ;
                    Adam student2 = (Adam)b ;
                    int n = student2.val - student1.val ;
                    if(n == 0) return student1.ID.compareTo(student2.ID) ;
                    else return n ;
                }
            });
            for(int j = 0 ; j < list[i].size() ; j ++)
            {
                if(j == 0)
                {
                    list[i].get(j).localrank = j + 1 ;
                    continue ;
                }
                if(list[i].get(j).val == list[i].get(j-1).val)
                    list[i].get(j).localrank = list[i].get(j-1).localrank ;
                else
                    list[i].get(j).localrank = j + 1 ;
            }
        }
        Collections.sort(ranking,new Comparator<Object>(){
            public int compare(Object a , Object b)
            {
                Adam student1 = (Adam)a ;
                Adam student2 = (Adam)b ;
                int n = student2.val - student1.val ;
                if(n == 0) return student1.ID.compareTo(student2.ID) ;
                else return n ;
            }
        });
        System.out.println(sum);
        for(int i = 0 ; i < ranking.size() ; i ++)
        {
            Adam a = ranking.get(i) ;
            if(i == 0)
            {
                a.rank = i + 1 ;
                System.out.println(a.ID+" "+a.rank+" "+a.local+" "+a.localrank);
                continue ;
                
            }
            if(ranking.get(i).val == ranking.get(i-1).val)
                ranking.get(i).rank = ranking.get(i-1).rank ;
            else
                a.rank = i + 1 ;
            System.out.println(a.ID+" "+a.rank+" "+a.local+" "+a.localrank);
        }
    }
    public static class Adam
    {
        String ID ;
        int val ;
        int rank ;
        int localrank ;
        int local ;
        Adam(String ID , int val , int local)
        {
            this.ID = ID ;
            this.val = val ;
            this.local = local ;
        }
    }
}