10.2.1直接插入排序 算法描述 初值：待记录放在无序部分的数组r[1.n中。 1)在有序部分中有1个元素r[1,无序部分元素为r[2.n; 2)令i=2,将r[2]作为排序元素； 3)把r[2]放到r[0]中，r[0]即作为暂存单元，又可作为后面 循环比较用的“监视哨” 4)取辅助参数j=-1,其作用是记录待比较元素的下标（有 序部分)，其位置在的前面； 5)将r[0]的关键字与r的关键字相比较；
10.2.1 直接插入排序 ◼ 算法描述 初值：待记录放在无序部分的数组r[1..n]中。 1) 在有序部分中有1个元素r[1]，无序部分元素为r[2..n]； 2) 令i=2，将r[2]作为排序元素； 3) 把r[2]放到r[0]中， r[0]即作为暂存单元，又可作为后面 循环比较用的“监视哨”； 4) 取辅助参数j=i-1，其作用是记录待比较元素的下标（有 序部分），其位置在i的前面； 5) 将r[0]的关键字与r[j]的关键字相比较；
10.2.1直接插入排序 6)若r[0]的关键字小于r]的关键字，则r们后移一个位 置，并继续搜索前面的元素，即j=j-1,然后转向5。 7) 若r[o]的关键字大于r的关键字，故r[O]应放在r[的 后面，即在j+1的位置。 8) 令i=i+1,若此时i>n,则排序完成，否则转入4
10.2.1 直接插入排序 6) 若r[0]的关键字小于r[j]的关键字，则r[j]后移一个位 置，并继续搜索前面的元素，即j=j-1，然后转向5。 7) 若r[0]的关键字大于r[j]的关键字，故r[0]应放在r[j]的 后面，即在j+1的位置。 8) 令i = i +1，若此时i >n，则排序完成，否则转入4
10.2.1直接插入排序 设记录关键字分别为49,38,65,97,76,13,27,49。为了检 测稳定性，我们在后一个49上加了一个横线。具体排 序过程如图所示： [初始关键字] r[O] [49]38659776132749 j=2 (38) [3849]659776132749 j=3 (65) [384965]9776132749 j=4 (97) [38496597]76132749 j=5 (76) [3849657697]132749 j户6 (13) [133849657697]2749 j=7 (27） [13273849657697]49 j=8 (49) [1327384949657697]
◼ 设记录关键字分别为49,38,65,97,76,13,27,49。为了检 测稳定性，我们在后一个49上加了一个横线。具体排 序过程如图所示： [初始关键字] r[0] [49] 38 65 97 76 13 27 49 j=2 (38) [38 49] 65 97 76 13 27 49 j=3 (65) [38 49 65] 97 76 13 27 49 j=4 (97) [38 49 65 97] 76 13 27 49 j=5 (76) [38 49 65 76 97] 13 27 49 j=6 (13) [13 38 49 65 76 97] 27 49 j=7 (27) [13 27 38 49 65 76 97] 49 j=8 (49) [13 27 38 49 49 65 76 97] 10.2.1 直接插入排序
10.2.1直接插入排序 直接插入排序算法： void InsertSort(SqList &L){ for(i=2;i<=L.length;++i) if(L.RI叮.key<L.R[i-1].key)X∥<需将Lr[0插入有序表 L.R[O]=L.R[]; /复制为哨兵 for(j=i-1;L.R[O].key<L.R[j].key;--j) L.R[j+1]=L.R]; /记录后移 L.Rj+1]=L.R0]: /插入到正确位置
◼ 直接插入排序算法： void InsertSort(SqList &L){ for(i=2;i<=L.length;++i) if(L.R[i].key<L.R[i-1].key){ //＜需将L.r[i]插入有序表 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]; //插入到正确位置 } } 10.2.1 直接插入排序
10.2.1直接插入排序 时间复杂度 若初始记录按关键字递增排列，所需进行关键字比较次 数达最小值为n-1,记录不需移动。时间复杂度是0n)。 在反序情况下，由于第个记录的找到相应插入位置需要 比较i次，所以从第2到第个记录共需比较的总次数为： Cmax= ∑，=(n+2(n-1)2=0(n2) 每次首先要将r叮移到r[o], 故每趟移动比比较多一次，则 记录移动的总次数为： Mmax=∑ai+l =(n+4)(n-1)/2=0(n2) 时间复杂度最好情况为O(n),最坏情况为O(n)。平均时间 复杂度为0(n2),由于辅助空间只有R[0],S(n)=0(1)。直 接插入排序为稳定的排序方法
◼ 时间复杂度 ❖ 若初始记录按关键字递增排列，所需进行关键字比较次 数达最小值为n-1，记录不需移动。时间复杂度是O(n)。 ❖ 在反序情况下，由于第i个记录的找到相应插入位置需要 比较i次，所以从第2到第n个记录共需比较的总次数为： Cmax = =(n+2)(n-1)/2=O(n2 ) 每次首先要将r[i]移到r[0]，故每趟移动比比较多一次，则 记录移动的总次数为： Mmax = =(n+4)(n-1)/2=O(n2 ) ❖ 时间复杂度最好情况为O(n),最坏情况为O(n2 )。平均时间 复杂度为O(n2 )，由于辅助空间只有R[0]，S(n)=O(1)。直 接插入排序为稳定的排序方法。 = n i i 2 = + n i i 2 1 10.2.1 直接插入排序