java—是否可以修改compareto()方法以确保插入排序和选择排序返回相同的输出?

lh80um4z  于 2021-06-30  发布在  Java
关注(0)|答案(1)|浏览(380)

关闭。这个问题需要细节或清晰。它目前不接受答案。
**想改进这个问题吗?**通过编辑这个帖子来添加细节并澄清问题。

27天前关门了。
改进这个问题
具体问题
所以我实现了这个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对象的列表)。然而,如果这是不可能的,我需要解释为什么。我知道插入排序是稳定的,而选择排序不是,这就是它们主要的根本区别所在。可能吗?怎么可能?

rnmwe5a2

rnmwe5a21#

是的,可以使用不同的或修改过的 compareTo .
如您所知,不稳定排序是指相等元素的顺序(根据排序函数)从未排序的输入序列更改为排序的输出序列。
一般来说,解决这个问题的最佳方法1是安排输入序列中的元素不相等:
使用所有可能元素的域的总排序函数,或
使用对输入序列中实际存在的所有元素求和的排序函数。
在您的具体案例中,问题在于 compareTo 只是部分订单。它没有考虑到 rank ; i、 它将所有具有相同套装的牌视为同等对待。有许多解决方案:
显而易见的解决办法是考虑到 rank . (但是如果你玩的是卡纳斯塔牌,其中包括两副牌一起洗牌呢?)
另一个解决方案是为每张卡添加一个唯一的id字段,并将其用作“抽签开关”。
第三种解决方案是完全基于唯一id进行排序。根据生成唯一id的方式,结果可能是稳定的,但从玩家的Angular 来看完全不可预测的排序。
最终的解决方案是将输入列表中的位置记录在一个单独的数据结构中(例如 HashMap<PlayingCard, Integer> ),并将该值用作“draw breaker”。
请注意,以上每一项都会导致不同的排序。。。在某些情况下。
1-备选方案至少更复杂。
2-也就是说,使不稳定排序的行为类似于稳定排序的问题。

相关问题