归并排序1926559-课件（PPT-精）.pptVIP

LOGO LOGO LOGO LOGO LOGO ThemeGallery PowerTemplate Add your company slogan Sorting algorithm 第三组 - 软件工程班 重装上阵 华东理工大学 2014级 排序算法 简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。 华东理工大学 2014级 排序分类 根据排序过程中待排序文件存放的位置不同，可以把排序分为内部和外部排序两类。 内部排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 举例：所有今天要讲的排序方法 外部排序：外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。 举例：多路归并排序 （即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。） 华东理工大学 2014级 归并排序 Divide：把n个元素的序列分为两个元素个数为n/2的子序列。 Conquer：递归的调用归并排序算法对两个子序列进行排序 Combine：对排好序的子序列进行合并，得到最后排序的结果。 算法原理： 归并排序算法是分治法（Divide-and-Conquer）的典型应用 华东理工大学 2014级 归并排序 MERGESORT(A,?first,?last)?? ???if?first??last?? ????????mid?=?(first ?+?r)?/?2?? ????????MERGESORT(A,? first,? last)?? ????????MERGESORT(A,? first ?+?1,? last)?? ????????MERGE(A,? first,? mid,?last)?? 伪代码： 华东理工大学 2014级 归并排序示意图 Mergesort(1,9) Mergesort(1,5) Mergesort(6,9) Mergesort(1,3) Mergesort(4,5) Mergesort(6,7) Mergesort(8,9) Mergesort(1,2) Mergesort(3,3) Mergesort(4,4) Mergesort(5,5) Mergesort(1,1) Mergesort(2,2) Mergesort(6,6) Mergesort(7,7) Mergesort(8,8) Mergesort(9,9) Merge(1,1,2) Merge(4,4,5) Merge(6,6,7) Merge(8,8,9) Merge(1,2,3) Merge(1,3,5) Merge(6,7,9) Merge(1, 5，9） 合并子序列 递归分治 华东理工大学 2014级 归并排序 12 23 78 6 25 16 27 55 30 12 23 78 6 25 16 27 55 30 12 23 78 6 25 16 27 55 30 12 23 78 6 25 16 27 55 30 12 23 23 12 25 6 27 16 55 30 78 23 12 78 25 23 12 6 55 30 27 16 78 55 30 27 25 23 16 12 6 合并子序列 递归分治 华东理工大学 2014级 归并排序 效率（快速排序，归并排序，希尔排序，堆排序比较）： 对20000个随机数据进行测试 对50000个随机数据进行测试 对200000个随机数据进行测试 LOGO LOGO LOGO LOGO LOGO