冒泡排序

介绍：

原理:
        相邻元素两两比较, 大的往后走, 这样第一轮比较完毕后, 最大值就在最大索引处.
        重复此动作, 直至排序完成.
    流程: 假设共 5 个元素
           第几轮(索引)         该轮比较的总次数         公式
            第1轮(0):            4次               5 - 1 - 0 = 4
            第2轮(1):            3次               5 - 1 - 1 = 3
            第3轮(2):            2次               5 - 1 - 2 = 2
            第4轮(3):            1次               5 - 1 - 3 = 1
    要点:
       1. 比较的总轮数.        列表长度 - 1
       2. 每轮比较的总次数.     列表长度 - 1 - 轮数的索引(从0开始)
       3. 谁和谁比较.          索引j 和 j + 1位置的元素比较
    时间复杂度:
        最优: O(n)
        最坏: O(n²)
    扩展:
        冒泡排序 = 稳定 排序算法
    扩展:
        外循环的 -1 是什么意思: 减少比较的轮数, 提高效率.
        内循环的 -1 是什么意思: 为了防止索引 越界.
        内循环的 -i 是什么意思: 减少每轮比较的次数, 提高效率

# 1. 定义函数 bubble_sort(my_list), 表示: 冒泡排序.
def bubble_sort(my_list):  # 形参接收可变类型, 则: 形参的改变直接影响实参.
    # 1.1 获取列表的长度.
    n = len(my_list)  # 假设 n = 5
    # 1.2 外循环, 控制比较的: 轮数
    for i in range(n - 1):  # i的值: 0, 1, 2, 3
        # 细节1: 定义变量, 记录具体的交换次数.
        count = 0

        # 1.3 内循环, 控制比较的: (每轮比较的)总次数
        for j in range(n - 1 - i):
            # 1.4 具体的比较过程, 即: 索引j 和 j + 1位置的元素比较, 大的往后走.
            if my_list[j] > my_list[j + 1]:
                # 细节2: 走这里, 说明发生了交换.
                count += 1

                # 1.5 具体的交换过程, a, b = b, a
                my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]

        # 细节3: 打印每轮的交换次数.
        print(f'第 {i + 1} 轮交换了{count}次')

        # 细节4: 判断如果本轮没有发生交换, 说明已经是拍完序的, 结束即可.
        if count == 0:
            break


# 2. 测试
if __name__ == '__main__':
    # 2.1 定义列表, 记录要排序的元素.
    # my_list = [5, 3, 6, 7, 2]
    my_list = [3, 2, 5, 7, 6, 6]
    # 2.2 调用函数 bubble_sort(my_list), 进行排序.
    bubble_sort(my_list)  # 实参, 可变
    # 2.3 打印结果.
    print(my_list)

选择排序

介绍：

案例: 演示选择排序.

选择排序介绍:
    原理:
        每轮都假设该轮最前边的那个元素为最小值, 然后去 剩下的元素列表中找真正的最小值, 最终交换即可, 本轮就找到了 本轮的最小值, 重复即可.
    大白话:
        第1轮, 假设 i = 0位置的元素是最小值, 然后用min_index记录住它的索引, 然后去剩下所有元素中找真正的最小值, 找到后就用min_index做记录, 最终判断i 和 min_index是否交换,
        第1轮完毕后, 最小值就在最小索引处.
        重复该步骤, 直至排序完成.
    流程: 假设共 5 个元素
           第几轮(索引)         该轮比较的总次数         公式(具体的谁和谁比较)
            第1轮(0):            4次                    索引0和 1,2,3,4比较
            第2轮(1):            3次                    索引1和 2,3,4比较
            第3轮(2):            2次                    索引2和 3,4比较
            第4轮(3):            1次                    索引3和 4比较
    要点:
       1. 比较的总轮数.        列表长度 - 1
       2. 每轮比较的总次数.     i+1 ~ n
       3. 谁和谁比较.          索引min_index(初值为i) 和 索引j比较,  索引i 和 索引min_index的值交换
    时间复杂度:
        最优: O(n²)
        最坏: O(n²)
    扩展:
        选择排序 = 不稳定 排序算法
    扩展:
        外循环的 -1 是什么意思: 减少比较的轮数, 提高效率.

# 1. 定义函数select_sort(my_list), 表示: 选择排序.
def select_sort(my_list):   # 形参接收可变类型, 则: 形参的改变直接影响实参.
    # 1. 获取列表长度.
    n = len(my_list)
    # 2. 外循环, 控制比较的: 轮数.
    for i in range(n - 1):
        # 3. 定义变量min_index, 记录住 本轮真正最小值的索引.
        min_index = i
        # 4. 内循环, 控制每轮比较的: 次数.
        for j in range(i + 1, n):
            # 5. 具体的比较过程 索引min_index(初值为i) 和 索引j比较
            if my_list[j] < my_list[min_index]:
                min_index = j   # 记录最小值的索引
        # 6. 都到这里, 说明本轮已经找到了最小值, 判断, 并交换.
        if min_index != i:
            my_list[min_index], my_list[i] = my_list[i], my_list[min_index]


# 2. 测试
if __name__ == '__main__':
    # 2.1 定义列表, 记录要排序的元素.
    # my_list = [5, 3, 6, 7, 2]
    my_list = [2, 3, 5, 6, 7]
    # 2.2 调用函数select_sort(my_list), 进行排序.
    select_sort(my_list)    # 实参, 可变
    # 2.3 打印结果.
    print(my_list)

插入排序

插入排序介绍:
    原理:
       把列表分成两部分, 假设第1个元素是有序的, 剩下的元素是无序的, 每次都从无序列表中获取1个元素, 和它前边所有元素比较, 决定它的位置, 进行插入.
       直至无序列表的元素操作完毕, 剩下的列表就是: 有序的.

    流程: 假设共 5 个元素
           第几轮(索引)         该轮比较的总次数         公式(具体的谁和谁比较)
            第1轮(1):            1次                    索引1和 0比较
            第2轮(2):            2次                    索引2和1, 2和0比较
            第3轮(3):            3次                    索引3和2, 3和1, 3和0比较
            第4轮(4):            4次                    索引4和3, 4和2, 4和1, 4和0比较
    要点:
       1. 比较的总轮数.        列表长度 - 1       range(1, n)
       2. 每轮比较的总次数.     range(i, 0, -1)
       3. 谁和谁比较.          索引j 和 j - 1 位置的元素比较
    时间复杂度:
        最优: O(n)
        最坏: O(n²)
    扩展:
        插入排序 = 稳定 排序算法

# 1. 定义函数 insert_sort(my_list), 表示: 插入排序.
def insert_sort(my_list):   # 形参接收可变类型, 则: 形参的改变直接影响实参.
    # 1. 获取列表长度.
    n = len(my_list)        # 假设列表长度为 5
    # 2. 外循环, 控制: 比较的轮数.
    for i in range(1, n):                       # i的值:  1,  2,      3,      4
        # 3. 内循环, 控制: 每轮比较的总次数.
        for j in range(i, 0, -1):               # j的值:  1   2,1     3,2,1   4,3,2,1
            # 4. 具体的比较过程, 如果 j < j -1 的元素, 就交换.
            if my_list[j] < my_list[j - 1]:     # j-1的值:0   1,0     2,1,0   3,2,1,0
                my_list[j], my_list[j - 1] = my_list[j - 1], my_list[j]
            else:
                # 5. 走到这里, 说明元素找到了自己的位置, break即可.
                break


# 2. 测试
if __name__ == '__main__':
    # 2.1 定义列表, 记录要排序的元素.
    my_list = [5, 3, 6, 7, 2]
    # 2.2 调用函数 insert_sort(my_list), 进行排序.
    insert_sort(my_list)    # 实参, 可变
    # 2.3 打印结果.
    print(my_list)