1. 什么是选择排序？
选择排序（Selection sort）的基本原理是：从列表中选出最大(小)的元素，放到列表的起始位置，然后从剩余的元素中选出最大(小)的元素放到已排好序的列表的后面，直到所有元素都排好。
2. 图解选择排序
图解选择排序
3.代码实现
· 两个列表实现选择排序
def findlargest(arr):
largest = arr[0]
largest_index = 0
for i in range(1, len(arr)):
if arr[i] > largest:
largest_index = i
largest = arr[i]
return largest_index
def selectionsort(arr):
newArr = []
for i in range(len(arr)):
smallest = findlargest(arr)
newArr.append(arr.pop(smallest))
return newArr
· 一个列表实现选择排序
def selectionsort(arr):
for i in range(0, len(arr)):
for j in range(i+1, len(arr)):
if arr[j] > arr[i]:
arr[i], arr[j] = arr[j], arr[i]
return arr
4. 时间复杂度
选择排序的时间复杂度是O(n^2)。
第一次需要检查n个元素，但随后检查的元素数依次为n-1, n-2, …, 2和1。平均每次检查的元素数为1/2 × n，因此运行时间为O(n × 1/2 × n)。但大O表示法省略诸如1/2这样的常数，因此简单地写作O(n × n)或O(n^2)。
5. 进一步思考选择排序
选择排序比较耗费时间的地方就在于每次循环只选出一个符合条件的元素，我们可以进一步思考，如果每次循环能选出两个元素放到指定位置，效率会不会提升呢？
以下代码一次选出两个元素，最大和最小的元素：
def selectionsort3(arr):
n = len(arr)
for i in range(0, n//2):
largest = arr[i]
largest_index = i
smallest = arr[n-i-1]
smallest_index = n-i-1
for j in range(i+1, n-i):
if arr[j] > largest:
largest = arr[j]
largest_index = j
if arr[j] < smallest:
smallest = arr[j]
smallest_index = j
arr[i], arr[largest_index] = arr[largest_index], arr[i]
arr[n-i-1], arr[smallest_index] = arr[smallest_index], arr[n-i-1]
return arr
使用了10000的随机数，进行了简单比较：
一个列表实现选择排序 6s
选择两个元素的方法 2s
