前言📢📢

Python每日一练来啦，本文已收录于：《Python每日一练》专栏

此专栏目的在于，帮忙学习Python的小白提高编程能力，训练逻辑思维，每周持续更新中，欢迎免费订阅！！！

---

---

1. 算法描述

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2. 算法分析

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

3. 动图展示

看明白了运行流程，我们再来看看动图实现：

4. 代码实现

实现代码📝：

import random

# random库随机生成列表
sec_list = [random.randint(1, 100) for i in range(8)]
# 获取当前列表长度
length = len(sec_list)
print("未排序的列表：" % sec_list)
# 外层循环
for i in range(length - 1):
    min_index = i
    # 内层循环从认为最小的那个数后一位开始，一直到结束
    for j in range(i + 1, length):
        # 如果最小的元素大于后面的元素
        if sec_list[min_index] > sec_list[j]:
            # 重新赋值最小元素
            min_index = j
    # 当内层循环执行一整轮后交换位置
    sec_list[min_index], sec_list[i] = sec_list[i], sec_list[min_index]
    print("第%s轮排好序的是：%s" % (i + 1, sec_list))
print("最终排好序的结果为：%s" % sec_list)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

运行结果👇：

5. 时间复杂度分析

• 最优时间复杂度：O(n2)
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定（考虑升序每次选择最大的情况）
  
  
• 选择排序与冒泡排序一样，需要进行N*(N-1)/2次比较，但是只需要N次交换，当N很大时，交换次数的时间影响力更大，所以选择排序的时间复杂度为O(N^2)。
  
  
• 虽然选择排序与冒泡排序在时间复杂度属于同一量级，但是毫无疑问选择排序的效率更高，因为它的交换操作次数更少，而且在交换操作比比较操作的时间级大得多时，选择排序的速度是相当快的。

6. 如何让刷题变得更加高效呢？

1. 编程小白选手

很多刚入门编程的小白学习了基础语法，却不知道语法的用途，不知道如何加深映像，不知道如何提升自己，这个时候每天刷自主刷一道题就非常重要（百炼成神），可以去牛客网上的编程初学者入门训练。该专题为编程入门级别，适合刚学完语法的小白练习，题目涉及编程基础语法，基本结构等，每道题带有练习模式和考试模式，可还原考试模式进行模拟，也可通过练习模式进行练习。

链接地址：牛客网 | 编程初学者入门训练

2. 编程进阶选手

当基础练习完已经逐步掌握了各知识要点后，这个时候去专项练习中学习数据结构、算法基础、计算机基础等。先从简单的入手，感觉上来了再做中等难度，以及较难的题目。这三样是面试中必考的知识点，我们只有坚持每日自己去多加练习，拒绝平躺持续刷题，不断提升自己才能冲击令人满意的公司。

链接地址：牛客网 | 专项练习

速度上号，大家一起冲击大厂，有疑问评论区留言解答！！！