Python中排序算法之选择排序

选择排序算法是对《Python中排序算法之冒泡排序》中提到的冒泡排序算法的改进。

1 选择排序原理

选择排序是在参加排序的所有元素中找到数值最小（或最大）的元素，如果它不是左侧第一个元素，就使它与左侧第一个元素中的数据相互交换位置；然后在余下的元素中找出数值最小（或最大）的元素，如果它不是左侧第二个元素，就与左侧第二个元素的数据交换位置，以此类推，直到所有元素成为一个有序的序列。

2 选择排序的手动实现

假设数列中有“8、5、9、3、6”这5个数，使用选择排序算法对该数列进行升序（从小到大）排列，如图1所示。

图1 原始数列

首先，找出“8、5、9、3、6”这5个数中的最小数“3”，之后将“3”放在数列的最左端，如图2所示。

图2 第一次排序

注意1 “1 选择排序原理”中提到的是数列中最小数与数列左侧第一个数交换位置，得到两个子数列，如图2中红框和绿框中的数列。我们想得到的最终升序数列是红框中的子序列，绿框中子数列中数字的排列顺序对不影响最后的结果，也就是说，绿框中的数列顺序是“8、5、9、6”还是“5、9、8、6”，不影响最终的排序。

接下来在绿框中的数列中找出其最小值“5”，然后把“5”放到红框数列的尾部，如图3所示。

图3 第二次排序

之后继续在绿框的数列中查找最小值，放到红框数列的尾部，最终红框数列即为得到的升序数列，如图4所示。

图4 接下来的排序

注意2 使用选择排序算法对n个数字进行排序时，需要排n-1次。

注意3 选择排序的排序次数与冒泡排序相同，但是交换数字位置的次数要比冒泡排序少，因此它具有更高的效率。

3 选择排序的编码实现

通过图5所示的代码实现选择排序。

图5 选择排序的代码实现

其中，第1行为原始的数列；第2行的for循环为排序的次数；第3行中的变量k表示绿框序列中最小值的下标，将其初始值设置为i，即绿框中左侧第一个数的下标；第4-6行通过for循环找到绿框数列中的最小值，并将其下标保存到变量k中；如果最小值就是绿框中左侧第一个数，则此时无需交换数字的位置，如果最小值不是绿框中左侧第一个数，如第7行代码所示，则交换两个数的位置，如代码第8行所示。程序运行的结果如图6所示。