算法概述 插入排序(Insertion sort)是一种简单直观且稳定的排序算法。 将数组的第一个数认为是有序数组,从后往前(从前往后)扫描该有序数组,把数组中其余n-1个数,根据数值的大小,插入到有序数组中,直至数组中的所有数有序排列为止。这样的话,n个元素需要进行n-1趟排序! 主要参数 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性 O(n2) O(n) O(n2) O(1) In-place 稳定 演示动画 作者:馒头老爸