Python|调换位置来排序

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

引言

在生活休息时，有人喜欢打麻将。如果你也会打麻将，你一定会发现：在刚拿到牌的时候，牌的顺序一定是无序的，然后你就会按花色给牌进行排序。在进行排序时，如果你是习惯从小到大的顺序，你一定会将其中两张牌调换位置，并且重复这一步骤，直到排完序。而这里面也包含了一个排序算法—简单选择排序。

问题描述

将下列无序的数字进行排序：【99、33、55、66、22、88、77、11】。

算法描述

首先扫描一遍数组，找到最小的那个元素，即11。然后进行第一次排序：只将99与11调换位置，其他元素位置不变，即【11、33、55、66、22、88、77、99】。进行第二次排序：发现第二个位置本应该是22（第二小的元素），但却是33，所以将33与22调换位置，其他元素位置不变，即【11、22、55、66、33、88、77、99】。进行第三次排序：发现55＞33，所以将55与33调换位置，即【11、22、33、66、55、88、77、99】。然后后面只需要重复以上操作，就可以得到最后的排序数组【11、22、33、44、55、66、77、88、99】

简单选择排序算法思想：一方面，顺序扫描序列中的元素，记住扫描到的最小元素。在一次扫描完毕后就可以找到最小的元素，重复扫描就能完成排序。另一方面：在选出了一个元素后，原来的序列中就会出现空位，就把这些空位集中起来存放已排好的序列

简单选择排序的方法：首先将最小的元素与第一个元素调换位置（如果第一个元素就是最小的元素，则忽略这一步），下一步从未排序的元素中选择最小元素与第二个位置的元素调换位置，即放在第一个元素后面。然后不停的重复以上两步，将要排序的元素放在已排好序段的后面，最终就可以得到有序序列。

结语

在排序过程中，其实我们还可以发现：在排序过程中的任何时刻，被排序表的前段是一段已排好序的，并且他们都不大于任何一个还未排序的元素。

主编：欧洋

稿件来源：深度学习与文旅应用实验室（DLETA）