什么是选择排序

上一篇学习了二分查找算法，但是要求序列的有序性，所以这一篇学习了排序算法--选择排序，选择排序的原理是先选择样本中的极值（最小值或最大值），比如每次都选择最小值，让后将其有顺序的储存在容器中，直至样本枯竭。

例如有一样本[3,6,8,9,5,4,7,1,2,0],使用选择排序从小到大排序过程如下：

样本：[3,6,8,9,5,4,7,1,2,0]

有序集合：[]

第一次选择：

最小值=3，

比较值=6,3<6,

最小值=3，

比较值=8,3<8,

最小值=3，

比较值=9,3<9,

最小值=3，

比较值=5,3<5,

最小值=3，

比较值=4,3<4,

最小值=3，

比较值=7,3<7,

最小值=3，

比较值=1,3>1,

最小值=1，

比较值=2,1<2,

最小值=1，

比较值=0,0<1,

最小值=0，存入有序集合，样本弹出0

样本：[3,6,8,9,5,4,7,1,2]

有序集合：[0]

如此这般，不断的进行选择最小值，然后存入有序结合，直至样本中无数据。

小结

选择排序是一种灵巧的算法，但其速度不是很快。一个容量为n的样本空间，第一次需要比较n-1次，第二次需要比较需要n-2次，比较9次选出10个值，即：

(N - 1) + (N - 2) + ... + 1 = (N - 1 + 1)* N / 2 = N^2 / 2

所以选择排序的时间复杂度简化为为O（n^2）

代码实现

List = [3,6,8,9,5,4,7,1,2,0,]

def select_min(list):
    min = list[0]
    for i in range(1,len(list)):
        next = list[i]
        if min > next:
            min = next
    list.remove(min)
    return min

def sort(list):
    sort_arr = []
    for i in range(1, len(list)):
        sort_arr.append(select_min(list))
    sort_arr.append(List[0])
    return sort_arr

print(sort(List))

E:\DataAnalysis\tools\python3\python.exe E:/DataAnalysis/tools/python3/project/SuanFa/SelectionSort/selection_sort.py
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Process finished with exit code 0