python sort().doc

来源：/maverick/archive/2006/07/09/951101.aspx学习笔记：Python的排序Python语言内置了sort方法，可以很方便地对某个List进行排序：L = 6, 5, 1, 3, 4, 2L.sort()print L- Run Python Program -1, 2, 3, 4, 5, 6某些时候，我们希望按照自己定义的排序规则来排序（例如，按关键词的权重排序，按人的年龄排序，等等）。在Java语言中，我们可以自定义Comparator来实现，Python中也提供了类似的办法。若List中每个元素都是2-tuple，tuple中第一个元素为String类型的keyword，第二个元素为该字符串对应的权重（int类型），希望按照权重排序（从高到低），则可以这样：def my_cmp(E1, E2): return -cmp(E11, E21) #compare weight of each 2-tuple #return the negative result of built-in cmp function #thus we get the descend orderL = (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)正因为可以自定义cmp方法，我们不妨探究一下，built-in的sort方法，到底是采用的哪一种排序算法：from random import shuffledef my_cmp(E1, E2): print E1:, E1, E2:, E2 return cmp(E1, E2)L = range(0, 10)shuffle(L)print LL.sort(my_cmp)- Run Python Program -5, 3, 7, 6, 2, 8, 9, 4, 1, 0E1: 3 E2: 5E1: 7 E2: 3E1: 7 E2: 5E1: 6 E2: 5E1: 6 E2: 7E1: 2 E2: 6E1: 2 E2: 5E1: 2 E2: 3E1: 8 E2: 5E1: 8 E2: 7E1: 9 E2: 6E1: 9 E2: 8E1: 4 E2: 6E1: 4 E2: 3E1: 4 E2: 5E1: 1 E2: 6E1: 1 E2: 4E1: 1 E2: 3E1: 1 E2: 2E1: 0 E2: 5E1: 0 E2: 3E1: 0 E2: 2E1: 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, 10L.sort(my_cmp)- Run Python Program -E1: 1 E2: 0E1: 2 E2: 1E1: 3 E2: 2E1: 4 E2: 3E1: 5 E2: 4E1: 6 E2: 5E1: 7 E2: 6E1: 8 E2: 7E1: 9 E2: 8E1: 10 E2: 9结果发现，比较的次数非常少，插入每个元素的时候，只会与它之前紧邻的元素比较，而不是二分检索。这真是个有意思的现象。改一改程序L = 0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10L.sort(my_cmp)- Run Python Program -E1: 1 E2: 0E1: 2 E2: 1E1: 3 E2: 2E1: 4 E2: 3E1: 5 E2: 4E1: 6 E2: 5E1: 8 E2: 6E1: 7 E2: 8E1: 7 E2: 4E1: 7 E2: 6E1: 7 E2: 8E1: 9 E2: 4E1: 9 E2: 7E1: 9 E2: 8E1: 10 E2: 5E1: 10 E2: 8E1: 10 E2: 9可以看到，在数字8以前，List中的元素都是有序的，于是sort算法也只比较欲插入元素和已排序序列的最后一个元素；一旦发现输入序列不是自然有序之后，就采用二分插入排序算法。这样的混合排序算法，相对单纯的插入排序，保证了最好条件下时间代价最低，也减小了一般情况下的时间代价。p.s.写完之后查阅Python的文档，发现sort采用的是混合（hybrid）排序，规模小的时候采用binary insertion，规模大的时候采用samplesort（据说是quicksort的一个变种，我没接触过，汗.）来源：/question/99895220.htmlli = 1, 32, 2, 56, 18li.sort(cmp=None, key=None, reverse=False)uMinNum = li0li.sort(cmp=None, key=None, reverse=True)uMaxNum = li0-li是一个列表,用列表存储这些数据， 然后用列表的排序方法sort()。li.sort(cmp=None, key=None, reverse=False)也可以写成li.sort()， 因为sort()函数的原形就是这样。默认的为是升序排序。li.sort(cmp=None, key=None, reverse=True)修改sort()的reverse变量， 让sort（）进行降序排序。 li0 是取排好序后的第一个元素来源：/blog/user_content.aspx?id=369619Python学习笔记1：排序今天学习Python核心编程（第二版）的排序sort方法，非常感兴趣，特把学习体会写下来：一、Sort基础实现sort可以很方便地对某个List进行排序：L = 6, 5, 1, 3, 4, 2L.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(E11, E21) #compare weight of each 2-tuple#return the negative result of built-in cmp function#thus we get the descend orderL = (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(x1,y1)二、Sort方法的排序算法正因为可以自定义cmp方法，不妨探究一下，built-in的sort方法，到底是采用的哪一种排序算法：from random import shuffledef my_cmp(E1, E2):print E1:, E1, E2:, E2return cmp(E1, E2)L = range(0, 10)shuffle(L)print LL.sort(my_cmp)- Run Python Program -5, 3, 7, 6, 2, 8, 9, 4, 1, 0E1: 3 E2: 5E1: 7 E2: 3E1: 7 E2: 5E1: 6 E2: 5E1: 6 E2: 7E1: 2 E2: 6E1: 2 E2: 5E1: 2 E2: 3E1: 8 E2: 5E1: 8 E2: 7E1: 9 E2: 6E1: 9 E2: 8E1: 4 E2: 6E1: 4 E2: 3E1: 4 E2: 5E1: 1 E2: 6E1: 1 E2: 4E1: 1 E2: 3E1: 1 E2: 2E1: 0 E2: 5E1: 0 E2: 3E1: 0 E2: 2E1: 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, 10L.sort(my_cmp)- Run Python Program -E1: 1 E2: 0E1: 2 E2: 1E1: 3 E2: 2E1: 4 E2: 3E1: 5 E2: 4E1: 6 E2: 5E1: 7 E2: 6E1: 8 E2: 7E1: 9 E2: 8E1: 10 E2: 9结果发现，比较的次数非常少，插入每个元素的时候，只会与它之前紧邻的元素比较，而不是二分检索。这真是个有意思的现象。改一改程序L = 0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10L.sort(my_cmp)- Run Python Program -E1: 1 E2: 0E1: 2 E2: 1E1: 3 E2: 2E1: 4 E2: 3E1: 5 E2: 4E1: 6 E2: 5E1: 8 E2: 6E1: 7 E2: 8E1: 7 E2: 4E1: 7 E2: 6E1: 7 E2: 8E1: 9 E2: 4E1: 9 E2: 7E1: 9 E2: 8E1: 10 E2: 5E1: 10 E2: 8E1: 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 dicline += 1 else: #如果不在，首次出现统计增加新key，统计数初始化为1 dicline = 1fp.close() #读完文件，关闭文件#按value排序，返回是一个元组的列表afterSort = sorted(dic.items(), key=lambda dic: dic1)print afterSort #打印排序后列表，可按照自己需求提取打印结果：data.txt里存有qiangsongwanqiangsongqiang执行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,keenprint samplelist_strsamplelist_str.sort()print samplelist_strprint n# 演示对整型数进行排序samplelist_int = 34,23,2,2333,45print samplelist_intsamplelist_int.sort()print samplelist_intprint n# 演示对字典数据进行排序sampledic