java - 稳定排序——我们真的需要它吗？

Question

我不明白试图解决稳定排序算法的潜在问题。
Arrays.sort(Object[]) Javadoc 指出:

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

但是如果元素相等，它们就不能相互区分!如果交换两个相等的元素，这应该不会影响任何事情。这就是平等的定义。

那么，我们为什么需要稳定性呢？

更新:我的问题是关于 Collections.sort(List<T>)/ Objects.sort(Object[])方法，而不是 Collections.sort(List<T>, Comparator<T>) , Objects.sort(Comparator<T>) .后者有点不同。但是它们仍然不需要稳定性:如果您想要可预测的复合排序，那么您可以创建适当的复合比较器。

Answer 1

假设您有两列。列名称和列日期。然后你开始先按日期排序你的列表，然后按名称排序。如果您的排序是稳定的，那么它将产生的结果是您得到的名称排序正确，如果名称相同，则由于您的订单稳定，您将按日期对它们进行排序。但是，如果您的订单不稳定，则相等键之间将不会有任何相对顺序。

public static void main (String[] args) 
{
    // your code goes here
    List<FirstNameLastName> list = new ArrayList<FirstNameLastName> ();
    list.add(new("A","B"));
    list.add(new("D","B"));
    list.add(new("F","B"));
    list.add(new("C","C"));
    list.add(new("E","C"));
    list.add(new("B","C"));

    Arrays.sort(list,new Comparator(firstName)); //FIXME
    // A-B , B-C , C-C , D-B , E-C  , F-B
    Arrays.sort(list,new Comparator(lastName)); //FIXME
    // A-B , D-B F-B,B-C,C-C,E-C
    //So as you see here inside the last name B and C each first name 
    //is sorted also

    //However if you just sorted instead directly on last name only
    //A-B , D-B -F,B-C-C,E-C,B-C
}

private class FirstNameLastName {
      String firstName;
      Stirng lastName;
      public FirstNameLastName(String firstName,String lastName) {
          this.firstName = firstName;
          this.lastName = lastName;
       }
 }