✨博客主页：王乐予🎈
✨年轻人要：Living for the moment（活在当下）！💪
🏆推荐专栏：【图像处理】【千锤百炼Python】【深度学习】【排序算法】

简单插入排序是排序算法系列的第五个要介绍的算法！

简单插入排序既属于比较类排序也属于内部排序。

😺一、算法原理

🐶1.1 算法原理

插入排序（Insertion Sort）是一种简单直观的排序算法，属于插入排序的一种。

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

🐶1.2 算法步骤

• 步骤一：从序列的第一个元素开始，将该元素视为已被排序的序列（目前该序列中仅包含一个元素）；
• 步骤二：从未排序序列中取出下一个元素，在已排序序列的元素中从后向前扫描；
• 步骤三：若待排序元素小于已排序序列中正在比较的元素，则将待排序元素继续前移；
• 步骤四：重复步骤三，直至从已排序元素中找到<=新元素的位置，并将新元素置于其后；
• 步骤五：重复上述步骤，直至所有元素排序完毕。

😺二、动图演示

😺三、程序实现

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    sort = insertionSort(arr)
    print(sort)

输出结果为：

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

【千锤百炼Python—11】：十大排序算法总结（动画+代码）