第9章内排序2

《第9章内排序2》由会员分享，可在线阅读，更多相关《第9章内排序2（66页珍藏版）》请在金锄头文库上搜索。

1、1主要内容29.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 分配排序 9.7 性能比较选择排序的主要操作是选择，其主要思想是：每趟排序在 当前待排序序列中选出关键码最小的记录，添加到有序序列中 。 有序序列r r1r r2r ri-1r rir rnr rk无序序列r rnr ri+1r r1r r2r ri-1r rir ri交换 最小记录9.4 选择排序常用的选择排序算法：（1）直接选择排序 （2）堆排序 39.4.1 直接选择排序41、基本思想每经过一趟比较就找出一个最小值，与待排序列最前面的 位置互换. 2、优点：实现简单3、缺点

2、：每趟只能确定一个元素，表长为n时需要n-1趟 4、前提：顺序存储结构 9.4 选择排序521212525494925*25*16160808 0 1 2 3 4 5212125*25*i i = 1= 14949252516162525161608084949080825*25*49492121i i = 2= 2i i = 3= 30808161625*25*25252121初始初始最小者 0808 交换交换21,0821,08最小者最小者 1616 交换交换25,1625,16最小者最小者 2121 交换交换49,2149,215、直接选择排序的过程9.4.1 直接选择排序6最小者 25

3、*25* 无交换无交换494925*25*0 1 2 3 4 525*25*i i = 5= 5252516160808494925*25*49492121结果i i = 4= 40808161625252121最小者最小者 2525 无交换无交换2525212116160808各趟排序后的结果9.4.1 直接选择排序解决方法：设置一个整型变量index，用于记录在一趟比较的 过程中关键码最小的记录位置。 如何在无序区中记录关键码最小的记录？21212828252516164949 0808indexindex index0808需解决的关键问题?79.4.1 直接选择排序解决方法：第i趟简单

4、选择排序的待排序区间是ri rn ，则ri是无序区第一个记录，所以，将index所记 载的关键码最小的记录与ri交换。如何确定最小记录交换后的最终位置？需解决的关键问题?89.4.1 直接选择排序97、直接选择排序的算法void SelectSort ( elemtype L,int n )for ( i = 1; i =1; i-)HeapAdjust(r, i, n) ;/将序列rin建成堆 关键问题1：如何新建堆？189.4.2 堆排序关键问题2：如何处理堆顶记录？49 25 21 25* 16 081 2 3 4 5 6对 应交换08 25 21 25* 16 491 2 3 4 5

5、6对 应4949252525*25*2121161608081234560808252525*25*212116164949123456199.4.2 堆排序算法描述：r1rn-i+1; 解决方法：第 i 次处理堆顶是将堆顶记录r1与序列中第n -i+1个记录rn-i+1交换。关键问题2：如何处理堆顶记录？209.4.2 堆排序关键问题3：怎样将剩余记录调整成一个新堆？21*算法描述：HeapAdjust(r, 1, n-i);解决方法：第 i 次调整剩余记录，此时，剩余记录有n-i个，调 整根结点至第n-i个记录。9.4.2 堆排序例:对刚才建好的大根堆进行排序：220808 25 21 2

6、5* 16 25 21 25* 16 4949交换 1号与 6 号记录r1 rn492525*21160812345649 25 21 25* 16 08初始最大堆252525*25*16162121136542080849499.4.2 堆排序2316 25* 21 08 25 49交换 1号与 5 号记录0808 25 2125 21 25* 16 25* 16 4949从 1 号到 5 号 重新 调整为最大堆082525*211649123456161625*25*0808252521214949136542 0808252525*25*080825 25* 21 08 16 499.4

7、.2 堆排序240808 16 21 16 21 25* 25 4925* 25 49交换 1 号与 4 号记录25* 16 21 08 25* 16 21 08 25 4925 49从 1号到 4号 重新 调整为最大堆25*25*161608082121252549491234560808161625*25*252521214949136542 161625*25*9.4.2 堆排序2508 16 21 25* 25 49交换 1号与3 号记录21 16 08 21 16 08 25* 25 4925* 25 49从 1 号到 3号 重新 调整为最大堆2121161625*25*080825

8、2549491234560808161625*25*252521214949136542212108089.4.2 堆排序2608 16 21 25* 25 49交换 1 号与2 号记录 排序完毕。16 08 16 08 2121 25* 25 4925* 25 49从 1 号到 2 号 重新 调整为最大堆1616080825*25*2121252549491234560808161625*25*252521214949136542161608089.4.2 堆排序void HeapSort(elemtype h,int n) /* 对顺序表*h进行堆排序 */ for(i=n/2；i=1；i

9、-) Heapadjust(h，i，n)；for(i=n；i=2；i-) temp=h1;h1=hi； hi=temp; /* HeapSort */ 27/*将hi.n建成大顶堆 */* 堆顶与堆底元素交换 */*对h1.i-1重新调整为堆*/Heapadjust(h，1，i-1)；堆排序算法9.4.2 堆排序28void Heapajust(elemtype r，int s，int m)/* 对rs进行调整使其成为大顶堆 */temp=rs；child=2*s；/*temp暂存rs值，child是其左孩子*/ while(child=rchild) break;/*根大则不必调整，函数结束

10、*/else /*否则子女中的大者上移*/s=child； /*将根下降到子女位置并继续向下整理！*/ rs=temp； /直到自下而上都满足堆定义，再放置入口结点针对结点 s 的堆调整函数HeapAdjust ：从结点s开始到当前堆尾m为止，自上向下比较，如果子女的 值大于双亲结点的值，则互相交换，即把局部调整为大根堆。rs=rchild；child=child*2 ;9.4.2 堆排序练习：已知序列503，87，512，61，908，170 ，897，275，653，462，写出采用堆排序法对 该序列作升序排列的第一趟结果。29第一趟结果： 908,653,897,503,462,170,

11、512,275,61,879.4.2 堆排序305、堆排序算法分析： 时间效率： O(nlog2n)。因为整个排序过程中需 要调用n-1次堆顶点的调整，而每次堆排序算法 本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记 录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。9.4.2 堆排序主要内容319.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 分配排序 9.7 性能比较9.5 归并排序321、基本思想：将若干有序序列逐步归并，最终得到一个有 序序列。 （归并排序主要是二

12、路归并排序）2、二路归并排序：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 n / 2 个长度为 2 的有序子序列 ；再做两两归并，如 此重复，直到最后得到一个长度为 n 的有序序列。需解决的关键问题?如何将两个有序序列合成一个有序序列？ 怎样完成一趟归并？ 如何控制二路归并的结束？33212525* 936272083716544921 2525* 4962 9308 7216 375416 37 5421 25 25* 4908 62 72 9308 21 25 25* 49 62 72 9308 16 21 25 25* 37 49 54

13、62 72 93len=1len=2len=4len=8len=1616 37 54整个归并排序仅需log2n 趟关键问题：如何将两个有序序列合成一个有序序列？602031544556520 605 3144 556560 20 31 5 44 55 65ij5kj20i31j609.5 归并排序34kkk在归并过程中，可能会破坏原 来的有序序列，所以，将归并 的结果存入另外一个数组中。 关键问题：如何将两个有序序列合成一个有序序列？602031544556520 605 3144 556560 20 31 5 44 55 65ij5kj20i31j609.5 归并排序3536算法思想（以升序

14、为例）：先用两个指针分别指向两个序列 的第一个数据元素，进行比较，取出较小者，然后将其所在 序列的指针后移，重复以上过程，直到指针达到序列的末尾 ，这时将另一个序列的剩余元素依次顺序放到有序序列的后 面即可。关键问题：如何将两个有序序列合成一个有序序列？s m m+1 t r s t r1 ijk9.5 归并排序37具体步骤： 将两个有序序列rs.m和rm+1.t归并为有序序列 r1s.t的过程： i=s；j=m+1；k=s； 若im 或 jt，执行(4)； 比较ri和rj关键字,将较小的存入r1中: 如果ri =n-h+1) for (k=i; k=n; k+) r1k=rk; 9.5 归并排序43void MergePass (int r , int r1 , int n, int h) /对r做一趟归并，结果存入r1i=1;while (in-2h+1) /长度均为h的区间合并Merge (r, r1, i, i+h-1, i+2*h-1);i+=2*h;if (in-h+1) /长度不相等的区间合并Merge (r, r1, i, i+h-1, n); else for (k=i; k=n;