选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n^2) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法原理

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;

再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;

重复第二步,直到所有元素均排序完毕。

图解

xuanze.gif

复杂度分析

最坏复杂度: 时间复杂度为 O(n^2)

最好复杂度:时间复杂度为 O(n^2)

平均复杂度: 时间复杂度为 O(n^2)

def select_sort(sequence):
    for i in range(len(sequence)-1):
        minIndex = i  # 记录最小数的索引
        for j in range(i+1, len(sequence)):
            if sequence[j] < sequence[minIndex]:
                minIndex = j
        # 将该数放到已排序序列的末尾
        sequence[minIndex], sequence[i] = sequence[i], sequence[minIndex]
    return sequence