插入排序的反转！

Question

这是我在 Wikipedia 站点中发现的问题（我想很好地学习排序算法）。无论如何，这是一个问题 - 你能向我解释一下如何展示它吗？

练习：假设 I 是数组 A 中的反转次数，则证明算法插入排序 (A) 的运行时间为 O(n + I)。

Answer 1

查看 此页面。

考虑此处介绍的算法：

private static void insertionsort()
{
    int i, j, t;
    for (i=1; i<n; i++)
    {
        j=i;
        t=a[j];
        while (j>0 && a[j-1]>t)
        {
            a[j]=a[j-1];
            j--;
        }
        a[j]=t;
    }
}

请注意，while 循环运行 v[i] 次迭代，其中 v[i] 是由元素 i 引起的反转次数。这应该会使那里的证明非常容易理解。