algorithm - 插入排序的反转！

Question

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

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

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。这应该使那里的证明很容易理解。