python sort怎么用_Python的sort用法以及原理

在python中如果要对list, tuple, dict进行排序，一般会用到sort函数

1. 基本用法

1.1 列表1

2

3

4

5

6x = [4, 6, 2, 3]

y = x.sort()

z = sorted(x)

print(x)

print(y)

print(z)

output:

1

2

3[2,3,4,6]

None

[2,3,4,6]

sort和sorted的原理类似，区别在于sort()是直接对原对象进行排序，没有返回值；而sorted()是新建一个对原对象排序后的新对象，返回新对象1.2 元组

1.2 元组1

2

3

4x = (2, 5, 3, 4)

z = sorted(x)

print(x)

print(z)

output:

1

2(2, 5, 3, 4)

[2, 3, 4, 5]

tuple没有sort()函数，另外值得注意的是，返回的是list，而非tuple

1.3 字典1

2

3x = {"a":2, "c":5, "e":3, "b":4}

z = sorted(x)

print(z)

output:

1['a', 'b', 'c', 'e']

dict没有sort()函数，默认情况下是对字典的键进行排序，并返回排序后的键列表

2. 进阶用法

2.1 key函数1print(sorted("This is a test string from Andrew".split(), key=str.lower))

output:

1['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

key可以接受一个函数，用于指定排序方法

2.2 lambda函数1

2

3

4

5

6student_tuples = [

('john', 'A', 15),

('jane', 'B', 12),

('dave', 'B', 10),

]

print(sorted(student_tuples, key=lambda student: student[2]))

output:

1[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

通过第三个元素进行排序

2.3 类方法1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16class :

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))

def weighted_grade(self):

return 'CBA'.index(self.grade) / float(self.age)

student_objects = [

Student('john', 'A', 15),

Student('jane', 'B', 12),

Student('dave', 'B', 10),

]

print(sorted(student_objects, key=lambda student: student.age))

output:

1[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

通过类方法指定key参数

2.4 正序或反序1

2

3

4

5

6student = [

('john', 'A', 15),

('jane', 'B', 12),

('dave', 'B', 10),

]

print(sorted(student, key=lambda x:x[2], reverse=True))

output:

1[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

指定reverse的参数为True则进行反序排列，设为False或者不设则默认为正序排列

3 Operator模组1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29from operator import itemgetter, attrgetter, methodcaller

class :

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))

def weighted_grade(self):

return 'CBA'.index(self.grade) / float(self.age)

student_objects = [

Student('john', 'A', 15),

Student('jane', 'B', 12),

Student('dave', 'B', 10),

]

student_tuples = [

('john', 'A', 15),

('jane', 'B', 12),

('dave', 'B', 10),

]

print(sorted(student_tuples, key=itemgetter(2)))

print(sorted(student_objects, key=attrgetter('age')))

print(sorted(student_tuples, key=itemgetter(1,2)))

print(sorted(student_objects, key=attrgetter('grade', 'age')))

print(sorted(student_objects, key=methodcaller('weighted_grade')))

output:

1

2

3

4

5[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

[('jane', 'B', 12), ('dave', 'B', 10), ('john', 'A', 15)]

在Operator模组中，有itemgetter, attrgetter以及methodecaller方法

4 sorted()原理

python中的sort()方法使用的是快排。

快速排序分治法思想的一种实现，它的思路是使数组中的每个元素与基准值(Pivot，通常是数组的首个值，A[0])比较，数组中比基准值小的放在基准值的左边，形成左部；大的放在右边，形成右部；接下来将左部和右部分别递归地执行上面的过程：选基准值，小的放在左边，大的放在右边…直到排序结束。

4.1 步骤：找基准值，设Pivot = a[0]

分区(Partition)：比基准值小的放左边，大的放右边，基准值(Pivot)放左部与右部的之间。

进行左部(a[0] - a[pivot-1])的递归，以及右部(a[pivot+1] - a[n-1])的递归，重复上述步骤。

4.2 快排源码：1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20class quick_sort(object):

def _partition(self, alist, p, r):

i = p-1

x = alist[r]

for j in range(p, r):

if alist[j] <= x:

i += 1

alist[i], alist[j] = alist[j], alist[i]

alist[i+1], alist[r] = alist[r], alist[i+1]

return i+1

def _quicksort(self, alist, p, r):

if p < r:

q = self._partition(alist, p, r)

self._quicksort(alist, p, q-1)

self._quicksort(alist, q+1, r)

def __call__(self, sort_list):

self._quicksort(sort_list, 0, len(sort_list)-1)

return sort_list