17 选择排序

排序就是按高矮顺序站好队

大纲

• 选择排序

• 对嵌套列表的排序

• 使用内置的排序函数

选择排序

排序是很常见的一种操作，给你一组数字，你需要把它从小到大排队排好。虽然python中有内置的函数可以用来排序，不过从练习编程和思维的角度讲，我们自己写一个排序的函数会更好。

一种简单的排序思路就是利用循环的思路，先找出所有数字中最小的那个，再找出剩余数字中最小的那个，以此类推。

先回顾一下循环的时候，我们通常是遍历一个列表中的值

x = [10,20,30]
for value in x:
    print(value)

10
20
30

如果还需要遍历值对应的位置编号，可以像下面这样处理,这里enumerate函数的功能在于循环的时候，同时输出对应的位置编号和值，可以用来遍历值，也可以同时遍历位置。

x = [10,20,30]
for index,value in enumerate(x):
    print(index,value)

0 10
1 20
2 30

下面的函数是用来实现找到一组数字中最小数字的功能，输入是一个列表，输出列表中最小数字的值，以及对应的位置。

def find_smallest(x):
    smallest = x[0]
    smallest_index = 0
    for index,value in enumerate(x):
        if smallest>value:
            smallest = value
            smallest_index = index
    return smallest,smallest_index

find_smallest([14,6,7,4,9,30])

(4, 3)

可以用这个find_smallest找到最小值是4，而且知道这个4对应的位置编号是3，因为python的编号索引是从0开始的。

然后我们来实现排序的函数，整体思路是我们先准备一个空列表sorted_list，将需要排序的列表X中最小的找出来，放入sorted_list，同时从X中删除这个最小值。pop这个函数是个有趣的功能，它在删除操作的同时，会返回这个被删除的值，正好用append补充到sorted_list最后。

def sort_list(x):
    sorted_list = [] # 用于存放排序好的列表
    for i in range(len(x)):  # 遍历次数是列表的长度
        smallest,samllest_index = find_smallest(x) # 找到最小值和编号
        sorted_list.append(x.pop(samllest_index)) # 将最小值从X中删除并补充到sorted_list中
    return sorted_list

sort_list([14,6,7,4,9,30])

[4, 6, 7, 9, 14, 30]

对嵌套列表的排序

对于一个只有数字的列表用这种排序很容易完成了，如果是象课程分数这种嵌套的列表，想按分数来排序，应该如何做呢，我们只需要将find_smallest函数改造一下就可以了，改造的时候只需要修改几个地方。

def find_smallest(x):
    smallest = x[0][1]
    smallest_index = 0
    for index,value in enumerate(x):
        if smallest>value[1]:
            smallest = value[1]
            smallest_index = index
    return smallest,smallest_index

course = [['语文',85],['数学',90],['英语',94],['历史',87],['体育',85],['音乐',98]]

sort_list(course)

[['语文', 85], ['体育', 85], ['历史', 87], ['数学', 90], ['英语', 94], ['音乐', 98]]

使用内置的排序函数

现在我们是自己实现了一个列表排序的函数，当然在现实中，我们没有必要自己造轮子，可以直接使用现有的内置函数sorted

num_list = [14,6,7,4,9,30]

sorted(num_list)

[4, 6, 7, 9, 14, 30]

sorted函数默认是从小到大排序，如果是从大到小排序，可以加一个参数reverse

sorted(num_list,reverse=True)

[30, 14, 9, 7, 6, 4]

对于嵌套列表这种数据，要对它排序会略有不一样，因为每一个元素都有两个信息可以用来排序，一个是字符串，另一个是数值，那么需要指定我们按哪一个信息来排序，这里可以使用一个lambda匿名函数来，匿名函数是将函数定义用一行代码完成，适合于非常简单的函数。例如

course = [['语文',85],['数学',90],['英语',94],['历史',87],['体育',85],['音乐',98]]

f = lambda x:x[1]
f(course[0])

85

这里定义了一个函数表示取出一个列表中的第2项元素，非常简单的逻辑，用在course的第一门课上，就会取出语文对应的分数85.

在使用sorted对嵌套列表这种数据进行排序时，需要用key参数指定按哪一个信息来排序，就使用lambda匿名函数，意思就是按分数来排序，结果如下。

sorted(course,key=lambda x:x[1])

[['语文', 85], ['体育', 85], ['历史', 87], ['数学', 90], ['英语', 94], ['音乐', 98]]

小结：一种简单的排序思路是用循环，每次循环是找到当前列表中最小的值，这种方法称为选择排序。我们通过自己写代码实现了选择排序，理解了选择排序的思路。不过真正用的时候只需要使用内置的sorted函数就可以了。