选择排序
选择排序的思想
选择排序的思想比较直观：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素都排序完毕。
图解选择排序
选择排序的性质
- 最优时间复杂度：$O(n^2)$
- 最坏时间复杂度：$O(n^2)$
- 稳定性：不稳定（考虑升序每次选择最大的情况）
对考虑升序的情况进行说明：将下表中两个相同数据用（1）（2）进行区分，如果我们选择最大的数据放置末尾（从前往后遍历）：
| 原始数据 | 45（2） | 23 | 77 | 45（1） | 56 |
|---|---|---|---|---|---|
| 第一次 | 45（2） | 23 | 45（1） | 56 | 77 |
| 第二次 | 45（2） | 23 | 45（1） | 56 | 77 |
| 第三次 | 23 | 45（1） | 45（2） | 56 | 77 |
| 结果 | 23 | 45（1） | 45（2） | 56 | 77 |
由上面的过程可以看出（2）的位置在排序完后和（1）发生了交换，所以我们说该算法不稳定。
选择排序的代码实现
lst = list(map(int, input().split(',')))
def select_sort(alist):
n = len(alist)
for j in range(n - 1):
min_index = j
for i in range(j + 1, n):
if alist[min_index] > alist[i]:
min_index = i
alist[j], alist[min_index] = alist[min_index], alist[j]
return alist
select_sort(lst)