【排序】选择排序

选择排序（Selection sort）是一种简单直观的排序算法，将数列分为两部分：排序部分和待选择部分，每次从待选择的数列选出最大或者最小的元素放置于起始位置。

算法思想

• 将第一个作为比较元素，一次和后边的比较，完事儿找到最小的元素，和第一个元素比较；
• 重复操作，直到找到第二小的元素和第二个元素互换，以此类推

代码实现

def selection_sort(arr):
    """选择排序"""
    # 第一层for表示循环选择的遍数
    for i in range(len(arr) - 1):
        # 将起始元素设为最小元素
        min_index = i
        # 第二层for表示最小元素和后面的元素逐个比较
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                # 如果当前元素比最小元素小，则把当前元素角标记为最小元素角标
                min_index = j
        # 查找一遍后将最小元素与起始元素互换
        arr[min_index], arr[i] = arr[i], arr[min_index]
    return arr

算法分析

与冒泡不同的是，每次只有一次数据交换，因而可以减少CPU消耗，实际使用还是少

• 比较性：需要比较来处理，属于比较排序
• 稳定性：与冒泡不同，因为不是相邻元素交换，所以肯定会发生相同元素之间的换位，所以属于不稳定排序
• 时间复杂度：与冒泡一样，同样是双层循环n(n-1)，所以是O(n^2)
• 空间复杂度：只需常数辅助单元，所以是O(1)
• 内层循环做对比的时候，遇到小的元素只是先更改min_index的指向，等到一轮内层循环结束才会进行数据交换，因为内层只有一次数据交换。