【算法】选择排序 Select Sort

算法介绍

选择算法，以升序排序为例，每次从未排序的数据中找出（选出）最小数，然后将这个数放在已排序数据的后面。

视频演示

视频地址：https://www.bilibili.com/video/av18176082

python代码

#-*- coding: utf-8 -*-

# 升序
def select_sort(data):
    n = len(data)
    # 外循环，i 代表扫描轮数，一共扫描 n-1 轮
    for i in range(n-1):
        min_idx = i
        # 内循环，从未排序数据中找出最小数
        for j in range(i+1, n):
            if data[min_idx]>data[j]:
                min_idx=j
        if min_idx!=i:
            data[min_idx], data[i] = data[i], data[min_idx]
    return data


if __name__ == '__main__':
    data = [64, 25, 12, 22, 11]
    sorted_data = select_sort(data.copy())
    print("排序前：", data)
    print("排序后：", sorted_data)

算法分析

无论真实数据如何，比较次数固定为：n*(n-1)/2。

最好情况下，数据刚好是升序的，不需要交换数据；
最坏情况下，数据刚好是降序的，每轮选择都需要交换数据，即交换数据次数为：n-1

选择排序时间复杂度为：O(n^2)

需要一个辅助标记记录每轮最小值的位置。

选择排序空间复杂度为：O(1)