干货！Python排序算法之选择排序

选择排序法就是反复从未排序的数列中取出最小（ 最大 的数据，将其存放在序列的起始位置，然后，再从未排序的元素中继续寻找最小（ 最大 的数据，存放在已排序序列的末尾，以此类推。最后的结果即为已排序好的数列。选择排序法最后的结果有两种形式，即递增数列和递减数列，下面就对于两种结果形式的具体排序流程进行描述。

• 结果为递增排序 首先在未排序数列中取最小值，与数列第一个位置交换；然后再从未排序的数列中取最小值，与数列的第二个位置交换。如此重复，直到排序数列中的数据按照从小到大的顺序排序完成。

• 结果为递减排序 首先在未排序数列中取最大值，与数列第一个位置交换；然后再从未排序的数列中取最大值，与数列的第二个位置交换。如此重复，直到排序数列中的数据按照从大到小的顺序排序完成。

接下来用一组数据来详细讲解选择排序法。例如，有这样一组数据 56，18，49，84，72，如图1所示。

图1 原始值

按照递增顺序进行排序，步骤如下

步骤1 找到如图5.1所示数列中的最小值18与此数列中的第一个元素56交换，如图2所示。

图2  第一次排序结果

步骤2 从第二个值开始，找到此数列中（不包含第一个值 的最小值49，再和第二个值56交换，如图3所示。

图3  第二次排序结果

步骤3 从第三个值开始，找到此数列中（不包含第一、第二个值 的最小值56，再和第三个值84交换，如图4所示。由于56小于84，且它本来就是在第三个位置，因此不需要交换。

图4  第三次排序结果

步骤4 从第四个值开始，找到此数列中（不包含第一、第二、第三个值 的最小值72，再和第四个值84交换，如图5所示。

图5  第四次排序结果

步骤5 数列递增顺序排序完毕，结果如图6所示。

图6  递增顺序排序结果

实例1 使用选择排序法进行递增排序     

使用选择排序法为列表 56，18，49，84，72，进行递增排序。具体代码如下

def choose(data):                                # 自定义一个选择排序法函数

    for i in range(4):                              # 遍历新数据

        for j in range(i+1,5):            

            if data[j]<data[i]:                  # 如果数据小于原来的数据

                data[i],data[j]=data[j],data[i]     # 需要交换位置

        print('第 %d 次排序之后的结果是'%(i+1),end='') # 提示

        for j in range(5):                       # 遍历每次排序的结果

            print('%3d'%data[j],end='')          # 输出结果

        print()                            # 输出空行

data=[56,18,49,84,72]                          # 创建数列并初始化

print("原始数据为 ")                         # 提示

for i in range(5):                               # 遍历原有数据

    print('%3d'%data[i],end='')                   # 输出结果

print('\n---------------------------')                     # 输出分界符

choose(data)                                  # 调用选择排序法函数

print('\n---------------------------')                    # 输出分界符

print("排序之后的数据为 ")                    # 提示

for i in range(5):                                 # 遍历排序好的新数列的数据

    print('%3d'%data[i],end='')                   # 输出结果

print('')                                      # 输出空行

程序运行结果如图7所示。

图7  选择排序法

从图7所示的运行结果来看，排序的步骤和上述介绍的步骤完全吻合。

实例2 为五名学生的期末考试成绩排名             

例如 五名学生的期末考试成绩如下 420，434，421，539，555，利用选择排序法把这五名学生的期末考试成绩按照从高到低的顺序进行排序，具体代码如下

def choose(data):                                            # 自定义一个选择排序法函数

    for i in range(4):                                         # 遍历新数据

        for j in range(i+1,5):

            if data[j]>data[i]:                      # 如果数据大于原来的数据

                data[i],data[j]=data[j],data[i]            # 需要交换位置

        print('第 %d 次排序之后的结果是'%(i+1),end='') # 提示

        for j in range(5):                          # 遍历每次排序的结果

            print('%6d'%data[j],end='')               # 输出结果

        print()                                    # 输出空行

data=[420,434,421,539,555]                          # 创建数列并初始化

print("各个学生成绩如下 ")                     # 提示

for i in range(5):                                   # 遍历原有数据

    print('%6d'%data[i],end='')                        # 输出结果

print('\n---------------------------')                             # 输出分界符

choose(data)                                   # 调用选择排序法函数

print('\n---------------------------')                             # 输出分界符

print("从高到低排名之后的成绩如下 ")              # 提示

for i in range(5):                                   # 遍历排序好的新数列的数据

    print('%6d'%data[i],end='')                        # 输出结果

print('')                                       # 输出空行

程序运行结果如图8所示。

图8  期末考试成绩排名