时间戳

首页 > 解决方案 > Is it possible to modify a compareTo() method so as to ensure that Insertion sort and Selection sort return the same output no matter what?

java - Is it possible to modify a compareTo() method so as to ensure that Insertion sort and Selection sort return the same output no matter what?

问题描述

Specific Problem

So I implemented this PlayingCard class:

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);
}

}

and I'm supposed to modify the compareTo method so that Selection Sort and Insertion Sort always return the same output no matter what (with the input to the selection and insertion sort methods being a list of these PlayingCard objects). However, if this isn't possible, I need to explain why. I know that insertion sort is stable and selection sort isn't, and that's where their major underlying difference lies. Is it possible, and how?

标签： javaalgorithmsortingoopdata-structures

解决方案

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

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

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

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

在您的具体情况下，问题是给出的顺序compareTo只是部分顺序。它不考虑rank; 即它将所有具有相同花色的牌视为平等。有多种解决方案：

  • 显而易见的解决方案是考虑rank. （但是如果你玩的是两副牌一起洗牌的卡纳斯塔呢？）

  • 另一种解决方案是为每张卡添加一个唯一的 id 字段并将其用作“平局破坏者”。

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

  • 最终解决方案是将输入列表中的位置记录在单独的数据结构（例如 a HashMap<PlayingCard, Integer>）中，并将该值用作“绘图断路器”。

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

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

推荐阅读