`
yunmanfan
  • 浏览: 95909 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

归并排序

阅读更多

归并(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实现插入排序、二分归并排序、归并排序.rar

    在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...

    三路归并_C语言_三路归并排序_三路归并_

    **三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...

    归并排序C语言实现

    归并排序是一种高效的排序算法,基于分治策略。在C语言中实现归并排序,我们需要理解以下几个关键知识点: 1. **分治法**:归并排序的核心思想是将大问题分解为小问题来解决。首先将数组分为两半,分别对两半进行...

    归并排序算法实现

    ### 归并排序算法实现详解 #### 一、引言 归并排序是一种经典的排序算法,采用分治法的思想,将待排序数组分为若干个子序列,这些子序列是已排序的,然后再按照一定的方式合并这些子序列得到最终排序后的数组。...

    归并排序算法实现(排序算法系列1)

    归并排序是一种高效的、稳定的排序算法,由著名计算机科学家John W. Backus在1946年提出。它是基于分治策略的一种经典算法,适用于处理大量数据。在本系列的第一部分,我们将深入探讨归并排序的基本原理、实现过程...

    java实现归并排序

    Java实现归并排序 Java 实现归并排序是一种常用的排序算法,通过分治策略将原始数组分成小组,然后对每个小组进行排序,最后将排序好的小组合并成一个有序数组。下面是 Java 实现归并排序的知识点总结: 基本思想 ...

Global site tag (gtag.js) - Google Analytics