来自:
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; }
所以它可以在非升序下工作吗?