插入排序 #

当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。我们需要将其余所有元素在插入之前都向右移 动一位。

复杂度 #

当数组已经有序的时候，比较 N - 1 次，交换 0 次。

当数组完全倒序是，比较 N^2 / 2 次，交换 N^2 / 2 次。

平均情况下，比较 N^2 / 4 次，交换 N^2 / 4 次。

时间复杂度：O(N^2)

特点 #

• 对于非随机数组（比如已经有序的数组、所有值都相同的数组），运行时间是线性的（相比选择排序：平方级别）
• 对于部分有序的数组，这种算法最有效
  • 如果数组中倒置的数量小于数组大小的某个倍数，那么我们说这个数组是部分有序的。倒置指的是数组中的两个顺序颠倒的元素。
  • 比如：
    • 数组中每个元素距离它的最终位置都不远；
    • 一个有序的大数组接一个小数组；
    • 数组中只有几个元素的位置不正确；

代码 #