Python的内建sort方法

Python语言内置了sort方法&＃xff0c;可以很方便地对某个List进行排序&＃xff1a;
L &＃61; [6, 5, 1, 3, 4, 2]
L.sort()
print L

———- Run Python Program ———-
[1, 2, 3, 4, 5, 6]

某些时候&＃xff0c;我们希望按照自己定义的排序规则来排序&＃xff08;例如&＃xff0c;按关键词的权重排序&＃xff0c;按人的年龄排序&＃xff0c;等等&＃xff09;。在Java语言中&＃xff0c;我们可以自定义Comparator来实现&＃xff0c;Python中也提供了类似的办法。

若List中每个元素都是2-tuple&＃xff0c;tuple中第一个元素为String类型的keyword&＃xff0c;第二个元素为该字符串对应的权重&＃xff08;int类型&＃xff09;&＃xff0c;希望按照权重排序&＃xff08;从高到低&＃xff09;&＃xff0c;则可以这样&＃xff1a;
def my_cmp(E1, E2):
    return -cmp(E1[1], E2[1])    #compare weight of each 2-tuple
                    #return the negative result of built-in cmp function
                    #thus we get the descend order

L &＃61; [(&＃39;a&＃39;, 0), (&＃39;b&＃39;, 1), (&＃39;c&＃39;, 2), (&＃39;d&＃39;, 3)]
L.sort(my_cmp)
print L

———- Run Python Program ———-
[(&＃39;d&＃39;, 3), (&＃39;c&＃39;, 2), (&＃39;b&＃39;, 1), (&＃39;a&＃39;, 0)]

正因为可以自定义cmp方法&＃xff0c;我们不妨探究一下&＃xff0c;built-in的sort方法&＃xff0c;到底是采用的哪一种排序算法&＃xff1a;
from random import shuffle

def my_cmp(E1, E2):
    print ‘E1:’, E1, ‘E2:’, E2
    return cmp(E1, E2)

L &＃61; range(0, 10)
shuffle(L)
print L
L.sort(my_cmp)

———- Run Python Program ———-
[5, 3, 7, 6, 2, 8, 9, 4, 1, 0]
E1: 3 E2: 5
E1: 7 E2: 3
E1: 7 E2: 5
E1: 6 E2: 5
E1: 6 E2: 7
E1: 2 E2: 6
E1: 2 E2: 5
E1: 2 E2: 3
E1: 8 E2: 5
E1: 8 E2: 7
E1: 9 E2: 6
E1: 9 E2: 8
E1: 4 E2: 6
E1: 4 E2: 3
E1: 4 E2: 5
E1: 1 E2: 6
E1: 1 E2: 4
E1: 1 E2: 3
E1: 1 E2: 2
E1: 0 E2: 5
E1: 0 E2: 3
E1: 0 E2: 2
E1: 0 E2: 1

可以看到&＃xff0c;每次调用my_cmp&＃xff0c;E1依次是List中的第2、3、4……直到最后一个元素&＃xff0c;可以肯定sort不是采用的分治法&＃xff08;devide-and-conqure&＃xff09;
看前三次调用&＃xff0c;可以发现sort采用的是典型的插入排序——也就是说&＃xff0c;将新元素插入已排序部分的合适位置&＃xff0c;查找位置时采用的似乎是从后向前线形探察的办法。从元素6开始&＃xff0c;新元素不再直接与已排序部分的最后元素比较&＃xff0c;而是先与中间值比较&＃xff0c;采用二分检索探察合适位置&＃xff0c;这样&＃xff0c;可以把时间代价从n缩小到log(n)。
至此&＃xff0c;我们可以认为&＃xff0c;built-in的sort方法&＃xff0c;采用的是“二分法插入排序”&＃xff08;binary insertion&＃xff09;的算法。

为了检测这个结论&＃xff0c;可以输入一个已排序的数组&＃xff0c;看看结果。
L &＃61; [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
L.sort(my_cmp)

———- Run Python Program ———-
E1: 1 E2: 0
E1: 2 E2: 1
E1: 3 E2: 2
E1: 4 E2: 3
E1: 5 E2: 4
E1: 6 E2: 5
E1: 7 E2: 6
E1: 8 E2: 7
E1: 9 E2: 8
E1: 10 E2: 9

结果发现&＃xff0c;比较的次数非常少&＃xff0c;插入每个元素的时候&＃xff0c;只会与它之前紧邻的元素比较&＃xff0c;而不是二分检索。这真是个有意思的现象。

改一改程序
L &＃61; [0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10]
L.sort(my_cmp)

———- Run Python Program ———-
E1: 1 E2: 0
E1: 2 E2: 1
E1: 3 E2: 2
E1: 4 E2: 3
E1: 5 E2: 4
E1: 6 E2: 5
E1: 8 E2: 6
E1: 7 E2: 8
E1: 7 E2: 4
E1: 7 E2: 6
E1: 7 E2: 8
E1: 9 E2: 4
E1: 9 E2: 7
E1: 9 E2: 8
E1: 10 E2: 5
E1: 10 E2: 8
E1: 10 E2: 9

可以看到&＃xff0c;在数字8以前&＃xff0c;List中的元素都是有序的&＃xff0c;于是sort算法也只比较欲插入元素和已排序序列的最后一个元素&＃xff1b;一旦发现输入序列不是自然有序之后&＃xff0c;就采用二分插入排序算法。
这样的混合排序算法&＃xff0c;相对单纯的插入排序&＃xff0c;保证了最好条件下时间代价最低&＃xff0c;也减小了一般情况下的时间代价。

p.s.
写完之后查阅Python的文档&＃xff0c;发现sort采用的是混合&＃xff08;hybrid&＃xff09;排序&＃xff0c;规模小的时候采用binary insertion&＃xff0c;规模大的时候采用samplesort&＃xff08;据说是quicksort的一个变种&＃xff0c;我没接触过&＃xff0c;汗….&＃xff09;

转载自&＃xff1a;http://blog.donews.com/maverick/archive/2006/07/09/951101.aspx