今天学习《Python核心编程（第二版）》的排序sort方法，非常感兴趣，特把学习体会写下来：

一、Sort基础实现

sort可以很方便地对某个List进行排序：

L = [6, 5, 1, 3, 4, 2]
L.sort()
print L

 

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

某些时候，我们希望按照自己定义的排序规则来排序（例如，按关键词的权重排序，按人的年龄排序，等等）。

若List中每个元素都是2-tuple，tuple中第一个元素为String类型的keyword，第二个元素为该字符串对应的权重（int类型），希望按照权重排序（从高到低），则可以这样：
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 = [('a', 0), ('b', 1), ('c', 2), ('d', 3)]
L.sort(my_cmp)
print L

---------- Run Python Program ----------
[('d', 3), ('c', 2), ('b', 1), ('a', 0)]

PS：可以简化一点：无需定义对象，直接用L.sort(cmp=lambda x,y :cmp(x[1],y[1]))

二、Sort方法的排序算法

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

def my_cmp(E1, E2):
print 'E1:', E1, 'E2:', E2
return cmp(E1, E2)

L = 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

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

为了检测这个结论，可以输入一个已排序的数组，看看结果。
L = [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

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

改一改程序
L = [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

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

p.s.
写完之后查阅Python的文档，发现sort采用的是混合（hybrid）排序，规模小的时候采用binary insertion，规模大的时候采用samplesort（据说是quicksort的一个变种）

三、Sort方法简单应用

情景：有一个文件，里面一行记录一条字符串，比如有数百行，当然有重复的，然后按独立字符串出现的次数排序，print输出.

思路：字典类型的典型用法，使用字典类型来统计出现次数，字符串作为key，出现次数作为value。

#!/usr/bin/python
# -*- coding: utf-8 -*-

dic = {} #定义一个字典类型
fp = open('c://data.txt') #打开要查询的文件
for line in fp: #从fp中读取行，利用这种方法可以避免有空行截断读取
    line = line.strip()#去掉前后导空白
    if('' == line):
        continue #去掉前后导空白如果是空行不作处理
    if(line in dic): #判断s是否在字典内，如果在统计加1
        dic[line] += 1
    else: #如果不在，首次出现统计增加新key，统计数初始化为1
        dic[line] = 1

fp.close() #读完文件，关闭文件

#按value排序，返回是一个元组的列表
afterSort = sorted(dic.items(), key=lambda dic: dic[1])
print afterSort #打印排序后列表，可按照自己需求提取打印

结果：
data.txt里存有
qiang
song
wan
qiang
song
qiang
执行python后打印出：
[('wan', 1), ('song', 2), ('qiang', 3)]

四、对不同对象的排序演示汇总

# sort.py    
# 这个类用来演示如何对自定义对象进行排序    
class Sortobj:
    a = 0
    b = ''
    def __init__(self, a, b):
        self.a = a
        self.b = b
    def printab(self):
        print self.a, self.b    
    
# 演示对字符串列表进行排序    
samplelist_str = ['blue','allen','sophia','keen']    
print samplelist_str    
samplelist_str.sort()    
print samplelist_str    
    
print 'n'    
   
# 演示对整型数进行排序    
samplelist_int = [34,23,2,2333,45]    
print samplelist_int    
samplelist_int.sort()    
print samplelist_int    
    
print 'n'    
     
# 演示对字典数据进行排序    
sampledict_str = {'blue':'5555@sina.com',    
                  'allen':'222@163.com',    
                  'sophia':'4444@gmail.com',    
                  'ceen':'blue@263.net'}    
print sampledict_str    

# 按照key进行排序    
print sorted(sampledict_str.items(), key=lambda d: d[0])    

# 按照value进行排序    
print sorted(sampledict_str.items(), key=lambda d: d[1])    
    
# 构建用于排序的类实例    
obja = Sortobj(343, 'keen')    
objb = Sortobj(56, 'blue')    
objc = Sortobj(2, 'aba')    
objd = Sortobj(89, 'iiii')    
   
print 'n'    
   
samplelist_obj = [obja, objb, objc, objd]    
# 实例对象排序前    
for obj in samplelist_obj:
    obj.printab()
    print 'n'    

# 按照对象的a属性进行排序    
samplelist_obj.sort(lambda x,y: cmp(x.a, y.a))    
for obj in samplelist_obj:
    obj.printab()
    print 'n'    

# 按照对象的b属性进行排序    
samplelist_obj.sort(lambda x,y: cmp(x.b, y.b))    
for obj in samplelist_obj:
    obj.printab()

 

转载本文请联系原作者获取授权，同时请注明本文来自胡海华科学网博客。
链接地址：https://blog.sciencenet.cn/blog-243747-369619.html

上一篇：开博第一篇
下一篇：Range和XRange的区别