2路插入排序.pptVIP

基本思想 直接插入算法虽然简单，但当记录数量n很大时，则比较次数将大大增加，对于有序表（限于顺序存储结构），为了减少关键字的比较次数，可采用二路插入排序。 二路插入排序的基本思想是：用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入。 2-路插入排序是在折半插入排序的基础上再改进，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。 具体做法：另设一个和L.r同类型的数组d，首先将L.r[1]赋值给d[1]，并将d[1]看成是在排好序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到d[1]之前或之后的有序序列中。先将待插记录的关键字和d[1]的关键字进行比较，若L.r[i].keyd[1].key,则将L.r[i]插入到d[1]之前的有序表中。反之，则将L.r[i]插入到d[1]之后的有序表中。在实现算法时，可将d看成是一个循环向量，并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。 2.例10-2。现有17、29、3、87、25、64、126,7位数字，现对这些数字由大到小进行排序。 1 2 3 4 5 6 7 17?? 29 3 87 25 64 127 （1） 29 17 （2） 29 3 17 （3） 29 87 3 17 （4） 29 87 3 17 25 （5） 29 64 87 3 17 25 （6） 29 64 87 127 3 17 25 if (L[i] d[first])//待插入记录小于d中最小值，插入到d[first]之前（不需移动d数组的元素）。 { first = (first - 1 + length) % length; d[first] = L[i]; } else if (L[i] d[final])//待插入记录大于d中最大值，插入到d[final]之后（不需移动d数组的元素）。 { final = final + 1; d[final] = L[i]; } else//待插入记录大于d中最小值，小于d中最大值，插入到d的中间（需要移动d数组的元素）。 { int j = final ++;//移动d尾部元素以便按序插入记录。 while (L[i] d[j]) { d[(j + 1) % length] = d[j]; j = (j - 1 + length) % length; } d[j + 1] = L[i]; } } 习题 现有以下这些数字，进行2-路排序 35、68、12、46、99、103、80 、99 二路插入排序 讲解： 王云飞 flash：史涵旭 习题： 崔淇瑞 ppt： 杨宇 final first first final final final 谢谢大家！！！ 祝大家考试顺利！！！