」最坏情况下,第i趟时第个对象必须与前面 i个对象都做排序码比较,并且每做1次比较 就要做1次数据移动。则总排序码比较次数 KCN和对象移动次数RMN分别为 KCN=∑i=m(n-1)/2≈n2/2 RMN=∑(i+2)=(n+4)n-1)/2≈n2/2 在平均情况下的排序码比较次数和对象移动 次数约为m4。因此,直接插入排序的时间 复杂度为o(m2) a直接插入排序是一种稳定的排序方法
1 1 1 1 2 4 1 2 2 1 2 2 n i n i RMN i n n n KCN i n n n ( ) ( )( ) / / ( ) / / , 2 2
折半插入排序 Binary Insertsort 」基本思想是:设在顺序表中有一个对象序列 VI0,V[1],Vm-1]。其中,V|0],Ⅵ1] V1是已经排好序的对象。在插入Ⅴ团时, 利用折半搜索法寻找V团的插入位置。 折半插入排序的算法 template <class Type> void dataList<Type>: BinerylnsSort(t Element<Type> temp; int Left, Right for( int i=l; i< CurrentSize; 1++i Left=0; Right=1-1; temp= Vector[i];
template <class Type> void dataList<Type> :: BineryInsSort ( ) { Element<Type> temp; int Left, Right; for ( int i = 1; i < CurrentSize; i++) { Left = 0; Right = i-1; temp = Vector[i];
while( Left<- Right i int middle=( Left Right )/2 if( temp< Vector middle) Right- middle-1 else left= middle +1 for( int k=1-1; k>= Left; k-- Vector k+1- Vector k; Vector Left]=temp 算法分析
while ( Left <= Right ) { int middle = ( Left + Right )/2; if ( temp < Vector[middle] ) Right = middle - 1; else Left = middle + 1; } for ( int k = i-1; k >= Left; k-- ) Vector[k+1] = Vector[k]; Vector[Left] = temp; } 算法分析
」折半搜索比顺序搜索查找快,所以折半插入 排序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序 列的初始排列无关,仅依赖于对象个数。在 插入第个对象时需要经过L小+1次排 序码比较,才能确定它应插入的位置。因此, 将m个对象(为推导方便,设为=2k)用折半 插入排序所进行的排序码比较次数为: ∑log2l+1)≈nlg2n 折半插入排序是一个稳定的排序方法
1 1 2 2 log 1 log n i i n n
」当m较大时,总排序码比较次数比直接插入 排序的最坏情况要好得多,但比其最好情况 要差。 在对象的初始排列已经按排序码排好序或 接近有序时,直接插入排序比折半插入排序 执行的排序码比较次数要少。折半插入排 序的对象移动次数与直接插入排序相同,依 赖于对象的初始排列