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