稳定排序-我们真的需要吗? [英] Stable sort - do we really need it?

问题描述

我不理解试图解决稳定排序算法的潜在问题.

I do not understand the underlying problem that tries to solve the stable sorting algorithm.

Arrays.sort(Object[]) Javadoc状态:

Arrays.sort(Object[]) Javadoc states:

保证这种排序是稳定的:相等的元素将 不会由于排序而重新排序.

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

但是，如果元素相等，则它们不能相互区分！如果交换两个相等的元素，这应该不会有任何影响.这是平等的定义.

But if elements are equal, they are not distringuishable from each other! If you swap two equal elements, this should not affect anything. This is the definition of equality.

那么，为什么我们需要稳定?

So, why do we need stability at all?

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

UPDATE: My question is about Collections.sort(List<T>) / Objects.sort(Object[]) methods, not Collections.sort(List<T>, Comparator<T>), Objects.sort(Comparator<T>). The latter ones are bit different. But there is still no need for stability for them: if you want predictable compound sorts, then you create appropriate compound comparators.

推荐答案

假设您有两列.列名称和列日期.然后，您首先开始按日期对列表进行排序，然后再按名称对它们进行排序.如果排序是稳定的，将会产生的结果是您正确地订购了名称，如果名称相等，则由于日期稳定，因此可以按日期对它们进行排序.但是，如果您的顺序不稳定，则等号之间将没有任何相对顺序.

Let's say you have two columns. Column name and column date. Then you start ordering your list by date first, afterwards you sort them by name. If your sort is stable what it will produce is that you get the name ordered correctly and if the names are equal you get them sorted by date since your order is stable. But if your order is not stable you won't have any relative ordering between the equal keys.

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

这篇关于稳定排序-我们真的需要吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！