最坏情况下,第i趟时第i个对象必须与前 面i个对象都做排序码比较,并且每做1次 比较就要做1次数据移动。则总排序码比较 次数KCN和对象移动次数RMN分别为 KCN=∑i=m(n-1)/2≈n2/2 RMM ∑(+2)=(n+4)n-1)/2≈n2/2 在平均情况下的排序码比较次数和对象移 动次数约为n214。因此,直接插入排序的 时间复杂度为0(m2) 直接插入排序是一种稳定的排序方法
◼ 最坏情况下, 第 i 趟时第 i 个对象必须与前 面 i 个对象都做排序码比较, 并且每做1次 比较就要做1次数据移动。则总排序码比较 次数KCN和对象移动次数RMN分别为 ◼ 在平均情况下的排序码比较次数和对象移 动次数约为 n 2 /4。因此，直接插入排序的 时间复杂度为 o(n2 )。 ◼ 直接插入排序是一种稳定的排序方法。 − = − = = + = + − = = − 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) 基本思想设在顺序表中有一个对象序列v0l VI1,…,Ⅴn-1l。其中,V0l,V[1I,…,Vi-1是 已经排好序的对象。在插入V时,利用折半 搜索法寻找V[的插入位置。 折半插入排序的算法
折半插入排序 (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 VI, int n)i SortData temp; int Left, Right; for(int i=1; i< n; i++)i Left=0; Right=i-1; temp=V]; while( left < right)t int mid=( Left Right 2; if( temp < vimid]) right=mid-1 else left mid +1 for(int k=i-l; k>= Left; k--)V[k+1=vk]; / 记录后移 VLLeft=temp;插入
typedef int SortData; void BinInsSort ( SortData V[ ], int n ) { SortData temp; int Left, Right; 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; //插入 } }
折半插入排序 234 5 temp 21 5 0 2 4 5 temp i=2 5 3 i=3⑤ i=46②⑤20 i=5@6②0 ③④0(6
折半插入排序 0 1 2 3 4 5 temp i = 1 i = 2 0 1 2 3 4 5 temp 5 21 3 3 i = 3 5 5 3 5 21 21 4 4 i = 4 3 5 21 8 8 i = 5 3 5 8 21 16 16 4 4 3 4 5 8 16 21
算法分析 折半搜索比顺序搜索查找快,所以折半插入 排序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序 列的初始排列无关,仅依赖于对象个数。在 插入第个对象时,需要经过Llog2+1次排 序码比较,才能确定它应插入的位置。因此, 将n个对象(为推导方便设为n=2k)用折半 插入排序所进行的排序码比较次数为: ∑d0g21+1)≈nlg2n
◼ 折半搜索比顺序搜索查找快, 所以折半插入 排序就平均性能来说比直接插入排序要快。 ◼ 它所需的排序码比较次数与待排序对象序 列的初始排列无关, 仅依赖于对象个数。在 插入第 i 个对象时, 需要经过 log2 i +1 次排 序码比较, 才能确定它应插入的位置。因此, 将 n 个对象(为推导方便, 设为 n=2k )用折半 插入排序所进行的排序码比较次数为： ( ) − = + 1 1 2 2 log 1 log n i i n n 算法分析