归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并
归并操作:
归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。
如 设有数列{6,202,100,301,38,8,1}
初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
i=3 [ 1 6 8 38 100 202 301 ] 4
总计: 11次
算法描述:
归并操作的工作原理如下:
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
设定两个指针,最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
复杂度:
时间O(nlogn)
空间O(n)
与快速排序类似。
与快速排序的比较:
归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.
分享到:
相关推荐
在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...
**三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...
归并排序是一种高效的排序算法,基于分治策略。在C语言中实现归并排序,我们需要理解以下几个关键知识点: 1. **分治法**:归并排序的核心思想是将大问题分解为小问题来解决。首先将数组分为两半,分别对两半进行...
### 归并排序算法实现详解 #### 一、引言 归并排序是一种经典的排序算法,采用分治法的思想,将待排序数组分为若干个子序列,这些子序列是已排序的,然后再按照一定的方式合并这些子序列得到最终排序后的数组。...
归并排序是一种高效的、稳定的排序算法,由著名计算机科学家John W. Backus在1946年提出。它是基于分治策略的一种经典算法,适用于处理大量数据。在本系列的第一部分,我们将深入探讨归并排序的基本原理、实现过程...
Java实现归并排序 Java 实现归并排序是一种常用的排序算法,通过分治策略将原始数组分成小组,然后对每个小组进行排序,最后将排序好的小组合并成一个有序数组。下面是 Java 实现归并排序的知识点总结: 基本思想 ...