来自:
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
和:
http://en.wikipedia.org/wiki/Timsort
我明白了,Timsort 有一些优化 when 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 http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java 中的 TimSort 有一个方法“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;
}
所以它会在非升序下正常工作吗?