《第13周内排序第2讲-插入排序.pdf》由会员分享，可在线阅读，更多相关《第13周内排序第2讲-插入排序.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、主要的插入排序主要的插入排序方法：方法： （1）直接插入排序）直接插入排序 （2）折半插入排序）折半插入排序 （3）希尔排序）希尔排序 有序区有序区无序区无序区 一个一个地一个一个地 插入插入 基本思路基本思路 不一定是全局有序（整体有序）不一定是全局有序（整体有序）全局有序区全局有序区的元素的元素 在后面排序中不再发生位置的改变在后面排序中不再发生位置的改变 有序区有序区 R0 Ri- -1 无序区无序区 RiRn- -1 有序区有序区 R0 Ri- -1 Ri 无序区无序区 Ri+1 Rn- -1 一趟排序一趟排序 初始时，有序区只有一个元素初始时，有序区只有一个元素R0 i1n- -1，
2、共经过，共经过n- -1趟排序趟排序 基本思路基本思路 j Ri j=i- -1 插入位置插入位置 一趟直接插入排序：在有序区中插入一趟直接插入排序：在有序区中插入Ri的过程。的过程。 有序有序区区R0.i- -1 无序无序区区Ri.n- -1 Rj+1=tmp tmp 使使R0.i有序有序 扩大有序区扩大有序区 Rj大时便后移大时便后移 当当Ri.keyRi- -1.key时时 void InsertSort(RecType R,int n) int i, j; RecType tmp; for (i=1;in;i+) if (Ri.key=0 /在在j+1处插入处插入Ri 直接插入排序的直
3、接插入排序的算法：算法： 算法分析算法分析 最好的情况（关键字在记录序列中正序）最好的情况（关键字在记录序列中正序）： 最坏的情况（关键字在记录序列中反序）：最坏的情况（关键字在记录序列中反序）： “比较”的次数：比较”的次数： 11 1 1 n n i 0 “移动”的次数：移动”的次数： “比较”的次数：比较”的次数： 2 )1( 1 1 nn i n i “移动”的次数：移动”的次数： 2 )4)(1( )2( 1 1 nn i n i 总的平均比较和移动次数约为总的平均比较和移动次数约为 )( 2 )4)(1( )2()2 22 ( 2 1 1 1 1 n O nn i ii n i n
4、 i 最好：最好：O(n) 最坏：最坏：O(n2) 平均：平均：O(n2) 查找采用折半查找方法，称为二分插入排序或折半插入排序。查找采用折半查找方法，称为二分插入排序或折半插入排序。 有序区有序区 R0 Ri- -1 无序区无序区 RiRn- -1 采用采用折半查找折半查找在有序区找在有序区找 到插入的到插入的位置位置 基本思路基本思路 void BinInsertSort(RecType R,int n) int i, j, low, high, mid; RecType tmp; for (i=1;in;i+) if (Ri.keyRi-1.key)/反序时反序时 tmp=Ri;/将将R
5、i保存到保存到tmp中中 low=0; high=i-1; while (low=high)/在在Rlow.high中查找插入的位置中查找插入的位置 mid=(low+high)/2;/取中间位置取中间位置 if (tmp.key=high+1;j-)/记录记录后移后移 Rj+1=Rj; Rhigh+1=tmp;/插入插入tmp 折半插入排序折半插入排序算法：算法： 折半插入排序：在折半插入排序：在R0.i- -1中查找插入中查找插入Ri的位置，折半查找的平均的位置，折半查找的平均 关键字比较次数为关键字比较次数为log2(i+1)- -1，平均移动元素的次数为，平均移动元素的次数为i/2+2
6、，所以平均时，所以平均时 间复杂度为：间复杂度为： )()2 2 1)1(log( 2 1 1 2 n O i i n i 算法分析算法分析 折半折半插入排序采用折半查找，查找插入排序采用折半查找，查找效率提高。但元素移动次数不变，效率提高。但元素移动次数不变， 仅仅将分散移动改为仅仅将分散移动改为集合移动。集合移动。 说明：本题为说明：本题为2012年年全国考研题全国考研题 【例例】对同一待排序序列分别进行折半插入排序和直接插入对同一待排序序列分别进行折半插入排序和直接插入 排序，两者之间可能的不同之处是排序，两者之间可能的不同之处是。 A.排序的总趟数排序的总趟数 B.元素的移动次数元素的
7、移动次数 C.使用辅助空间的数量使用辅助空间的数量 D.元素之间的比较次数元素之间的比较次数 d=n/2 将排序序列分为将排序序列分为d个组，在个组，在各组内进行各组内进行直接直接插入排序插入排序 递减递减d=d/2，重复重复 ，直到直到d=1 基本思路基本思路 算法最后一趟对所有数据进行了算法最后一趟对所有数据进行了直接插入排序，所以结果一直接插入排序，所以结果一 定是正确的。定是正确的。 将将记录序列分成若干子序列，分别对每个子序列进行直接插入排序。记录序列分成若干子序列，分别对每个子序列进行直接插入排序。 R0， Rd，R2d，Rkd R1， R1+d，R1+2d，R1+kd Rd- -
8、1，R2d- -1，R3d- -1，R(k+1)d- -1 一趟希尔排序一趟希尔排序过程过程 例如：将例如：将 n 个记录分成个记录分成 d 个子序列：个子序列： 相距相距d个位置的记录分为一组个位置的记录分为一组 一组一组 一组一组 一组一组 例如：例如：n=10 9876543210 初始序列初始序列 8765943210d=5 直接插直接插 入排序入排序 4321098765 d=d/2=24321098765 0123456789 直接插直接插 入排序入排序 d=d/2=10123456789 直接插直接插 入排序入排序 0123456789 注意：对于注意：对于d=1的一趟，排序前的
9、数据已将近的一趟，排序前的数据已将近正序正序！ void ShellSort(RecType R,int n) int i, j, d; RecType tmp; d=n/2;/增量置初值增量置初值 while (d0) for (i=d;i=0 j=j-d; Rj+d=tmp; d=d/2;/减小增量减小增量 希尔排序希尔排序算法：算法： for (i=1;i=0 j=j-1; Rj+1=tmp; 直接插入排序：直接插入排序： d循环：使得每个记循环：使得每个记 录都参加排序了录都参加排序了 希尔排序的时间复杂度约为希尔排序的时间复杂度约为O(n1.3)。 希尔排序希尔排序 直接插入排序直接
10、插入排序 大约时间大约时间=102=100 d=5：分为：分为5组，时间约为组，时间约为52220 d=2：分为：分为2组，时间约为组，时间约为25250 d=1：分为：分为1组，几乎有序，时间约为组，几乎有序，时间约为10 + + = 80 为什么希尔排序比直接插入排序好？为什么希尔排序比直接插入排序好？ 例如：有例如：有10个元素要排序。个元素要排序。 希希尔排序算法不稳定的反例：尔排序算法不稳定的反例：希尔排序法是一种不稳定的排序算法。希尔排序法是一种不稳定的排序算法。 351087281206 d=5 317285106208 相对位置发生改变相对位置发生改变 希尔排序是不稳定的希尔排序是不稳定的 【例例10- -1】 希尔排序的组内排序采用的是希尔排序的组内排序采用的是。 A.直接插入排序直接插入排序B.折半插入排序折半插入排序 C.快速排序快速排序D.归并排序归并排序 说明：本题说明：本题为为2015年年全国考研题全国考研题 本讲完本讲完