算法分析 设待排序对象个数为n,则该算法的主程序 执行n-1趟。 排序码比较次数和对象移动次数与对象排 序码的初始排列有关。 最好情况下,排序前对象已按排序码从小 到大有序,每趟只需与前面有序对象序列 的最后一个对象比较次移动次对象,总 的排序码比较次数为n-1,对象移动次数为 2(n-1)
11 算法分析 ◼ 设待排序对象个数为 n, 则该算法的主程序 执行n-1趟。 ◼ 排序码比较次数和对象移动次数与对象排 序码的初始排列有关。 ◼ 最好情况下, 排序前对象已按排序码从小 到大有序, 每趟只需与前面有序对象序列 的最后一个对象比较1次, 移动2次对象, 总 的排序 码比较次数为 n-1, 对象移动次数为 2(n-1)
最坏情况下,第i趟时第i个对象必须与前 面i个对象都做排序码比较,并且每做1次 比较就要做1次数据移动。则总排序码比较 次数KCN和对象移动次数RMN分别为 KCN=∑i=m(n-1)/2≈n2/2 RMN=∑(i+2)=(n+4n-1)/2≈n2/2 在平均情况下的排序码比较次数和对象移 动次数约为n2/4。因此,直接插入排序的 时间复杂度为0(n2) 直接插入排序是一种稳定的排序方法。 12
12 ◼ 最坏情况下, 第 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[1l,…,Vn-1l。其中,V0J,l,…, V[i-1是已经排好序的对象。在插入v时, 利用折半搜索法寻找Ⅴ的插入位置。 折半插入排序的算法 typedef int SortData; void BinInsSort( SortData VI, int n)t SortData temp; int Left, Right; 13
13 折半插入排序 (Binary Insertsort) ◼ 基本思想 : 设在顺序表中有一 个对象序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的对象。在插入V[i] 时, 利用折半搜索法寻找V[i] 的插入位置。 折半插入排序的算法 typedef int SortData; void BinInsSort ( SortData V[ ], int n ) { SortData temp; int Left, Right;
for(int i-1; i<n; 1++)i Left=0; Right=i-1; temp=V[; while( Left <- Right )& int mid=( Left+ Right )/2; if( temp <Mid)Right=mid-1; else left mid +1 for( int k=1-1; k>= Left; k--) V[k+1]=V[k] VILeftl-- temp;
14 for ( int i = 1; i < n; i++) { Left = 0; Right = i-1; temp = V[i]; while ( Left <= Right ) { int mid = ( Left + Right )/2; if ( temp < V[mid] ) Right = mid - 1; else Left = mid + 1; } for ( int k = i-1; k >= Left; k-- ) V[k+1] = V[k]; V[Left] = temp; } }
算法分析 折半搜索比顺序搜索查找快,所以折半插入 排序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序 列的初始排列无关,仅依赖于对象个数。在 插入第i个对象时,需要经过Log+1次排 序码比较,才能确定它应插入的位置。因此 将n个对象为推导方便,设为n=k)用折半 插入排序所进行的排序码比较次数为 ∑d0g2l+1)≈nlg2n 15
15 ◼ 折半搜索比顺序搜索查找快, 所以折半插入 排序就平均性能来说比直接插入排序要快。 ◼ 它所需的排序码比较次数与待排序对象序 列的初始排列无关, 仅依赖于对象个数。在 插入第 i 个对象时, 需要经过 log2 i +1 次排 序码比较, 才能确定它应插入的位置。因此, 将 n 个对象(为推导方便, 设为 n=2k )用折半 插入排序所进行的排序码比较次数为： ( ) − = + 1 1 2 2 log 1 log n i i n n 算法分析