sorting - Timsort如何按降序对数据执行？

来自:

http://svn.python.org/projects/python/trunk/Objects/listsort.txt

和:

http://en.wikipedia.org/wiki/Timsort

我看到，Timsort在a0 > a1 > a2 > ...时有一些优化，但是下一个数组呢？
10000,10000,9999,9999,9998,9998,....,9,9,8,8,7,7,6,6,5,5,4,4,3,3,2,2,1,1,0,0
这种阵列的时间效率是多少？

(使用整数来简化示例，需要稳定的排序)
我进行了一些测量，看来，这种阵列对于Timsort而言不是“好”情况。

实际上，JDK中的TimSort就是http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java
有一个方法“countRunAndMakeAscending”

@SuppressWarnings("unchecked")
private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
    assert lo < hi;
    int runHi = lo + 1;
    if (runHi == hi)
        return 1;

    // Find end of run, and reverse range if descending
    if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
        while(runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
            runHi++;
        reverseRange(a, lo, runHi);
    } else {                              // Ascending
        while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
            runHi++;
    }

    return runHi - lo;
}

为什么不以另一种方式实现它:

private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
    int runHi = lo;
    int lastEqual = lo;
    int ascending = 0;
    while (++runHi < hi) {
      int c = ((Comparable) a[runHi+1]).compareTo(a[runHi]);
      if (ascending == 0) {
        if (c != 0) {
          if (c > 0) {
            ascending = 1;
          } else {
            ascending = -1;
            reverseRange(a, lastEqual, runHi);
            lastEqual = runHi;
          }
        }
      } else if (ascending == 1) {
        if (c < 0) {
          return runHi - lo;
        }
      } else {
        if (c > 0) {
          reverseRange(a, lastEqual, runHi);
          reverseRange(a, lo, runHi);
          return runHi - lo;
        } else if (c < 0) {
          reverseRange(a, lastEqual, runHi);
          lastEqual = runHi;
        }
      }
    }
    if (ascending == -1) {
      reverseRange(a, lastEqual, runHi);
      reverseRange(a, lo, runHi);
    }
    return runHi - lo;
}

所以它可以在不升序的情况下正常工作？

最佳答案

是的。

基本上，它决定“升序”实际上是“不降序”，而又不失一般性-如果您有[5,5,4 3]，它将变成[5,5](升序)，然后[4,3](降序)在下一个电话上。

至于原因，我想这很简单:只需尝试计算代码和原始代码中reverseRange()的调用次数，您就会明白(我注意到了花了多长时间才能理解一个版本与另一个 :)

编辑:错错错!正如奥斯卡·史密斯(Oscar Smith)指出的，原因是使timsort成为稳定的排序算法。
如果有人知道如何转移不当的赏金...

关于sorting - Timsort如何按降序对数据执行？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20311706/