数据结构课件第8章排序技术幻灯片.ppt

归并排序 关键问题⑵：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ①若i≤n-2h+1，则相邻两个有序表的长度均为h，执行一次归并，完成后i加2h，准备进行下一次归并； 算法描述： while (i≤n-2h+1) { Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; } 归并排序 关键问题⑵：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ②若i＜n-h+1，则表示仍有两个相邻有序表，一个长度为h，另一个长度小于h，则执行两个有序表的归并，完成后退出一趟归并。 20 60 5 31 44 55 65 i h i=4 n-2h+1=4 n-h+1=6 n-2h+1 n-h+1 h 归并排序 关键问题⑵：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ②若i＜n-h+1，则表示仍有两个相邻有序表，一个长度为h，另一个长度小于h，则执行两个有序表的归并，完成后退出一趟归并。 算法描述： if (i＜n-h+1) Merge (r, r1, i, i+h-1, n); 归并排序 关键问题⑵：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ③若i≥n-h+1，则表明只剩下一个有序表，直接将该有序表送到r1的相应位置，完成后退出一趟归并。 i i=9 n-h+1=8 n-h+1 h 20 60 5 31 44 55 65 15 28 归并排序 关键问题⑵：怎样完成一趟归并？ 设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况： ③若i≥n-h+1，则表明只剩下一个有序表，直接将该有序表送到r1的相应位置，完成后退出一趟归并。 算法描述： if (i=n-h+1) for (k=i; k=n; k++) r1[k]=r[k]; void MergePass (int r[ ], int r1[ ], int n, int h) { i=1; while (i≤n-2h+1) //情况1 { Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; } if (i＜n-h+1) Merge (r, r1, i, i+h-1, n); //情况2 else for (k=i; k=n; k++) //情况3 r1[k]=r[k]; } 一趟归并排序算法 归并排序 解决方法： 开始时，有序序列的长度h=1，结束时，有序序列的长度h=n，用有序序列的长度来控制排序的结束。 归并排序 关键问题⑶：如何控制二路归并的结束？ 算法描述： void MergeSort (int r[ ], int r1[ ], int n ) { h=1; while (hn) { MergePass (r, r1, n, h); h=2*h; MergePass (r1, r, n, h); h=2*h; } } 归并排序 关键问题⑶：如何控制二路归并的结束？ 二路归并排序算法的性能分析 归并排序 时间性能： 一趟归并操作是将r[1]~r[n]中相邻的长度为h的有序序列进行两两归并，并把结果存放到r1[1]~r1[n]中，这需要O(n)时间。整个归并排序需要进行 趟，因此，总的时间代价是O(nlog2n)。这是归并排序算法的最好、最坏、平均的时间性能。 空间性能： 算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为O(n)。 é ù n 2 log 各种排序方法的比较 对排序算法应该从以下几个方面综合考虑： ⑴时间复杂性； ⑵空间复杂性； ⑶稳定性； ⑷算法简单性； ⑸待排序记录个数n的大小； ⑹记录本身信息量的大小； ⑺关键码的分布情况。 时间复杂度比较 各种排序方法的比较 排序方法 平均情况 最好情况 最坏情况 直接插入排序 O(n2) O(n) O(n2) 希尔排序 O(nlog2n) O(n1.3) O(n2) 起泡排序 O(n2) O (n) O(n2) 快速排序 O(nlog2n) O(nlog2n) O(n2) 简单选择排