例如80567123449386597|76|132752插入38插入位置08567234138975249165132776j-i-1插入658702365412252273849657697插入52插入位置2348561227384952657697
0 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 52 j j=i-1 0 1 2 3 4 5 6 7 8 38 49 97 76 13 27 52 插入38 插入65 j=i-1 65 插入位置 插入52 0 1 2 3 4 5 6 7 8 12 27 38 49 65 76 97 52 j j=i-1 插入位置 0 1 2 3 4 5 6 7 8 12 27 38 49 52 65 76 97 例如
void InsertionSort （SqList &L）//对顺序表L作直接插入排序。for （i=2; i<-L.length; ++i)if (L.r[i].key < L.r[i-1].key) /复制为监视哨L.r[O] = L.r[i];for (j-i-l; L.r[o].key < L.r[li].key; -- j)//记录后移L.r[j+1] = L.r[i]//插入到正确位置L.r[j+1] = L.r[O]:人? // 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）“比较”序列中两个关键字的 大小；
对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：“移动"“比较"的次数：的次数：Z101=n-1i=2最坏的情况（关键字在记录序列中逆序有序）：“比较"“移动'的次数：的次数：nn(n+2)(n-1)(n +4)(n -1)(i)=2(i+1)=22i=2i=2
对于直接插入排序： 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： 1 1 2 = − = n n i 0 2 ( 4)( 1) ( 1) 2 + − + = = n n i n i “移动”的次数： “移动”的次数： 2 ( 2)( 1) ( ) 2 + − = = n n i n i
二、折半插入排序因为 R[1.i-11 是一个按关键字有序的有序序列，则可以利用折半查找实现"在R[1..i-1]中查找R[i的插入位置”，如此实现的插入排序为折半插入排序
因为 R[1.i-1] 是一个按关键字有 序的有序序列，则可以利用折半查找 实现“在R[1.i-1]中查找R[i]的插入位 置”，如此实现的插入排序为折半插 入排序。 二、折半插入排序