时间戳

首页 > 解决方案 > 如何使用自己的快速排序来决定具有多个输入数据的任务

java - 如何使用自己的快速排序来决定具有多个输入数据的任务

问题描述

我有一个排序任务。我需要对奥运会比赛的参与者进行排序，他们有解决问题的数量和罚分的数量。为此，我需要应用我编写的排序算法。解决问题数多的那一项得分越高，但如果解决的问题数相同，则罚分越低的那一项就越高。如果解决的问题和惩罚的数量相同，则按名称排序。输入示例中的第一个数字是参与者的数量，第二个是解决问题的数量，第三个是惩罚的数量。样本输入：

5

阿拉 4 100

吉纳 6 1000

哥沙 2 90

丽塔 2 90

蒂莫菲 4 80

样本输出：

基因

蒂莫菲

阿拉

哥沙

丽塔

也许可以通过哈希图以某种方式实现这一点？有解决问题的排序和惩罚的排序

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class EffectiveQuickSort {
    public static void quickSort(ArrayList<Integer> aList, Integer start, Integer end) {
        if (start == null && end == null) {
            start = 0;
            end = aList.size();
        }
        if (end - start > 1) {
            int p = partition(aList, start, end);
            quickSort(aList, start, p);
            quickSort(aList, p + 1, end);
        }
    }

    public static int partition(ArrayList<Integer> aList, int start, int end) {
        int pivot = aList.get(start);
        int i = start + 1;
        int j = end - 1;
        while (true) {
            while (i <= j && aList.get(i) <= pivot) {
                i++;
            }
            while (i <= j && aList.get(j) >= pivot) {
                j--;
            }
            if (i <= j) {
                Collections.swap(aList, i, j);
            }
            else {
                Collections.swap(aList, start, j);
                return j;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        if (n < 1 || n > 100000) {
            throw new Exception("invalid n");
        }
        HashMap<String, ArrayList<Integer>> participants = new HashMap<>();
        ArrayList<Integer> solved = new ArrayList<>();
        ArrayList<Integer> penalty = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] human = reader.readLine().split(" ");
            ArrayList<Integer> scores = new ArrayList<>();
            scores.add(Integer.parseInt(human[1]));
            scores.add(Integer.parseInt(human[2]));
            participants.put(human[0], scores);
            solved.add(Integer.parseInt(human[1]));
            penalty.add(Integer.parseInt(human[2]));
        }

        System.out.println("solved: " + solved + ", penalty: " + penalty + ", participants: "  + participants);
        quickSort(solved, null, null);
        System.out.println("sorted solved: " + solved);

        quickSort(penalty, null, null);
        System.out.println("sorted penalty: " + penalty);
    }
}

标签： java

解决方案

您不需要 hashMap。你需要：

  • 将信息放入每个参与者的班级（或记录）中。
  • 然后创建一个比较器来对记录进行排序。

类似于以下内容：

  • 分数是相反的，所以高者先到。
  • 然后，如果相等，则对惩罚进行排序，因此较低的优先。
record Participant(String getName, int getPenalty, int getScore) {
}
    
Comparator<Participant> comp =
            Comparator.comparingInt(Participant::getScore).reversed()
                    .thenComparing(Participant::getPenalty);

这是使用比较器的外观。您必须进行一些修改才能读取数据并转换为记录（或类）。

public class EffectiveQuickSort {
    
    record Participant(String getName, int getScore, int getPenalty) {
    }
    
    static Comparator<Participant> comp =
            Comparator.comparingInt(Participant::getScore).reversed()
                    .thenComparingInt(Participant::getPenalty);
    
    public static void main(String[] args) throws Exception {
        
        // list.of is immutable so add to an array list.
        List<Participant> participants = new ArrayList<>(
                List.of(new Participant("alla", 4, 100),
                        new Participant("gena", 6, 1000),
                        new Participant("gosha", 2, 90),
                        new Participant("rita", 2, 90),
                        new Participant("timofey", 4, 80)));
        quickSort(participants, 0, participants.size());
        participants
                .forEach(par -> System.out.println(par.getName()));
        
    }
    
    public static void quickSort(List<Participant> aList, int start,
            int end) {
        
        if (end - start > 1) {
            int p = partition(aList, start, end);
            quickSort(aList, start, p);
            quickSort(aList, p + 1, end);
        }
    }
    
    public static int partition(List<Participant> aList, int start,
            int end) {
        Participant pivot = aList.get(start);
        int i = start + 1;
        int j = end - 1;
        while (true) {
            while (i <= j && comp.compare(aList.get(i), pivot) <= 0) {
                i++;
            }
            while (i <= j && comp.compare(aList.get(j), pivot) >= 0) {
                j--;
            }
            if (i <= j) {
                Collections.swap(aList, i, j);
            } else {
                Collections.swap(aList, start, j);
                return j;
            }
        }
    }
}

印刷

gena
timofey
alla
gosha
rita

推荐阅读