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