数据结构(非线性结构).ppt

* * 循环4步 * * 对应的算法(整棵树)： BSIFT(r,n) 1.p ? ?n/2? 2.for i=p to 1 step(-1) 3. SIFT(r,n,i) 4.return * * （2）堆排序 在上述算法基础上，堆排序分两个步骤： 由给定的无序序列构造堆。 将堆顶元素与堆中最后一个元素交换，然后将最后一个元素从堆中删除，将余下的元素构成的完全二叉树重新调整为堆，反复进行直到堆空为止。 下图为堆排序的前三趟。 * * 构堆?交换?删除?构堆?… * * 算法： HEAPSORT(r,n) 1. p ? ?n/2? 2.for i=p to 1 step(-1) SIFT(r,n,i) 3.for i=n to 2 step(-1) 4. {r[1]?r[i];SIFT(r,i-1,1)}//注意:k=1// 5.return 结点数递减 * * 堆排序总结： 把以结点r[k]为根结点的子树构造成堆，SIFT(r,n,k)； 整棵树构造为堆，BSIFT(r,n)，重复?n/2? 次SIFT(r,n,k)； 堆顶元素与堆中最后一个元素交换，删除最后一个元素，重新构堆。 有序区在序列的后端. 堆排序不一定是稳定排序. 两种选择排序皆为向量存储结构. E10 * * 堆排序本质: 把待排序的n个无序序列放在一维数组中,把它看作一棵完全二叉树,对它构造堆,让堆顶元素(第一个元素)与最后一个元素(第n个元素)交换,此时第n个元素即为有序区.然后对其余 n-1个元素进行调整,使其再成为堆,重复上述操作,直到整个数组都成为有序区为止. * * （3）算法分析：（自学） 对堆排序的比较次数和移动次数作精确分析较困难，这里采用近似估算。 ①建堆过程中比较次数C1与移动次数M1： 建堆过程共调用SIFT ?n/2? 次，最坏情况下每调用SIFT一次，比较次数为： * * 总的比较次数为： 当n足够大时，近似为： * * ②堆排序过程中比较次数C2与移动次数M2： 排序过程共调用SIFT n-1次，最坏情况下，每调用SIFT一次，比较次数为： * * 其中3(n-1)为交换r[1]与r[i]的次数。 在最坏情况下，时间复杂度为O(log2n)。 堆排序只需一个辅助空间用于交换记录。 * * 2.8.3 插入排序 基本操作： 将当前无序区中最前端的记录插入到有序区中，使有序区逐渐增大，直到所有记录都插入有序区为止。 一趟： 每插入一个记录的过程称为一趟。 插入方式： 线性插入 对半插入 * * 1、线性插入排序 在有序区中进行顺序查找，以确定插入的位置，然后移动记录腾出空间，以便相应关键字的记录插入。 “监视哨”：为防止循环变量越界，在有序区前端，即r[0]，设一个监视哨， r[0]中存放当前要插入的关键字。同线性查找中的监视哨r[n+1]。 * * 例子：序列｛20,6,15,7,3｝用线性插入排序的过程为： R[0] R[1] R[2] R[3] R[4] R[5] i=2,j=1 6 [20] 6 15 7 3 i=3,j=2 15 [6 20] 15 7 3 i=4,j=3 7 [6 15 20] 7 3 i=5,j=4 3 [6 7 15 20] 3 [3 6 7 15 20] i：当前要插入的记录，j：当前有序区的最后一个记录--有序区的上界 * * 线性插入排序算法： INSERTSORT(r,n) 1.for i=2 to n 2. r[0]?r[i];j ?i-1//有序区的上界 3. While(r[0]r[j]) do 4. r[j+1] ?r[j];j ?j-1 5. end(while)//顺序寻找插入位置 6. r[j+1] ?r[0]//插入空位 7.end(i) 8.return * * （自学） 算法分析：线性插入排序的比较次数和移动次数与序列中关键字的原始排列情况有关。 若原始记录已按关键字排序，则比较次数和移动次数最小。 比较次数 移动次数 若原始记录是按关键字逆序排列的，则比较次数和移动次数最大。 比较次数 移动次数 * * 时间复杂度取最小值和最大值的平均值O(n2)。 只需一个辅助单元r[0]，因此空间复杂度为O(1)。 * * 2、对半插入排序 同对分查找，在有序区中有哪些信誉好的足球投注网站插入位置时，可用对分查找方法，称为对半插入排序。 算法：BINSORT(r,n) 1.for i=2 to n 2. r[0]?r[i];low?1;high ?i-1 3. While (low ? high) do 4. mid ? ?(low+high)/2? 5. if(r[0]r[mid]) then high