binary insertion sort 复杂度问题

homme1986

public static void binaryInsertionSort( int[] a ) {
  for ( int i = 1; i != a.length; i += 1 ) {
    int t = a[ i ];
    if ( t < a[ i - 1 ] ) {
      int p = binarySearch( t, a, i - 1 );
      for ( int j = i - 1; j >= p; i -= 1 ) {
        a[ j + 1 ] = a[ j ];
      }
    a[ p ] = t;
    }
  }
}

改进的insertion sort， 为什么它的average/worst-case时间复杂度和普通的insertion sort一样都是O(n^2)？它的worst-case比较次数是O(nlogn)又是怎么推出来的? 欢迎熟悉算法的朋友说明下，提供资料也行。cheers

mcemil

你知道O()是什么意思吗，O(nlogn)  log是以几为底吗？
就好比压根没做爱过，却硬要问别人哪种姿势最舒服