第八章排序要点解析.pptVIP

堆排序算法的性能分析 第1个for循环是初始建堆，需要O(n)时间； 第2个for循环是输出堆顶重建堆，共需要取n-1次堆顶记录，第 i 次取堆顶记录重建堆需要O(log2i)时间，需要O(nlog2n)时间； 因此整个时间复杂度为O(nlog2n)，这是堆排序的最好、最坏和平均的时间代价。 堆排序 8.5 归并排序 归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。 归并：将两个或两个以上的有序序列合并成一个有序序列的过程。 基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止。 二路归并排序 排序过程： 60 20 31 5 44 55 65 二路归并排序 初始关键字序列 20 60 5 31 44 55 65 第一趟结果 5 20 31 60 44 55 65 第二趟结果 5 20 31 44 55 60 65 第三趟结果 二路归并排序 需解决的关键问题? ⑴如何将两个有序序列合成一个有序序列？ ⑵怎样完成一趟归并？ ⑶如何控制二路归并的结束？ 关键问题⑴：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 20 60 5 31 44 55 65 60 20 31 5 44 55 65 i j 5 k j 20 i 31 j 60 二路归并排序 关键问题⑴：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 20 60 5 31 44 55 65 60 20 31 5 44 55 65 i j 5 k j 20 i 31 j 60 归并可以就地进行吗? 二路归并排序 在归并过程中，可能会破坏原来的有序序列，所以，将归并的结果存入另外一个数组中。 关键问题⑴：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 20 60 5 31 44 55 65 60 20 31 5 44 55 65 i j 5 k j 20 i 31 j 60 二路归并排序 关键问题⑴：如何将两个有序序列合成一个有序序列？ 60 20 31 5 44 55 65 20 60 5 31 44 55 65 60 20 31 5 44 55 65 i j 5 20 31 60 子序列的长度一定相等吗? 二路归并排序 关键问题⑴：如何将两个有序序列合成一个有序序列？ 设相邻的有序序列为r[s] ~ r[m]和r[m+1] ~ r[t]，归并成一个有序序列r1[s] ~ r1[t] s m m+1 t r[ ] s t r1[ ] i j k 二路归并排序 void Merge (int r[ ], int r1[ ], int s, int m, int t ) { i=s; j=m+1; k=s; while (i=m j=t) { if (r[i]=r[j]) r1[k++]=r[i++]; else r1[k++]=r[j++]; } if (i=m) while (i=m) //收尾处理 r1[k++]=r[i++]; //前一个子序列 else while (j=t) r1[k++]=r[j++]; //后一个子序列 } 关键问题⑴：如何将两个有序序列合成一个有序序列？ 算法实现： 二路归并排序 关键问题⑵：怎样完成一趟归并？ 60 20 31 5 44 55 65 20 60 5 31 44 55 65 60 20 31 5 44 55 65 5 20 31 60 44 55 65 在