1.从Ri-1起向前进行顺序查找， R[1] j+1 R[i门 R[O] 插入位置 R[0]=R[1]; ∥设置“监视哨” for (j=i-1;R[0].key<R[j].key;-j); /∥从后往前找第一个小于等于关键字RIO.ky的记录的位置i 循环结束后R]的插入位置为i+1
1. 从R[i-1]起向前进行顺序查找， R[0] = R[i]; // 设置“监视哨” 循环结束后R[i]的插入位置为 j +1 R[0] j R[ i] for (j=i-1; R[0].key≤R[j].key; -j); // 从后往前找第一个小于等于关键字R[0].key的记录的位置j 插入位置j=i-1 j+1 R[1]
2.对于在查找过程中找到的那些关键 3.字大于R[i]key的记录，在查找的 同时实现记录向后移动； forG=i-1;R[0].key≤Rj]key,-j)； R[j+1]=R[j] R[O] j+1R[的 插入位置 3.上述循环结束后可以直接进行插入
2. 对于在查找过程中找到的那些关键 3. 字大于R[i].key的记录，在查找的 同时实现记录向后移动； for (j=i-1; R[0].key ≤ R[j].key; -j); R[j+1] = R[j] R[0] j j= i-1 3. 上述循环结束后可以直接进行“插入” 插入位置 j+1 R[i]
4.令i=2,3,.,n, 实现整个序列的排序。 for i=2;i<-n;++i) if (R[i].key<R[i-1].key) {在R[1.i-1]中查找R[的插入位置； 插入R[;
4. 令 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 InsertionSort SqList &L) ∥对顺序表L作直接插入排序。 for i=2;i<=L.length;++i) if (L.r[i].key L.r[i-1].key){ L.r[0]=L.r[] 川复制为监视哨 for j=i-1;L.r[o].key L.r[j].key;-j) L.r[j+1]=L.r[];∥记录后移 L.r[ij+1]=L.[0] ∥插入到正确位置 //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]; // 插入到正确位置
二、折半插入排序 因为R[1.i-1]是一个按关键字有 序的有序序列，则可以利用折半查找 实现“在R[1.i-1]中查找R[]的插入位 置”，如此实现的插入排序为折半插 入排序
因为 R[1.i-1] 是一个按关键字有 序的有序序列，则可以利用折半查找 实现“在R[1.i-1]中查找R[i]的插入位 置”，如此实现的插入排序为折半插 入排序。 二、折半插入排序