python的排序详解

    python对list有一个内置函数：sorted(),专门用于排序。举例：

    也可以使用list.sort()来进行上述操作。

    2. >>> a               #注意这里，经过list.sort()之后，原有
    3. [1, 2, 3, 5, 6, 9]  #a的顺序已经发生变化，与上述不同之处。

    sorted和list.sort()的区别:list.sort()只能对list类型进行排序。如下：

    1. >>> b_dict={1:'e',3:'m',9:'a',5:'e'}
    2. >>> b_dict.sort()
    3. Traceback (most recent call last):
    4.   File "<stdin>", line 1, in <module>
    5.   AttributeError: 'dict' object has no attribute 'sort'

    而sorted则不然，看例子：

    sorted之后，上述对dictinoary中，将key值取出并排序，返回list类型的排序结果。

    按照指定关键词排序

    在list.sort()和sorted中，都可以根据指定的key值排序。例如：

    1. >>> qw="I am Qiwsir you can read my articles im my blog".split()
    2. >>> qw
    3. ['I', 'am', 'Qiwsir', 'you', 'can', 'read', 'my', 'articles', 'im', 'my', 'blog']
    4. >>> sorted(qw,key=str.lower)        #按照字母升序排列
    5. ['am', 'articles', 'blog', 'can', 'I', 'im', 'my', 'my', 'Qiwsir', 'read', 'you']

    list.sort()的例子：

    1. ['I', 'am', 'Qiwsir', 'you', 'can', 'read', 'my', 'articles', 'im', 'my', 'blog']
    2. >>> qw.sort(key=str.lower)
    4. ['am', 'articles', 'blog', 'can', 'I', 'im', 'my', 'my', 'Qiwsir', 'read', 'you']

    此外，key还可以接收函数的单一返回值，按照该值排序。例如：

    除了上述方式，python中还提供了一个选择循环选择指定元组值的模块

    1. >>> from operator import itemgetter    #官方文档：https://docs.python.org/2/library/operator.html#module-operator
    2. >>> name_mark_age.append(('zhaoliu','B',16))
    3. >>> name_mark_age
    4. [('zhangsan', 'A', 15), ('LISI', 'B', 14), ('WANGWU', 'A', 16), ('zhaoliu', 'B', 16)]
    6. >>> sorted(name_mark_age,key=itemgetter(2))     #按照年龄排序
    7. [('LISI', 'B', 14), ('zhangsan', 'A', 15), ('WANGWU', 'A', 16), ('zhaoliu', 'B', 16)]
    9. >>> sorted(name_mark_age,key=itemgetter(1,2))   #先按照等级排序，相同等级看年龄
    10. [('zhangsan', 'A', 15), ('WANGWU', 'A', 16), ('LISI', 'B', 14), ('zhaoliu', 'B', 16)]

    在官方文档上，有这样一个例子，和上面的操作是完全一样的。

    1. >>> class Student:
    2.         def __init__(self, name, grade, age):
    3.             self.name = name
    6.         def __repr__(self):
    7.             return repr((self.name, self.grade, self.age))
    9. >>> student_objects = [
    10.         Student('john', 'A', 15),       #注意这里，用class Student来生成列表内的值
    11.         Student('jane', 'B', 12),       #因此，可以通过student_objects[i].age来访问某个名称的年龄,i=0,则是john的年龄
    12.         Student('dave', 'B', 10),
    13.         ]
    15. >>> sorted(student_objects, key=lambda student: student.age)
    16. [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

    也可以引用operator模块来实现上述排序

    总结：sorted的能力超强，不仅实现排序，还能按照指定关键词排序。

    1. >>>from operator import itemgetter 
    2. >>> name_mark_age
    3. [('zhangsan', 'A', 15), ('LISI', 'B', 14), ('WANGWU', 'A', 16), ('zhaoliu', 'B', 16)]

    sorted的算法

    python中的sorted算法，网上有人撰文，说比较低级。其实不然，通过阅读官方文档，发现python中的sorted排序，真的是高大上，用的Timsort算法。什么是Timsort，请看 wiki的解释：

    从时间复杂度来看，Timsort是威武的。

    从空间复杂度来讲，需要的开销在数量大的时候会增大。

    排序之python sorted性能分析 - 图1

    综上，可以看出，就一般情况，使用sorted足以能够完成排序的要求，并且是稳定的。

    本文作者在博客和github上都有多种关于python排序方法和模块的文章说明。