1.sorted()函数与选择排序

在开始之间，我们首先来看看在Python当中有一个已经定义好的排序函数，sorted()函数，使用方法也非常简单，我们只需要在括号当中传递列表名称即可

a=[34,56,1,2,3,8,54]
b=sorted(a)    #返回一个新的已经排序好的列表
print(b)

#运行结果
#[1, 2, 3, 8, 34, 54, 56]

其实就算不用sorded()，我们也有一些其他的方式来进行排序，比如，使用下面的方式进行

a=[34,56,1,2,3,8,54]
b=[]    #建立一个空列表，用于存储已经排序好的数据

for i in range(len(a)):        #a有多长，就循环多少次
    min1=min(a)                #获取现在a当中的最小值
    a.pop(a.index(min1))    #弹出a当中的最小值
    b.append(min1)            #将最小值放到a当中
print(b)

#result
#[1, 2, 3, 8, 34, 54, 56]

以上所使用的方法非常简单，无非就是每次将a当中列表拿出来，并且放在b当中就好了，最后输出的结果，肯定是一个有序的结果。

当然，我们本节课是学习选择排序算法，因此，我们不单单要学会如何使用sorted()函数，还必须要了解这个函数的内部是如何运行的，那么对于选择排序算法来说，是怎样的一个运行过程呢？

假设，我们现在有这样的一个列表：[6,5,1,3,4]，那么选择排序算法会如何进行从小到大排序呢？

1.选择整个列表中选择一个最小的数：1，并将它放在最前面的位置，结果：[1,6,5,3,4]

2.由于1已经固定，因此从后面四个数中选择一个最小的数：3，将它放在1的后面，结果：[1,3,6,5,4]

3.由于1,3已经固定，因此从后面三个数中选择一个最小的数：4，将它放在3的后面，结果：[1,3,4,6,5]

4.由于1,3,4已经固定，因此从后面二个数中选择一个最小的数：4，将它放在4的后面，结果：[1,3,4,5,6]

5.由于1,3,4,5已经固定，因此从后面一个数中选择一个最小的数：6，将它放在5的后面，结果：[1,3,4,5,6]

在经过5次运算之后，我们成功的获得了正确的结果，在这个过程当中，总共选择了5次，刚好等于列表的长度。

由于每次都是选择列表当中的最小值/最大值，因此这个算法就叫做选择排序算法

2.pop()与insert()

那么知道了选择排序算法是怎么回事儿之后，我们就可以来尝试着来实现它了

由于每次循环都要获取一个最小值，因此，我们可以先将求解最小值的代码先写出来

a=[34,56,1,2,3,8,54]
min1=a[0]
for i in range(len(a)):
    if a[i]<min1:
        min1=a[i]
        
print(min1)
#result
#1

通过每次都与min1进行比较，如果a[i]的值小于min1，就将min1的值设置为a[i]，循环完成之后，成功的打印出了结果

了解了如何获得最小值，我们再来看看如何从列表当中取出值，我们可以使用pop()方法，它接受一个索引，我们可以通过index()方法来获取数值的索引

那么，怎么把元素添加到列表当中呢？我们可以使用insert()函数，因此，我们最后就可以写出选择排序的代码了

a=[34,56,1,2,3,8,54]

for j in range(len(a)):            #有多个数，就要循环多少次
    minindex=j
    for i in range(j,len(a)):    #内层循环用于获取最小值的索引
        if a[i]<=a[minindex]:
            minindex=i
    minNumber=a.pop(minindex)    #弹出最小值
    a.insert(0,minNumber)        #将最小值插入到开头

print(a)

#result
#[56, 54, 34, 8, 3, 2, 1]

3.元素交换

在上面的代码中，我们是通过了使用pop()和insert()函数的方式来进行排序，但是其实我们有一个更好的办法，使用元素交换，关于元素交换，有一个非常好的经典例子水杯交换的问题

假设我有一杯可乐（A）与一杯水（B），要将它们的杯子交换，那我们应该怎么办呢？

很明显，我们需要另外一个杯子C，将水放在C中，B就空了，我们就把可乐放在B中，这样A就空了，最后，我们在将杯子C中的水，放到A中，这样就完成了交换，因此，对于两个变量之间的数值交换，也是一样的，需要第三个变量

A=4
B=5

temp=A    #进行交换
A=B
B=temp

print(A,B)    #result:5, 4

我们可以就可以通过这样的方式来改进代码，找到最小值后，将最小值与j所在的位置进行交换

a=[34,56,1,2,3,8,54]

for j in range(len(a)):            #有多个数，就要循环多少次
    minindex=j
    for i in range(j,len(a)):    #内层循环用于获取最小值的索引
        if a[i]<=a[minindex]:
            minindex=i
    # minNumber=a.pop(minindex)    #弹出最小值
    # a.insert(0,minNumber)        #将最小值插入到开头
    temp=a[minindex]
    a[minindex]=a[j]
    a[j]=temp

print(a)
# result
# [1, 2, 3, 8, 34, 54, 56]

当然，我们还有其他的方式来进行元素交换，用python更加简洁的方式来进行

A=4
B=5
A,B=B,A
print(A,B)

# result
# 5, 4

思考：为什么两次运行的结果不一样呢？

4. 封装为通用方法

有了这个算法之后，我们还需要将它们封装一下，变成一个可以通用的算法，我们可以通过定义函数来完成

a=[34,56,1,2,3,8,54]
b=[45,12,23,56,34,5]
def sort_funtion(List):                #定义排序函数
    a=List                            #复制一个列表出来，不改变原来的列表
    for j in range(len(a)):            #有多个数，就要循环多少次
        minindex=j
        for i in range(j,len(a)):    #内层循环用于获取最小值的索引
            if a[i]<=a[minindex]:
                minindex=i
        temp=a[minindex]            #元素交换
        a[minindex]=a[j]
        a[j]=temp
    return a
print(sort_funtion(a))        #调用函数
print(sort_funtion(b))        #调用函数

5.综合练习

1.我们在这节课中学习了如何进行排序，那么，你能否把这排序的过程动态展示出来呢？
请尝试编写这样一个程序：利用海龟库，首先展示一个没有排好序的列表b，然后手动输入想要交换的元素的索引值，交换两个元素以达到排序的目的（最终与列表a的内容一致）。只有手动成功排序后程序才会结束，否则无限循环尝试，让使用者体验排序的过程。