算法010_选择排序

选择排序
每次遍历，找到一个最小的数，放到新的列表当中，然后再遍历，再找最小的数放到新列表当中。

• 一趟排序记录最小的数，放到第一个位置
• 再一趟排序记录列表无序区最小的数，放到第二个位置
• 算法关键点：有序区和无序区、无序区最小数的位置
• 算法复杂度：

简单版本
进行列表循环，然后找到最小的把它放到新的列表当中

def select_sort_simple(target_list):
    new_list = []
    for i in range(len(target_list)):
        min_val = min(target_list)
        new_list.append(min_val)
        target_list.remove(min_val)
    return new_list


test_list = [3, 2, 4, 1, 5, 6, 8, 7, 9]
print("原始的列表: ", test_list)
print("排序后列表: ", select_sort_simple(test_list))

运行结果

原始的列表:  [3, 2, 4, 1, 5, 6, 8, 7, 9]
排序后列表:  [1, 2, 3, 4, 5, 6, 7, 8, 9]

这些写法的问题
这种写法的问题
（1）多占一份内存，不是原地排序
（2）算法复杂度高。因为 remove 和 min 都不是 的复杂度，min 是需要遍历一遍才能找到的，remove 删除之后需要把后面的数往前移动，导致算法的复杂度是 。remove 和 min 的操作是一个 ，然后外层有一个循环，导致复杂度是

进阶版
进阶版：把找出来的值放到列表的第一个位置，然后左边是有序区，右边是无序区
需要进行 n - 1 趟排序，需要留一个数进行交换，因此是 n - 1 趟

def select_sort_advanced(target_list):
    for i in range(len(target_list) - 1):  # i是第几趟
        min_location = i  # 记录最小数的索引，是无序区的最后一个数的索引
        for j in range(i + 1, len(target_list)):  # 从 i + 1 开始比较
            if target_list[j] < target_list[min_location]:
                min_location = j  # 把最小数的下标给 min_location
        # 循环结束，得到最小数的下标，然后进行交换
        if min_location != i:
            target_list[i], target_list[min_location] = target_list[min_location], target_list[i]


test_list = [3, 4, 2, 1, 5, 6, 8, 7, 9]
print("原始的列表: ", test_list)
select_sort_advanced(test_list)
print("交换后列表: ", test_list)

运行结果

原始的列表:  [3, 4, 2, 1, 5, 6, 8, 7, 9]
交换后列表:  [1, 2, 3, 4, 5, 6, 7, 8, 9]