数据结构之选择排序

数据结构之选择排序

选择排序（Selection sort）是一种简单直观的排序算法，他的工作原理如下，首先将未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中急需寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动相关。如果某个元素位于了正确的最终位置上，那它不会移动，选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序算法分析

简述：每次把未排序的部分遍历，把最小值排到该部分的首元素。

对于未排序的原始数列alist = [2,3,5,3,5,1,6,7,3,5,4]，选择排序的原理如下：

首先假设序列的第一个元素为最小值，其最小值索引记为min_index = 0，比如第一个元素2记为最小元素，将剩余元素依次与之比较，找到比它更小的数据，可以发现1是比2更小的数据，且1的索引为5，加下来就将1的值与假设的最小元素2进行交换位置，如此一来，序列中最小值就被交换到序列的首位置

其次，将剩余未排序的序列的第一个元素假设为剩余序列中的最小元素，采取上述的方法进行操作，找到次最小值，以此类推，便可完成序列的排序工作。

时间复杂度 选择排序算法实现

def select_sort(list):
    """选择排序"""
    n = len(list)
    for i in range(n - 1):
        min = i
        for j in range(i + 1, n):
            if list[min] > list[j]:
                min = j
        list[min], list[i] = list[i], list[min]


if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 50, 20]
    print('排序前：', li)
    select_sort(li)
    print('排序后：', li)

运行结果：