是否可以修改compareTo()方法以确保插入排序和选择排序无论如何返回相同的输出？ [已关闭]

Question

所以我实现了这个 PlayingCard 类：

public class PlayingCard {
    public String suit;
    public int rank;

public PlayingCard(String suit, int rank) {
    this.suit = suit;
    this.rank = rank;
}

public int compareTo(PlayingCard other) {
    return suit.compareTo(other.suit);
}

}

我应该修改compareTo方法，以便选择排序和插入排序始终返回相同的输出（选择和插入排序方法的输入是这些PlayingCard对象的列表）。但是，如果这是不可能的，我需要解释原因。我知道插入排序是稳定的，而选择排序则不稳定，这就是它们主要的根本区别所在。可能吗？如何？

Answer 1

是的，可以使用不同的或修改的

compareTo

。

---

如您所知，不稳定排序是指相等（根据排序函数）的元素顺序从未排序的输入序列更改为排序的输出序列。

一般来说，解决这个问题¹的最佳方法²是安排输入序列中没有元素相等：

• 使用所有可能元素的域的total排序函数，或者
• 对输入序列中实际存在的所有元素使用total的排序函数。

在您的具体情况下，问题是

compareTo

给出的顺序只是部分顺序。它没有考虑

rank

；即，它将所有具有相同花色的牌视为平等。解决办法有很多种：

• 显而易见的解决方案是考虑

  rank

  。 （但是，如果您玩的 Canasta 游戏涉及两副洗牌的游戏，该怎么办？）

• 另一种解决方案是为每张卡添加一个唯一的 id 字段，并将其用作“抽奖断路器”。

• 第三种解决方案是完全根据唯一 ID 进行排序。根据您生成唯一 ID 的方式，结果可能是稳定的，但从玩家的角度来看完全不可预测。

• 最终的解决方案是将输入列表中的位置记录在单独的数据结构中（例如

  HashMap<PlayingCard, Integer>

  ），并使用该值作为“抽签断路器”。

请注意，在某些情况下，上述每项都会导致不同的排序。

---

^{1 - 替代方案至少更复杂。
2 - 也就是说，使不稳定排序表现得像稳定排序的问题。}