python数据结构之选择排序

选择排序（Selection sort）

是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

稳定性的概念：在排序过程中，相同元素的顺序在排序完成后顺序依然不发生变化
选择排序相对于冒泡排序的来说是不稳定的
当选择排序在（升序每次选择最大的情况下）是有可能发生不稳定的情况的

思路：
1.给定一个下标，记录每次排序的最小值（1~n-1）
2.排序过程中,用记录的最小值的下标去和其他元素相比较，如果其他元素是较小值，重新记录下标值
3.在一轮排序完成后将初始下标值的元素和最终得到的最小值下标的元素交换位置，然后开始下一轮的排序
4.一共需要执行（0~n-2）次排序

def selection_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
 
if __name__ == '__main__':
    li = [1, 3, 4, 2, 9, 5, 8]
    print(li)
    selection_sort(li)
    print(li)

注意range左开右闭，要分析个数
选择排序的时间复杂度都是O（n**2）,没有最优解
感觉Python中min和max的方法可以就是根据这个内部封装的

def min(alist):
    n = len(alist)
    min_index = 0
    for i in range( 1, n):
        if alist[min_index] > alist[i]:
            min_index = i
    alist[0], alist[min_index] = alist[min_index], alist[0]
    return alist[0]