第10章 内部排序数据结构讲义- 插入排序SunLandnuc.edu.cn数据结构课程的内容10.1 概述1. 什么是排序？将一组杂乱无章的数据按一定的规律顺次排列起来。 定义：设有记录序列： R1、R2 Rn 其相应的关键字序列为： K1、K2 Kn; 若存在一种确定的关系： Kxlength;i+) l-r0=l-ri;j=i-1;while(l-r0.keyrj.key) l-rj+1=l-rj;j-;l-rj+1=l-r0; n n若设待排序的对象个数为若设待排序的对象个数为n n，则算法需要进则算法需要进 行行n n-1-1次插入。次插入。n n最好情况下，排序前对象已经按关键码大最好情况下，排序前对象已经按关键码大 小从小到大有序，每趟只需与前面的有序小从小到大有序，每趟只需与前面的有序 对象序列的对象序列的最后一个对象最后一个对象的关键码比较的关键码比较 1 1 次，移动次，移动 2 2 次对象。因此，总的关键码比次对象。因此，总的关键码比 较次数为较次数为n n-1-1，对象移动次数为对象移动次数为 2(2(n n-1)-1)。直接插入排序的算法 分析 最坏情况下，第最坏情况下，第i i趟插入时，第趟插入时，第i i个对个对 象必须与前面象必须与前面i-1i-1个对象都做关键码个对象都做关键码 比较，并且每做比较，并且每做 1 1 次比较就要做次比较就要做 1 1 次数据移动。则总的关键码比较次次数据移动。则总的关键码比较次 数数KCNKCN和对象移动次数和对象移动次数RMNRMN分别为分别为 若待排序对象序列中出现各种可能排列的概若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码比较次数和对均情况。在平均情况下的关键码比较次数和对象移动次数约为象移动次数约为 n n2 2/4/4。因此，直接插入排序的因此，直接插入排序的时间复杂度为时间复杂度为 o(o(n n2 2) )。 直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。2） 折半插入排序优点：比较的次数大大减少，全部元素比较次数仅为 O(nlog2n)。 时间效率：虽然比较次数大大减少，可惜移动次数并 未减少，所以排序效率仍为O(n2) 。 空间效率： O（1） 稳定性：稳定新元素插入到哪里？在已形成的有序表中折半查找，并在适 当位置插入，把原来位置上的元素向后顺移。讨论：若记录是链表结构，用直接插入 排序行否？折半插入排序呢？折半插入排序的改进折半插入排序的改进2-2-路插入排序见教材路插入排序见教材P267P267。但链表无法但链表无法“折半折半”！答：直接插入不仅可行，而且还无需移动元 素，时间效率更高！例2：关键字序列T= （21，25，49，25*，16，08） ， 请写出直接插入排序的具体实现过程。i i=1=121212525494925*25*16160808 0 1 2 3 4 5 6暂暂 存存2121i i=2=2i i=3=3i i=5=5i i=4=4i i=6=62525252525494949494925*25*25*494916161625*25*0808084949解：假设该序列已存入一维数组V7中，将V0作为缓冲或 暂存单元（Temp）。则程序执行过程为：21212525494925*25*2121初态： 1616494925*25*2525212116160808完成完成! !直接插入排序直接插入排序的改进l算法的平均时间复杂度为O(n2)。l在最好情况下，即待排记录序列已经 是从小到大排好顺序时，其时间复杂 度为O(n)。l当待排记录基本有序时，算法的效率 也比较高。例如（25， 21， 49，26，56 ，76 ）l当n值很小时，算法效率也比较高。希尔排序（又称缩小增量排序）其基本 思想：对待排记录序列先作“宏观”调整，再 作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：10.2.3 希尔排序将记录序列分成若干子序列，分别对每个子 序列进行插入排序。其中，d 称为增量，它的值在排序过程 中从大到小逐渐缩小，直至最后一趟排 序减为 1。例如：将 n 个记录R1Rn分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 38希尔排序示例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体实现过程 。012345678910 4938659776132749*5504初态 ： 第1趟 (dk=5)第2趟 (dk=3) 第3趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 分析：开始时dk 的值较大，子序列中的对象较少，排序 速度较快；随着排序进展，dk 值逐渐变小，子序 列中对象个数逐渐变多，由于前面工作的基础， 大多数对象已基本有序，所以排序速度仍然很快 。riri练习l欲将序列： (8, 5, 2, 12, 7, 1, 6, 10, 9, 3, 4,11)l中的关键码按从小到大的顺序进 行排序，则初始步长为4的希尔 排序一趟的结果是？希尔排序的实现l取定步长序列，如dk=5,3,1。l对每一步长dk，重复执行如下过程：把每一子序列第一个元素看成是有序的，对 后面的每一个元素ri，重复执行如下过程 ：l把ri暂存在第0号单元；l寻找相应子序列中应该插入的位置：从 后向前依次比较相应子序列中的元素，直 到找到不大于ri的元素。l把ri放到适当的位置。编程实现希尔排序希尔排序的效率l时间效率：当增量序列为d(k)=2t-k+1-1时，时间复杂 度为O(O(n n1.51.5）。l空间效率：O（1）l算法的稳定性：不稳定初始： (49，38，65，97, 76, 13, 27, 49*，55, 04）结束： (04，13，27，38, 49*, 49, 55, 65，76, 97）作业以关键字序列（256，301，751，129，937 ，863，742，694，076，438）为例，分别写 出执行以下算法的各趟排序结束时，关键字 序列的状态。 直接插入排序 希尔排序（取dk=5,3,1）