插入排序的反转！

Question

这是我在维基百科网站上找到的一个问题（我想很好地学习排序算法）。无论如何，这是一个问题 - 你能向我解释一下如何展示它吗？

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

Answer 1

查看本页的Implementation和部分。Analysis

考虑那里提出的算法：

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]是 element 引起的反转次数i。这应该会使那里的证明非常容易理解。