专栏首页desperate633深入理解python中的排序

深入理解python中的排序

  • 基本排序 Sorting Basics
  • key函数Key Functions
  • operator库函数自定义排序( Operator Module Functions)
  • 升序和降序Ascending and Descending
  • 排序的稳定性和复杂排序 (Sort Stability and Complex Sorts)
  • 传统的DSU(Decorate-Sort-Undecorate)的排序方法
  • 利用cmp方法进行排序的原始方式
  • 其他

基本排序 Sorting Basics

进行一个简单的升序排列直接调用sorted()函数,函数将会返回一个排序后的列表:

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

sorted函数不会改变原有的list,而是返回一个新的排好序的list

>>> list = [1,3,2,4,5,3,2]
>>> sorted(list)
[1, 2, 2, 3, 3, 4, 5]
>>> list
[1, 3, 2, 4, 5, 3, 2]

如果你想使用就地排序,也就是改变原list的内容,那么可以使用list.sort()的方法,这个方法的返回值是None。

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

另一个区别是,list.sort()方法只是list也就是列表类型的方法,只可以在列表类型上调用。而sorted方法则是可以接受任何可迭代对象。

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

key函数Key Functions

list.sort()和sorted()函数都有一个key参数,可以用来指定一个函数来确定排序的一个优先级。比如,这个例子就是根据大小写的优先级进行排序:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

key参数的值应该是一个函数,这个函数接受一个参数然后返回以一个key,这个key就被用作进行排序。这个方法很高效,因为对于每一个输入的记录只需要调用一次key函数。 一个常用的场景就是当我们需要对一个复杂对象的某些属性进行排序时:

>>> student_tuples = [
... ('john', 'A', 15),
... ('jane', 'B', 12),
... ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

再如:

>>> class Student:
... def __init__(self, name, grade, age):
... self.name = name
... self.grade = grade
... self.age = age
... def __repr__(self):
... return repr((self.name, self.grade, self.age))
>>> student_objects = [
... Student('john', 'A', 15),
... Student('jane', 'B', 12),
... Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

operator库函数自定义排序( Operator Module Functions)

前面我们看到的利用key-function来自定义排序,同时Python也可以通过operator库来自定义排序,而且通常这种方法更好理解并且效率更高。 operator库提供了 itemgetter(), attrgetter(), and a methodcaller()三个函数

>>> from operator import itemgetter, attrgetter
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

同时还支持多层排序

>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

升序和降序Ascending and Descending

list.sort()和sorted()都有一个boolean类型的reverse参数,可以用来指定升序和降序排列,默认为false,也就是升序排序,如果需要降序排列,则需将reverse参数指定为true。

>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

排序的稳定性和复杂排序 (Sort Stability and Complex Sorts)

排序的稳定性指,有相同key值的多个记录进行排序之后,原始的前后关系保持不变

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

我们可以看到python中的排序是稳定的。

我们可以利用这个稳定的特性来进行一些复杂的排序步骤,比如,我们将学生的数据先按成绩降序然后年龄升序。当排序是稳定的时候,我们可以先将年龄升序,再将成绩降序会得到相同的结果。

>>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

传统的DSU(Decorate-Sort-Undecorate)的排序方法

传统的DSU(Decorate-Sort-Undecorate)的排序方法主要有三个步骤:

  • 给list添加一个新的值,这个值一般是用来控制排序的顺序(Decorate)
  • 排序
  • 将添加的值去掉,也就是Undecorate 具体可以看下面的例子:
>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated] # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

因为元组是按字典序比较的,比较完grade之后,会继续比较i。 添加index的i值不是必须的,但是添加i值有以下好处:

  • 可以保证排序的稳定性,如果key值相同,就可以利用i来维持原有的顺序
  • 原始对象的item不用进行比较,因为通过key和i的比较就能将数组排序好

现在python3提供了key-function,所以DSU方法已经不常用了

利用cmp方法进行排序的原始方式

python2.x版本中,是利用cmp参数自定义排序。 python3.x已经将这个方法移除了,但是我们还是有必要了解一下cmp参数 cmp参数的使用方法就是指定一个函数,自定义排序的规则,和java等其他语言很类似

>>> def numeric_compare(x, y):
... return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)
[1, 2, 3, 4, 5]

也可以反序排列

>>> def reverse_numeric(x, y):
... return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric)
[5, 4, 3, 2, 1]

python3.x中可以用如下方式:

def cmp_to_key(mycmp):
'Convert a cmp= function into a key= function'
class K:
def __init__(self, obj, *args):
self.obj = obj
def __lt__(self, other):
return mycmp(self.obj, other.obj) < 0
def __gt__(self, other):
return mycmp(self.obj, other.obj) > 0
def __eq__(self, other):
return mycmp(self.obj, other.obj) == 0
def __le__(self, other):
return mycmp(self.obj, other.obj) <= 0
def __ge__(self, other):
return mycmp(self.obj, other.obj) >= 0
def __ne__(self, other):
return mycmp(self.obj, other.obj) != 0
return K
>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]

其他

  • 可以通过以下方式定义lt函数来指定两个对象比较的方式
>>> Student.__lt__ = lambda self, other: self.age < other.age
>>> sorted(student_objects)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  • 排序的ley-function参数不仅仅可以依赖于排序的对象,也可以依赖于外部的对象. 如下例,成绩姓名分开存储。
>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 五分钟搞懂hashCode()和equals()方法的原理常见的误区错误出现的原因

    这两个方法最开发者来说是十分重要的,必须清楚的理解,但实际上,甚至很多经验丰富的Java开发者有时候也没有真正搞清楚这两个方法的使用和原理。当我们自定义了对象,...

    desperate633
  • LintCode 比较字符串题目分析代码

    比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母

    desperate633
  • 详解排序算法--插入排序和冒泡排序插入排序和冒泡排序分析

    冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把...

    desperate633
  • Python3:复杂数据结构的排序

    排序是非常常见的一个场景,相比于Python2,Python3中的排序有不少优化,今天谈一谈Python3中常见排序场景~~更多细节可参考Ref中的Python...

    企鹅号小编
  • 设计模式之单例模式

    单例模式指的是在应用整个生命周期内只能存在一个实例。单例模式是一种被广泛使用的设计模式。他有很多好处,能够避免实例对象的重复创建,减少创建实例的系统开销,节省内...

    用户1205080
  • 设计模式之单例模式

    会存在并发问题,因为调用newInstance()方法时没有加锁,导致会并发执行,如图:

    tanoak
  • 手动编译Parboil

    这里是使用Parboil自带的脚本编译和使用的教程:https://blog.csdn.net/FishSeeker/article/details/79479...

    用户1148523
  • DDCTF WEB 签到题

    用户5878089
  • 类的生命周期

    一个类从被加载到虚拟机内存开始,到卸载出内存为止,这个生命周期经历了七个阶段:加载、验证、准备、解析、初始化、使用、卸载。

    爱学习的孙小白
  • “互联网+”时代,做自己的品牌吧!

    ---- 在中国当下的舆论话语中,唱衰“中国制造”已经成为很流行的论调。认为传统中低端制造业受人力等成本上涨、东南亚等低成本国家抢夺市场份额、外需疲软等...

    机器人网

扫码关注云+社区

领取腾讯云代金券