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

Question

在引用Sedgewick教授的插入插入演讲中，

我学会了，

命题：要分类一个带有不同键的随机排序数组，插入排序使用〜（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?
  }
} 

问题：

so，

由于break的语句避免了进一步的比较，在最好的情况下，插入排序在平均情况和N-1比较中进行（N^2）/4比较。

。

我的理解正确吗？

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 

顺便说一句，我想你知道这一点...但是仍然是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