八大排序之选择排序

算法核心思想

选择排序的算法核心思想是从数组中选择最小的元素，放到第一个位置，再从数组 中选择第二小的元素放到第二个位置，一直到数组的最后一个元素为止。

选择排序的具体实现步骤

1. 选择数组的第一小的元素，将其放在第一个位置
2. 选择数组的第二小的元素，将其放在第二个位置
3. 重复上述步骤。。。
4. 选择数组的第三小的元素，将其放在第n个位置

代码实现

def selectSort(arr):
    length = len(arr)
    for i in range(length):
        min_value_index = i
        #查找数组的最小值的索引
        for j in range(i+1,length):
            if arr[j] < arr[min_value_index]:
                min_value_index = j
        #将最小值放到第i个位置
        arr[i],arr[min_value_index] = arr[min_value_index],arr[i]
    return arr

执行解析

使用2层for循环，外层循环控制查找第几小的元素，用于真正的查找，当内层循环 找到第n小的元素的时候，将其放置在第n个位置。当所有的元素都放置结束后，排 序结束。

时间复杂度分析&稳定性

选择排序时间复杂度是0( n²)，选择排序是一种不稳定排序，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺 序就被破坏了，所以选择排序是一个不稳定的排序算法。