十大排序算法之-＞插入排序

一、插入排序

插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而形成一个新的、记录数增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]
"""

二、动画演示