Python选择排序算法

选择排序表示从无序的数组中,每次选择最小或最大的数据,从无序数组中放到有序数组的末尾,以达到排序的效果。选择排序的平均时间复杂度是O(n2),最好情况下的时间复杂度和最坏情况下的时间复杂度都是 O(n2)。另外,它是一个不稳定的排序算法。

选择排序的过程如下;

1) 如图 1 所示,我们仍以递增排序的算法为例,先遍历未排序的数组,找到最小的元素。然后,把最小的元素从未排序的数组中删除,添加到有序数组的末尾。因为最小的元素是 1,所以 1 被添加到仍为空的有序数组末尾。
选择并放置第一个元素
图 1:选择并放置第一个元素

2) 如图 2 所示,我们继续对剩余元素进行遍历。这次,最小的元素是 2。我们把它添加到已排序的数组末尾。由于已在有序数组中的元素必定小于未排序数组中的所有元素,所以这步操作是正确无误的。
选择并放置第二个元素
图 2:选择并放置第二个元素

3) 如图 3 所示,重复上述步骤,当未排序数组中只剩下一个元素时,把它添加到已排序的数组末尾,整个数组的排序就完成了。
选择并放置剩余元素
图 3:选择并放置剩余元素

以下代码采用图 1~图 3 中的思路,将数组 nums 进行正序排序。

选择排序代码(基础版):
nums = [5,3,6,4,1,2,8,7]
res = []   #用于存储已排序元素的数组
while len(nums): #当未排序数组内还有元素时,重复执行选择最小数的代码
    minInd = 0 #初始化存储最小数下标的变量,默认为第一个数
    for i in range(1, len(nums)):
        if(nums[i] < nums[minInd]): #更新最小数的下标
            minInd = i
    temp = nums[minInd]
    nums.pop(minInd) #把最小数从未排序数组中删除
    res.append(temp) #把最小数插入到已排序数组的末尾
print(res)
运行程序,输出结果为:

[1,2,3,4,5,6,7,8]


代码中,外层的 while 循环用于判断是否所有的元素都已经进入有序的数组,从而确定排序是否已经完成。如果无序数组中已经没有元素,说明排序已经完成。

在开始遍历无序数组之前,先初始化记录最小值下标的变量为 0,所以 for 循环可以从第二个元素,也就是下标为 1 的元素开始遍历。找到最小值后,用 temp 存储最小数的值。执行 pop( ) 函数把最小数从原数组中删除,这样它不会影响下一步的选择。最后,用 append( ) 函数把 temp 存储的元素插入到有序数组末尾。

虽然这样实现排序较为直观,代码逻辑也比较简单,但可以注意到,这样实现插入排序需要两个同样大小数组的空间。如果要处理的数据量较大,这样的算法会浪费资源。所以,我们要对算法做一些改动,使选择排序能够在同一个数组内完成。同样地,我们用图来展示这个过程。

1) 首先,如图 4 所示,在未排序的数组中找到最小的数 1。
定位最小值
图 4:定位最小值

2) 此时,它是我们找到的第一个最小数。如图 5 所示,我们把它与数组的第一个元素交换。

最小值与首元素互换位置
图 5:最小值与首元素互换位置

3) 如图 6 所示,这时候,数组中的第一个位置就成了有序数组的一部分。
有序数组的第一个元素
图 6:有序数组的第一个元素

4) 接下来,如图 7 所示,由于第一个元素已经有序了,所以我们只需要在它之后的数组中搜索最小值。这一遍搜索过后,最小值是2,所以把2和第二个元素交换位置。
最小值与第二位元素互换位置
图 7:最小值与第二位元素互换位置

5) 如图 8 所示,2 和第二个元素交换位置后,第二个位置就成了这个有序数组的一部分。
第二次交换结束
图 8:第二次交换结束

6) 继续重复以上步骤,直到所有元素都被加入到有序数组中。如图 9 所示,下面给出了确定第三小的数并将其排序的过程。
第三次交换结束
图 9:第三次交换结束

7) 当所有元素都加入有序数组后,排序就完成了,如图 10 所示。
插入排序完成
图 10:插入排序完成

我们可以使用代码按照上述思路实现选择排序。

选择排序代码(“原地”版):
nums = [5,3,6,4,1,2,8,7]
for i in range(len(nums)-1): #更新有序数组的末尾位置
    minInd = i
    for j in range(i,len(nums)): #找出未排序数组中最小值的下标
        if nums[j] < nums[minInd]:
            minInd = j
    nums[i],nums[minInd] = nums[minInd],nums[i] #把最小值加到有序数组末尾
print(nums)
运行程序,输出结果为:

[1,2,3,4,5,6,7,8]


在程序中,第一个 for 循环中的 i 代表了有序数组之后的第一个位置,也就是未排序数组中的第一个位置。随后,再使用一个 for 循环,在未排序数组中找到最小值的下标。首先,把最小值下标 minInd 初始化为未排序数组中第一个元素的下标。

随后,遍历整个数组,遇到比目前的最小值更小的元素时,更新下标即可。找出最小值后,把它和未排序数组中的第一个元素交换位置,这时它就成了有序数组中的最后一个元素。

在其他一些编程语言中,不能像 Python 一样使用 pop、insert 等函数对数组进行操作。插入一个数时,需要把插入位置及后面的所有元素都向后移动一位,此时,本节中的“原地”版算法优势更加明显。