数据结构与算法-插入排序

       插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的基本步骤如下:

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。

1. 将新元素插入到该位置。
2. 重复步骤2~5。

代码实现：

def insert_sort(li):
    for i in range(1,len(li)): #表示遍历到的下标
        tem = li[i]
        j=i-1
        while j>=0 and li[j]>tem:
            li[j+1] = li[j]  #把比tem大的数整体往右移
            j -= 1             #把箭头往左移 去左边与下一个数相比大小
        li[j+1] = tem          # 结束循环 给tem找到一个合适的位置
        print(s)
s=[1,5,6,8,7,9,4,3,2]
print(s)
insert_sort(s)
print(s)

插入排序的时间复杂度为O(n^2)。它适用于小规模数据的排序,是稳定的排序算法。

       插入排序的优点是简单、直观、易于实现。对于部分有序的数据集来说,插入排序的性能要优于其他排序算法。缺点是对于较大规模的无序数组,插入排序的效率较低。

    总的来说,插入排序是一种简单高效的排序算法,在某些场景下表现不错。它是学习和理解其他复杂排序算法的基础。