vlambda博客
学习文章列表

我的《算法刷题日记》知识星球，Day2 星球内的朋友们打卡非常积极，截止目前已经有 100多 位提交代码打卡。下面是今天部分打卡的截图：

之所以放上这些截图，是帮助大家更加方便辨别我的这个星球是否对你真正有用。‍‍

‍

下面总结下 Day2：选择排序算法，以下主要参考：@川 顺 页，@Leven 两位球友的打卡总结。

1.1 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

1.2 这种性能差

有一部分球友提交了下面这个版本，此代码中虽然也没有太大问题，但是循环中只要找到小的就交换一次，增加了内存占用。

实际应该为在单次循环时不进行位置交换，而是单次循环后再进行位置交换

def select_fun(list1):
    n = len(list1)
    for i in range(n-1):  # 开启循环，只需要循环n-1次即可,
        # 假设第i个值为最小值，min_value = list1[i]
        for j in range(i+1, n):  # j 输入i后面的数字
            if list1[j] < list1[i]:  # 如果发现后面存在比最小值档还小的数
                list1[i], list1[j] = list1[j], list1[i]  # 交换顺序
    return list1


if __name__ == '__main__':
    list2 = [3, 5, 6, 1, 2]
    print(select_fun(list2))
    """
    # 输出结果
    [1, 2, 3, 5, 6]
    """

1.3 这种性能良

大部分球友提交的代码实现版本：

def select_fun(list1):
    n = len(list1)
    count = 0  # 统计更改次数
    for i in range(n-1):  # 开启循环，只需要循环n-1次即可,
        min_index = i
        for j in range(i+1, n):  # j 输入i后面的数字
            if list1[j] < list1[min_index]:  # 如果发现后面存在比最小值档还小的数
                min_index = j  # 这里暂时不更改位置，等循环结束后再更改
        if min_index != i:  # 判断当前的最小值是不是i所在位置
            list1[i], list1[min_index] = list1[min_index], list1[i]
            count += 1
    print('交换次数', count)
    return list1


if __name__ == '__main__':
    list2 = [3, 5, 6, 1, 2]
    print(select_fun(list2))
    """
    # 输出结果
    交换次数 4
    [1, 2, 3, 5, 6]
    """

1.4 性能更好的实现

@Leven 打卡代码：同时找出最小值与最大值放在数列两侧，两边逐渐逼近，循环次数会减少一些。