定义
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
算法步骤
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
动图分析
选择排序过程
过程分析
这六个数组成的无序序列[5,9,3,6,2,7]，由小到大排序。
按照选择排序算法，过程如下：
-
第一次选择，找到最小值2，和第一个数字交换，第一次结果为：[2,9,3,6,5,7]
-
第二次选择，由于数组第一个位置已经是有序的，所以只需要查找剩余位置，找到其中最小的数字3，然后和数组第二个位置的元素交换，第二次结果为：[2,3,9,6,5,7]
-
第三次选择，找到最小数5，然后和数组第三个位置的元素进行交换，第三次结果为：[2,3,5,6,9,7]
-
第四次选择，找到最小数6，由于6就在第四个位置，自己和自己交换位置，第四次结果为：[2,3,5,6,9,7]
-
第五次选择，找到最小数7，和数组第五个位置元素进行交换，第五次结果为：[2,3,5,6,7,9]
-
最后一个到达了数组末尾，没有可对比的元素，结束选择。
python实现选择排序
def selection_sort(arr):
n = len(arr)
# 交换次数
count_swap = 0
# 循环次数
count_iter = 0
# 需要进行n-1次选择
for i in range(n - 1):
# 记录最小数位置
min_index = i
# 从i+1位置到末尾选择出最小的数字
for j in range(i+1, n):
count_iter += 1
if arr[j] < arr[min_index]:
min_index = j
# 如果位置不对，进行交换
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
count_swap += 1
print("第{}次选择排序结果为：{}".format(i+1, arr))
print("选择排序交换次数为：{}".format(count_swap))
print("选择排序循环次数为：{}".format(count_iter))
return arr
if __name__ == '__main__':
arr = [5, 9, 3, 6, 2, 7]
print(selection_sort(arr))
结果：
第1次选择排序结果为：[2, 9, 3, 6, 5, 7]
第2次选择排序结果为：[2, 3, 9, 6, 5, 7]
第3次选择排序结果为：[2, 3, 5, 6, 9, 7]
第4次选择排序结果为：[2, 3, 5, 6, 9, 7]
第5次选择排序结果为：[2, 3, 5, 6, 7, 9]
选择排序交换次数为：4
选择排序循环次数为：15
[2, 3, 5, 6, 7, 9]
选择排序优化（二元选择排序）
优化思路：既然我们能一次找到最小值，那么最大值肯定也能找到，同时确定最大、最小值，减少迭代次数，达到优化目的。
代码实现：
def selection_sort(arr):
n = len(arr)
# 交换次数
count_swap = 0
# 循环次数
count_iter = 0
# 一次确定两个值，减半
for i in range(n // 2):
# 记录最小值位置
min_index = i
# 记录最大值位置,负索引
max_index = -i - 1
# 记录原始最大值位置
maxorigin = max_index
# 每次左边 +1 向右边走， 右边也需要 +1 向左走
for j in range(i+1, n - i):
count_iter += 1
if arr[min_index] > arr[j]:
min_index = j
if arr[max_index] < arr[-j -1]:
max_index = -j -1
# 如果最大和最小值相等，剩下的数据一定是重复的，不需要比较
if arr[max_index] == arr[min_index]:
break
# 如果位置不对，进行交换
if i != min_index:
arr[i], arr[min_index] = arr[min_index], arr[i]
count_swap += 1
# 如果最大值被交换过，更新索引
if i == max_index or i == n + max_index:
max_index = min_index
if maxorigin != max_index:
arr[maxorigin], arr[max_index] = arr[max_index], arr[maxorigin]
count_swap += 1
print("第{}次选择排序结果为：{}".format(i+1, arr))
print("选择排序交换次数为：{}".format(count_swap))
print("选择排序循环次数为：{}".format(count_iter))
return arr
if __name__ == '__main__':
arr = [5, 9, 3, 6, 2, 7]
print(selection_sort(arr))
结果：
第1次选择排序结果为：[2, 7, 3, 6, 5, 9]
第2次选择排序结果为：[2, 3, 5, 6, 7, 9]
第3次选择排序结果为：[2, 3, 5, 6, 7, 9]
选择排序交换次数为：4
选择排序循环次数为：9
[2, 3, 5, 6, 7, 9]
时间复杂度
- 最优时间复杂度：O(n^2)
- 最坏时间复杂度：O(n^2)
稳定性
考虑升序每次选择最大的情况，所以选择排序是不稳定排序算法
