如何使用自定义快速排序实现奥赛选手多条件排序任务

需求描述 #

需自行实现快速排序算法，对奥林匹克竞赛参赛选手按指定规则排序，选手包含三个属性：姓名、解出题目数量、罚时。

排序优先级规则 #

• 优先比较解出题目数：数值越高排名越靠前
• 解出题目数相同的情况下比较罚时：数值越低排名越靠前
• 解题数和罚时均相同的情况下比较姓名：按字典序升序排列

输入输出示例 #

样例输入

5
alla 4 100
gena 6 1000
gosha 2 90
rita 2 90
timofey 4 80

样例输出

gena
timofey
alla
gosha
rita

现有实现缺陷 #

你当前尝试用HashMap存储选手数据，分别对解题数、罚时做单独排序的思路不可行：独立排序两个字段会丢失字段与选手的关联关系，无法实现多维度联动排序，也没法处理姓名维度的比较逻辑。

修正实现方案 #

1. 封装选手对象，将姓名、解题数、罚时三个字段绑定存储，避免排序过程中关联关系丢失
2. 调整快速排序的比较逻辑，不再仅比较单个整数值，改为按排序规则比较两个选手对象的优先级：首先比较解题数降序，相等则比较罚时升序，再相等则比较姓名升序
3. 对存储选手对象的列表直接执行快速排序，排序完成后按顺序输出选手姓名即可

修正后代码示例 #

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

class Participant {
    String name;
    int solved;
    int penalty;

    public Participant(String name, int solved, int penalty) {
        this.name = name;
        this.solved = solved;
        this.penalty = penalty;
    }
}

public class EffectiveQuickSort {
    // 自定义比较逻辑：返回true说明a应该排在b前面
    private static boolean isBetter(Participant a, Participant b) {
        if (a.solved != b.solved) {
            return a.solved > b.solved;
        }
        if (a.penalty != b.penalty) {
            return a.penalty < b.penalty;
        }
        return a.name.compareTo(b.name) < 0;
    }

    public static void quickSort(ArrayList<Participant> 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<Participant> aList, int start, int end) {
        Participant pivot = aList.get(start);
        int i = start + 1;
        int j = end - 1;
        while (true) {
            while (i <= j && isBetter(aList.get(i), pivot)) {
                i++;
            }
            while (i <= j && isBetter(pivot, aList.get(j))) {
                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");
        }
        ArrayList<Participant> participants = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] human = reader.readLine().split(" ");
            participants.add(new Participant(
                    human[0],
                    Integer.parseInt(human[1]),
                    Integer.parseInt(human[2])
            ));
        }
        quickSort(participants, null, null);
        for (Participant p : participants) {
            System.out.println(p.name);
        }
    }
}

内容的提问来源于stack exchange，提问作者Razvie-arr