选择排序

选择排序工作原理

假设有一个数组需要使用选择排序的方法将数据从小到大排序，工作步骤如下：

• 查找数组中最小的元素，将其与第一位元素进行互换
• 对于剩下的元素，再次运行上述步骤，直到所有元素已完成排序

使用Python实现

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

"""
@Time    : 2020/4/11 13:24
@Author  : focksor
@Contact : 
"""

from random import randint


def selection_sort(arr):
    print("原始列表：", arr)
    for i in range(len(arr)):
        min_index = i
        # 获取最小元素的索引
        for j in range(i+1, len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]
        print("第%s次排序后： %s" % (i+1, arr))

    print("排序完成：", arr)


if __name__ == ‘__main__‘:
    arr = [randint(0, 10000) for _ in range(10)]
    selection_sort(arr)

原始列表： [4104, 8091, 732, 4719, 4860, 4893, 8129, 1410, 8934, 5257]
第1次排序后： [732, 8091, 4104, 4719, 4860, 4893, 8129, 1410, 8934, 5257]
第2次排序后： [732, 1410, 4104, 4719, 4860, 4893, 8129, 8091, 8934, 5257]
第3次排序后： [732, 1410, 4104, 4719, 4860, 4893, 8129, 8091, 8934, 5257]
第4次排序后： [732, 1410, 4104, 4719, 4860, 4893, 8129, 8091, 8934, 5257]
第5次排序后： [732, 1410, 4104, 4719, 4860, 4893, 8129, 8091, 8934, 5257]
第6次排序后： [732, 1410, 4104, 4719, 4860, 4893, 8129, 8091, 8934, 5257]
第7次排序后： [732, 1410, 4104, 4719, 4860, 4893, 5257, 8091, 8934, 8129]
第8次排序后： [732, 1410, 4104, 4719, 4860, 4893, 5257, 8091, 8934, 8129]
第9次排序后： [732, 1410, 4104, 4719, 4860, 4893, 5257, 8091, 8129, 8934]
第10次排序后： [732, 1410, 4104, 4719, 4860, 4893, 5257, 8091, 8129, 8934]
排序完成： [732, 1410, 4104, 4719, 4860, 4893, 5257, 8091, 8129, 8934]

Process finished with exit code 0

时间复杂度

选择排序第一次排序需要检查n个元素以寻找最小值，第二次需要检查n-1个，第三次需要检查n-2个。。。所以排序完成需要的操作数为：\(n+(n-1)+(n-2)+...+2\)，可以看出这是一个公差为1的等差数列，和为\((n+2)*n/2\)，所以选择排序的时间复杂度为\(O(n^2)\)

稳定性

排序算法稳定性是指，具有相同关键字的记录，排序完成后前后次序是否发生变化，如果变化则称为是不稳定的，否则为稳定的

假设有原始数组[2，1#1，1#2]（这里的#1，#2仅是用于标记这是第几个1的），通过选择排序，完成后的列表为[1#2，1#1，2]，可见相同关键字1的两个元素排序前后次序发生了变化，所以选择排序是不稳定的。