数据结构课件1第10章排序幻灯片.ppt

* 08 16 21 25* 25 49 交换 1号与3 号记录 21 16 08 25* 25 49 从 1 号到 3号 重新 调整为最大堆 21 16 25* 08 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 * 08 16 21 25* 25 49 交换 1 号与2 号记录 16 08 21 25* 25 49 从 1 号到 2 号 重新 调整为最大堆 16 08 25* 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 * void HeapSort (HeapType H ) { //对顺序表H进行堆排序 for ( i = H.length / 2; i 0; -- i ) HeapAdjust(H,i, H.length ); //初始堆 for ( i = H.length; i 1; --i) { H.r[1] H.r[i]; //交换，要借用temp HeapAdjust( H, 1,i-1 ); //重建最大堆 } } 堆排序的算法 参见教材P281-282 这是针对结点i 的堆调整函数（也是建堆函数），每次调用耗时O(log2n) * 附1：基于初始堆进行堆排序的算法步骤： 堆的第一个对象V[0]具有最大的关键码，将V[0]与V[n]对调，把具有最大关键码的对象交换到最后，再对前面的n-1个对象，使用堆的调整算法，重新建立堆。结果具有次最大关键码的对象又上浮到堆顶，即V[0]位置。 再对调V[0]和V[n-1]，调用对前n-2个对象重新调整，…如此反复，最后得到全部排序好的对象序列。 * 比较左右孩子大小，j指向大者 比较大孩子与rc的大小 若大向上浮 rc = H.r[s]; j = 2s; jm H.r[j].keyH.r[j+1].key ++ j; // 指向右兄弟 j m rc.key H.r[j].key H.r[s]=H.r[j]; s=j; j=2*j; //指向左孩子 N N N Y Y Y H.r[s…m]中除r[s]外，其他具有堆特征 现调整r[s]的值 ，使H.r[s…m]为堆 附2：算法流程 * 堆排序算法分析： 时间效率： O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法，而算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。 * 10.5 归并排序 归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。 更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 ?n / 2? 个长度为 2 的子序列 ；再做两两归并，…，如此重复，直到最后得到一个长度为 n 的有序序列。 例：关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。 * 21 25 25* 93 62 72 08 37 16 54 49 21 25 25* 49 62 93 08 72 16 37 54 16 37 54 21 25 25* 49 08 62 72 93 08 21 25 25* 49 62 72 93 08 16 21 25 25* 37 49 54 62 72 93 len=1 len=2 len=4 len=8 len=16 16 37 54 整个归并排序仅需?log2n ?趟 * 一趟归并排序算法: (两路有序并为一路) 参见教材P283 void Merge (SR，TR，i, m, n) { // 将有序的SR[i…m]和SR[m+1…n]归并为有序的TR[i…n] for(k=i , j=m+1; i=m j=n; ++k ) { if ( SR[i]= SR[j] )TR[k]=SR[i++]; else TR[k]=SR[j++]; // 将SR中记录由小到大地并入TR } if (i=m) TR[k…n]=SR[i…m]; // 将剩余的SR[i…m]复制到TR if (j=n) TR[k…n]=SR[j…n]; // 将剩余的SR[j…n]复制到TR } // Merge * void MSort (SR，TR1