下载掌阅APP，畅读海量书库
立即打开
选择排序表示从无序的数组中，每次选择最小或最大的数据，从无序数组中放到有序数组的末尾，以达到排序的效果。
选择排序的平均时间复杂度是 O ( n 2 )，最好情况下的时间复杂度和最坏情况下的时间复杂度都是 O ( n 2 )。另外，它是一个不稳定的排序算法。
选择排序的过程很容易理解。如图2-4所示，我们仍以递增排序的算法为例，先遍历未排序的数组，找到最小的元素。然后，把最小的元素从未排序的数组中删除，添加到有序数组的末尾。
图2-4 选择并放置第一个元素
因为最小的元素是1，所以1被添加到仍为空的有序数组末尾。
如图 2-5 所示，我们继续对剩余元素进行遍历。这次，最小的元素是 2。我们把它添加到已排序的数组末尾。由于已在有序数组中的元素必定小于未排序数组中的所有元素，所以这步操作是正确无误的。
图2-5 选择并放置第二个元素
如图2-6所示，重复上述步骤，当未排序数组中只剩下一个元素时，把它添加到已排序的数组末尾，整个数组的排序就完成了。
图2-6 选择并放置剩余元素
以下代码采用图2-4～图2-6中的思路，将数组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存储的元素插入到有序数组末尾。
虽然这样实现排序较为直观，代码逻辑也比较简单，但可以注意到，这样实现插入排序需要两个同样大小数组的空间。如果要处理的数据量较大，这样的算法会浪费资源。所以，我们要对算法做一些改动，使选择排序能够在同一个数组内完成。同样地，我们用图来展示这个过程。
首先，如图2-7所示，在未排序的数组中找到最小的数1。
图2-7 定位最小值
此时，它是我们找到的第一个最小数。如图2-8所示，我们把它与数组的第一个元素交换。
图2-8 最小值与首元素互换位置
如图2-9所示，这时候，数组中的第一个位置就成了有序数组的一部分。
图2-9 有序数组的第一个元素
接下来，如图2-10所示，由于第一个元素已经有序了，所以我们只需要在它之后的数组中搜索最小值。这一遍搜索过后，最小值是2，所以把2和第二个元素交换位置。
如图2-11所示，2和第二个元素交换位置后，第二个位置就成了这个有序数组的一部分。
图2-10 最小值与第二位元素互换位置
图2-11 第二次交换结束
继续重复以上步骤，直到所有元素都被加入到有序数组中。如图2-12所示，下面给出了确定第三小的数并将其排序的过程。
图2-12 第三次交换结束
当所有元素都加入有序数组后，排序就完成了，如图2-13所示。
图2-13 插入排序完成
我们可以使用代码按照上述思路实现选择排序。
选择排序代码（“原地”版）：
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等函数对数组进行操作。插入一个数时，需要把插入位置及后面的所有元素都向后移动一位，此时，本小节中的“原地”版算法优势更加明显。