插入排序-最佳/平均分析

Question

关于塞奇威克教授的插入排序讲课，

我知道了，

命题：为了对具有不同键的随机排序数组进行排序，插入排序使用~(1/4 )N^2比较和~(1/4 )N^2交换。

我也知道，

最好的情况--如果数组按升序排列，插入排序将使N-1比较和零交换。

如果我分析伪码，

int n = array.length;
for(int i=0; i < n; i++){
  for(int j=i; j>0; j--){
    if(less(a[j], a[j-1]))
      swap(array, j, j-1);
    else
      break; // Is N^2/4 due to break statement?
  }
} 

问题：

所以,

由于使用break语句来避免进一步的比较，插入排序在平均情况下执行(N^2)/4比较，在最好情况下执行N-1比较。

我的理解正确吗？

Answer 1

啊，还需要更多的数学。

您是否意识到插入排序所执行的掉期数量正是输入中存在的反转次数？

倒置:索引对(i，j)是如果i<j but a[i]>a[j]的逆。

So I(i,j) = 1 if (i,j) is inversion
          = 0 if (i,J) is not an inversion

Now you have to get the expectation of this to get the average case
E[I]= Sum(E[I_{i,j}) = Sum over i and j such that i<j [(1/2)]= 1/2*nC2=n*(n-1)/2*1/2~n^2/4

Why E[I_(i,j)]=1/2?
    E[I_(i,j)]=P(I_(i,j)=1)*I_(i,j)+P(I_(i,j)=0)*I_(i,j)
              = 1/2*1+1/2*0
              = 1/2

我有多少指数？

1 2 3 4 .. n
For 1 there is 0 such indices
For 2 there is 1 such index [1]
For 3 there is 2 such index [1,2]
..
For n there is 1 such index [1,2,..n-1]
So total = 0+1+2..+n-1= n*(n-1)/2 

顺便说一句，我猜你知道this...but still.why 1+2+.n-1=n*(n-1)/2

Let the sum be S= 1+2+3+...+n-1
               S= n-1+n-2+....1
            -----------------------
              2*S= (n-1+1)+(n-2+2)...(1+n-1)
                 = n *n*n...n-1 times
                 = n*(n-1)
            So S = n*(n-1)/2