void InsertionSort( SqList &l( ∥对顺序表L作直接插入排序。 for (i-2; K-L length;++1) if L r[i]. key <L ri-1.key)i L r0=L ri ∥复制为监视哨 for(j=1-1; L r[O key <L rli]. key; --j) Lr[i+1]=Lri;∥记录后移 Lr+1]=Lr[0;∥插入到正确位置 3//Insertsort
void InsertionSort ( SqList &L ) { // 对顺序表 L 作直接插入排序。 for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) { } } // InsertSort L.r[0] = L.r[i]; // 复制为监视哨 for ( j=i-1; L.r[0].key < L.r[j].key; -- j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置
内部排序的时间分析 实现内部排序的基本操作有两个 (1)“比较”序列中两个关键字的 大小; (2)“移动”记录
内部排序的时间分析： 实现内部排序的基本操作有两个： （2）“移动”记录。 （1）“比较”序列中两个关键字的 大小；
对于直接插入排序 最好的情况(关鍵字在记录序列中顺序有序) 比较”的次数:“移动”的次数 最坏的情况(关鍵字在记录序列中逆序有序): 比较”的次数:“移动”的次数 (+1)= (n+4)(n ∑(+ (n+4)(n-1) L-光了Lf
对于直接插入排序： 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： 1 1 2 = − = n n i 0 2 ( 4)( 1) ( 1) 2 + − + = = n n i n i “移动”的次数： “移动”的次数： 2 ( 4)( 1) ( 1) 2 + − + = = n n i n i
、折半插入排序 因为R[1.}-1是一个按关键字有 序的有序序列,则可以利用折半查找 实现“在R1-1中查找R[i的插入位 置”,如此实现的插入排序为折半插 入排序
因为 R[1..i-1] 是一个按关键字有 序的有序序列，则可以利用折半查找 实现“在R[1..i-1]中查找R[i]的插入位 置”，如此实现的插入排序为折半插 入排序。 二、折半插入排序
void BilnsertionSort( Sqlist &l)& for(i=2; 1<=L length;++1) Lr0]=Lrij;∥将Lr[暂存到Lr 在Lr[11中折半查找插入位置 for(j=i-1; j>=high+1; --j) Lr+1]=Lr[i;∥记录后移 L rhigh+1]=Lr0];∥插入 }∥for 3// BInsertsort u LoU 232
void BiInsertionSort ( SqList &L ) { } // BInsertSort 在 L.r[1..i-1]中折半查找插入位置； for ( i=2; i<=L.length; ++i ) { } // for L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] for ( j=i-1; j>=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入