教育部—微软精品课程建设项目 令i=2,3,…,n, 实现整个序列的排序。 for(=2; K-n;++i) if(R[i]. key<Ri-1. key) 在R[14查找R[的插入位置; 插入R[订]; 南京航空航天大学数据结构课题组版权所有
令 i = 2，3，…, n, 实现整个序列的排序。 for ( i=2; i<=n; ++i ) if (R[i].key<R[i-1].key) { 在 R[1..i-1]中查找R[i]的插入位置; 插入R[i] ; }
教育部—微软精品课程建设项 void Insertion Sort( Sqlist &l)i ∥对顺序表L作直接插入排序。 for(i-2, 1-Llength; ++i) if (L rli].key <Lr[i-1. key)& L r0=L ri ∥复制为监视哨 for(j=1-1; Lr[o]. key L rli]. key;--j) Lrj+1]=L,rj;∥记录后移 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）“比较”序列中两个关键字的 大小；
教育部—微软精品课程建设项目 对于直接插入排序 最好的情况(关键字在记录序列中顺序有序) 比较”的次数:“移动”的次数 2 最坏的情况(关键字在记录序列中逆序有序): 比较”的次数 移动”的次数 n+2(n 1) ∑(+1 n+4n-
对于直接插入排序： 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： 1 1 2 = − = n n i 0 2 ( 4)( 1) ( 1) 2 + − + = = n n i n i “移动”的次数： “移动”的次数： 2 ( 2)( 1) 2 n i n n i = + − =
教育部—微软精品课程建设项目 、折半插入排序 因为R[1.j-1是一个按关键字有 序的有序序列,则可以利用折半查找 实现“在R1-1中查找R[的插入位 置”,如此实现的插入排序为折半插 入排序。 南京航空航天大学数据结构课题组版权所有
因为 R[1..i-1] 是一个按关键字有 序的有序序列，则可以利用折半查找 实现“在R[1..i-1]中查找R[i]的插入位 置”，如此实现的插入排序为折半插 入排序。 二、折半插入排序