Vector] =temp 算法分析 排序码比较次数和对象移动次数与对象排序 码的初始排列有关。 最好情况下,排序前对象已按排序码从小到 大有序,每一个对象比较1次,移动次对象, 总的排序码比较次数为n-1,对象移动次数为 2(n-1)
算法分析 ◼ 排序码比较次数和对象移动次数与对象排序 码的初始排列有关。 ◼ 最好情况下, 排序前对象已按排序码从小到 大有序, 每一个对象比较1次, 移动2次对象, 总的排序码比较次数为n-1, 对象移动次数为 2(n-1) 。 Vector[j] = temp; } } }
最坏情况下,总排序码比较次数KCN和对象 移动次数RMN分别为 KCN=∑i=m(n-1)/2≈n2/2 i=1 RMN=∑(i+2)=(n+4)n-1)/2≈n2/2 i=1 a平均情况下排序的时间复杂度为O(m2) 直接插入排序是一种稳定的排序方法
◼ 最坏情况下, 总排序码比较次数KCN和对象 移动次数RMN分别为 ◼ 平均情况下排序的时间复杂度为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
2折半插入排序 Binary Insertsort) 基本思想是:设在顺序表中有一个对象序列 vI0VI1,…,Vn-1]l其中,v0l,V[1,…, V[i-1是已经排好序的对象。在插入V引时, 利用折半搜索法寻找v的插入位置。 折半插入排序的算法 template <class Type> void datalist<Type>: Binerylns Sortor Element<Type> temp; int Left, Right; for int i=1; 1< CurrentSize; 1++i Left=0; right=1-1; temp= Vectorj];
2.折半插入排序 (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 )& 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; }
算法分析 折半搜索比顺序搜索查找快,所以折半插入排 序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序列 的初始排列无关仅依赖于对象个数。在插入 第讠个对象时需要经过Logi+1次排序码比 较,才能确定它应插入的位置。因此将n个 对象为推导方便,设为m=2)用折半插入排序 所进行的排序码比较次数为: og2+1)≈nog2n 折半插入排序是一个稳定的排序方法
◼ 折半搜索比顺序搜索查找快, 所以折半插入排 序就平均性能来说比直接插入排序要快。 ◼ 它所需的排序码比较次数与待排序对象序列 的初始排列无关, 仅依赖于对象个数。在插入 第 i 个对象时, 需要经过 log2 i +1 次排序码比 较, 才能确定它应插入的位置。因此, 将 n 个 对象(为推导方便, 设为 n=2k )用折半插入排序 所进行的排序码比较次数为： ◼ 折半插入排序是一个稳定的排序方法。 ( ) − = + 1 1 2 2 log 1 log n i i n n 算法分析