算法18--内部排序-插入排序.ppt

《算法18--内部排序-插入排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、----插入排序（1）第9章内部排序9.1概述9.2插入排序9.3快速排序9.4选择排序9.5归并排序9.6基数排序9.7内部排序方法的比较第9章内部排序21.直接插入排序（基于顺序查找）3.表插入排序（基于链表存储）2.折半插入排序（基于折半查找）4.希尔排序（基于逐趟缩小增量）9.2插入排序1.直接插入排序利用“顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置”9.2插入排序插入过程分为两步:★在已排好序的表中查找插入位置；★插入元素。不同的插入算法的区别在于第一步的不同从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i];//设置“哨兵”循环结束表明R

2、[i]的插入位置为j+1对于在查找过程中找到的那些关键字不小于[i].key的记录，并在查找的同时实现记录向后移动；R[j+1]=R[j]R[0]j+1R[i]for(j=i-1;R[0].key

3、)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置9.2.1直接插入排序例1：关键字序列T=（20，25，46，25*，11，06），请写出直接插入排序的具体实现过程。*表示后一个25解：假设该序列已存入一维数组V[7]中，将V[0]作为缓冲或暂存单元（Temp）。则程序执行过程为：1125*062025i=2V[0]25*46L.r[i].key>L.r[i-1].keyi=3L.r[i].key

4、252011i=6L.r[i].key

5、趟排序：[47]329136第二趟排序：[347]29136第三趟排序：[34729]136第四趟排序：[3471329]6第五趟排序：[34671329]图9-1直接插入排序的过程最好的情况（关键字在记录序列中顺序有序）：最坏的情况（关键字在记录序列中逆序有序）：直接插入排序算法分析：“比较”的次数：“比较”的次数：0“移动”的次数：“移动”的次数：9.2.1直接插入排序10平均的情况：若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码比较次数和对象移动次数约为n2/4。空间效率：O（1）——因为仅占用1个缓冲单元9.2.1直接插入排

6、序9.2.1直接插入排序直接插入排序的时间复杂度为O(n2)。直接插入排序是一种稳定的排序方法。129.2.2折半插入排序当记录数量n的很大时，不宜采取直接插入排序的方法。因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。13voidBiInsertionSort(SqList&L){}//BInsertSort在L.r[1..i-1]中折半查找插入位置；for(i=2;i<=L.length;++i){}//forL.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]for

7、(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入9.2.2折半插入排序low=1;high=i-1;while(low<=high){}m=(low+high)/2;//折半if(L.r[0].key