01选择排序

1.选择排序含义

• 每次选择最小的，放到左侧。持续进行。

2.示例代码：

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        # if i != minIndex:
        #     arr[i], arr[minIndex] = arr[minIndex], arr[i]
        # 交换
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr


if __name__ == '__main__':
    arr = [3, 6, 1, 2, 4, 5]
    print(selectionSort(arr))

3.练习代码：

def select_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i,n):
            if arr[j] < arr[min_index]:
                min_index = j
        if arr[i] != arr[min_index]:
            arr[i],arr[min_index] = arr[min_index],arr[i]
    return arr

if __name__ == '__main__':
    nums = [1,4,5,3,2]
    print(select_sort(nums))

4.截图：

5.感悟：

• O（n^2）的复杂度
• 还是，最后加一个这个arr[i]!=arr[min_index]这个判断更好理解。

6.代码思路：

• 每次暂时定一个索引i位置的为最小值，往后进行比较，看是不是最小值。是的话，就更新索引，最后这一轮拿到的就是最小值。进行交换。

7.参考资料：

• https://www.runoob.com/w3cnote/selection-sort.html
• https://www.bilibili.com/video/BV12P41147to/?spm_id_from=333.999.0.0&vd_source=6176e79b66461eb74da787cb8321925b