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

Question

我不明白试图解决稳定排序算法的根本问题.

Arrays.sort(Object[]) Javadoc说:

这种类型保证是稳定的:相同的元素不会因排序而重新排序.

但如果元素是平等的,它们就不会彼此分裂!如果你交换两个相等的元素,这不应该影响任何东西.这是平等的定义.

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

更新:我的问题是关于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;
       }
 }

Answer 2

不稳定的排序可能会影响 UI。想象一下您正在 Windows 中使用文件资源管理器，其中包含歌曲的详细信息视图。您能想象如果您一直单击文件类型列来按文件类型排序，并且每次您单击它时它都会随机重新排序每个类型组中的所有内容吗？

UI 中的稳定排序允许我（用户）创建自己的复合排序。我可以将多种排序链接在一起，例如“按名称排序”，然后“按艺术家排序”，然后“按类型排序”。最终结果的排序优先考虑类型，然后是艺术家，最后是按名称。这是因为稳定排序实际上保留了以前的排序，允许我从一系列基本排序“构建”自己的排序！而不稳定排序会破坏先前排序类型的结果。

当然，在代码中，您只需进行一个大的、完全定义的排序，然后排序并排序一次，而不是像我上面描述的那样进行链式“复合”排序。这就是为什么大多数应用程序内部排序不需要稳定排序的原因。但当用户驱动点击时，稳定的排序是最好/最简单的。

编辑：“我的问题是关于Collections.sort(List<T>)/Objects.sort(Object[])方法”

这些是通用类型，适用于定义Comparable. Comparable即使对象在技术上不“相等”，您的类的实现也可能返回 0，因为您可能正在尝试特定的顺序。换句话说，这些方法与Collections.sort(List<T>, Comparator<T>). 您可能需要稳定排序，也可能不需要。