Python的sort用法以及原理

Python的sort用法以及原理

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

1. 基本用法

1.1 列表

1
2
3
4
5
6
x = [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
4
x = (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
3
x = {"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函数

1
print(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
6
student_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
16
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))
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
6
student = [
('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
29
from operator import itemgetter, attrgetter, methodcaller

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