一、插入排序
插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而形成一个新的、记录数增1的有序表。
排序过程：
1、外层循环：从第二个元素开始，依次选取未排序的元素。
2、内层循环：将当前选取的元素与已排序序列中的元素从后往前进行比较，找到合适的插入位置，并将比它大的元素向后移动一位，为新元素的插入腾出空间。
3、插入操作：将当前元素插入到找到的位置上，完成一次插入操作。
插入排序的时间复杂度在最好情况下是O(N)，在平均和最坏情况下是O(N^2)，其中N是列表的长度
# -*- coding: utf-8 -*-
"""
======================================
File Name ：insertion_sort.py
Author ：lanmingyong
date ：2024/4/19 17:04
Description：
插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而形成一个新的、记录数增1的有序表。它通过双层循环来实现排序过程：
外层循环：从第二个元素开始，依次选取未排序的元素。
内层循环：将当前选取的元素与已排序序列中的元素从后往前进行比较，找到合适的插入位置，并将比它大的元素向后移动一位，为新元素的插入腾出空间。
插入操作：将当前元素插入到找到的位置上，完成一次插入操作。
插入排序的时间复杂度在最好情况下是O(N)，在平均和最坏情况下是O(N^2)，其中N是列表的长度
=======================================
"""
def insertion(arr):
for i in range(1, len(arr)):
index = i
for j in list(range(i))[::-1]:
if arr[index] < arr[j]:
arr[index], arr[j] = arr[j], arr[index]
index = j
if arr[index] > arr[j]:
break
print(arr)
arr = [9, 6, 7, 2, 8, 1, 0, 4]
insertion(arr)
#执行输出
"""
[6, 9, 7, 2, 8, 1, 0, 4]
[6, 7, 9, 2, 8, 1, 0, 4]
[6, 7, 2, 9, 8, 1, 0, 4]
[6, 2, 7, 9, 8, 1, 0, 4]
[2, 6, 7, 9, 8, 1, 0, 4]
[2, 6, 7, 8, 9, 1, 0, 4]
[2, 6, 7, 8, 1, 9, 0, 4]
[2, 6, 7, 1, 8, 9, 0, 4]
[2, 6, 1, 7, 8, 9, 0, 4]
[2, 1, 6, 7, 8, 9, 0, 4]
[1, 2, 6, 7, 8, 9, 0, 4]
[1, 2, 6, 7, 8, 0, 9, 4]
[1, 2, 6, 7, 0, 8, 9, 4]
[1, 2, 6, 0, 7, 8, 9, 4]
[1, 2, 0, 6, 7, 8, 9, 4]
[1, 0, 2, 6, 7, 8, 9, 4]
[0, 1, 2, 6, 7, 8, 9, 4]
[0, 1, 2, 6, 7, 8, 4, 9]
[0, 1, 2, 6, 7, 4, 8, 9]
[0, 1, 2, 6, 4, 7, 8, 9]
[0, 1, 2, 4, 6, 7, 8, 9]
"""二、动画演示
欢迎大家关注我的订阅号，会定期分享一些关于测试相关的文章，有问题也欢迎一起讨论学习！