最好情况下,排序前对象已经按关键码大小 从小到大有序,每趟只需与前面的有序对象 序列的最后一个对象的关键码比较1次,移 动2次对象,总的关键码比较次数为n-1,对 象移动次数为2(n-1)。 ■最坏情况下,第i趟时第i个对象必须与前面 i个对象都做关键码比较,并且每做1次比较 就要做1次数据移动。则总的关键码比较次 数KCN和对象移动次数RMN分别为 KCN=∑i=m(n-1)/2≈n2/2, i=1 RMN=∑(i+2)=(n+4)n-1)/2≈n2/2
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
若待排序对象序列中出现各种可能排列的概 率相同,则可取上述最好情况和最坏情况的 平均情况。在平均情况下的关键码比较次数 和对象移动次数约为m2/4。因此,直接插入 排序的时间复杂度为0(n2)。 直接插入排序是一种稳定的排序方法
折半插入排序( Binary Insertsort) 折半插入排序基本思想是:设在顺序表中有 个对象序列V10,V1…v{n-1l。其中,v0l, V1],…1]是已经排好序的对象。在插入 v引时,利用折半搜索法寻找v的插入位置。 折半插入排序的算法 template <class Type> void BinaryInsertSort( datalist<Type>& list( for (int i=l; i< list. CurrentSize; i++) BinaryInsert( list, i );
template <class Type> void BinaryInsertSort ( datalist<Type> & list ) { for ( int i = 1; i < list.CurrentSize; i++) BinaryInsert ( list, i ); }
template <class Type> void BinaryInsert( datalist<Type> list, int i)& int left=0, Right=i-1; Element<Type> temp= list. Vector[i]; while( left < right)( int middle=( left Right )/2; if temp getKey o< list. Vector[middle].getKeyo) Right=middle- 1; else left= middle+ 1 for(int k=i-l; k>=left; k--) list. Vector[k+1]=list. Vector[k];
template <class Type> void BinaryInsert ( datalist<Type> & list, int i ) { int left = 0, Right = i-1; Element<Type> temp = list.Vector[i]; while ( left <= Right ) { int middle = ( left + Right )/2; if ( temp.getKey ( ) < list.Vector[middle].getKey ( ) ) Right = middle - 1; else left = middle + 1; } for ( int k = i-1; k >= left; k-- ) list.Vector[k+1] = list.Vector[k];
list. VectorLleft= temps 算法分析 对分查找比顺序查找快,所以对分插入排序 就平均性能来说比直接插入排序要快。 它所需要的关键码比较次数与待排序对象序 列的初始排列无关,仅依赖于对象个数。在 插入第i个对象时,需要经过Logi+1次关 键码比较,才能确定它应插入的位置。因此, 将n个对象(为推导方便,设为n=2k)用对分 插入排序所进行的关键码比较次数为
list.Vector[left] = temp; }