文档章节

归并排序

超级普华
 超级普华
发布于 2014/12/16 13:49
字数 1654
阅读 11
收藏 0

归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。
两路归并算法
1
、算法基本思路
    
 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m]R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。

1)合并过程
    
 合并过程中,设置ijp三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]R[j]的关键字,取关键字较小的记录复制到R1[p]中,然后将被复制记录的指针ij1,以及指向复制位置的指针p1
    
 重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。

2)动态申请R1
    
 实现时,R1是动态申请的,因为申请的空间可能很大,故须加入申请空间是否成功的处理。

2
、归并算法
  void Merge(SeqList R
int lowint mint high)
    {//
将两个有序的子文件R[low..m)R[m+1..high]归并成一个有序的
     //
子文件R[low..high]
     int i=low
j=m+1p=0 //置初始值
     RecType *R1
 //R1是局部向量,若p定义为此类型指针速度更快
     R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))

     if(! R1) //
申请空间失败
       Error("Insufficient memory available!")

     while(i<=m&&j<=high) //
两子文件非空时取其小者输出到R1[p]
       R1[p++]=(R[i].key<=R[j].key)?R[i++]
R[j++]
     while(i<=m) //
若第1个子文件非空,则复制剩余记录到R1
       R1[p++]=R[i++]

     while(j<=high) //
若第2个子文件非空,则复制剩余记录到R1
       R1[p++]=R[j++]

     for(p=0
i=lowi<=highp++i++)
       R[i]=R1[p]
//归并完成后将结果复制回R[low..high]
    } //Merge

归并排序
     归并排序有两种实现方法:自底向上和自顶向下。
1
、 自底向上的方法
1) 自底向上的基本思想
     
自底向上的基本思想是:第1趟归并排序时,将待排序的文件R[1..n]看作是n个长度为1的有序子文件,将这些子文件两两归并,若n为偶数,则得到
  个长度为2的有序子文件;若n为奇数,则最后一个子文件轮空(不参与归并)。故本趟归并完成后,前  个有序子文件长度为2,但最后一个子文件长度仍为1;第2趟归并则是将第1趟归并所得到的  个有序的子文件两两归并,如此反复,直到最后得到一个长度为n的有序文件为止。
     
上述的每次归并操作,均是将两个有序的子文件合并成一个有序的子文件,故称其为"二路归并排序"。类似地有k(k>2)路归并排序。
2) 一趟归并算法
 
分析:
      
在某趟归并中,设各子文件长度为length(最后一个子文件的长度可能小于length),则归并前R[1..n]中共有
  个有序的子文件:R
[1..length]
R[length+1..2length],…,
  
注意:
     
调用归并操作将相邻的一对子文件进行归并时,必须对子文件的个数可能是奇数、以及最后一个子文件的长度小于length这两种特殊情况进行特殊处理:
  ① 若子文件个数为奇数,则最后一个子文件无须和其它子文件归并(即本趟轮空)
  ② 若子文件个数为偶数,则要注意最后一对子文件中后一子文件的区间上界是n
  
具体算法如下:
    void MergePass(SeqList R
int length)
     { //
R[1..n]做一趟归并排序

      int i

      for(i=1;i+2*length-1<=n;i=i+2*length)
      Merge(R
ii+length-1i+2*length-1)
           //
归并长度为length的两个相邻子文件
      if(i+length-1<n) //
尚有两个子文件,其中后一个长度小于length
         Merge(R
ii+length-1n) //归并最后两个子文件

      //
注意:若ini+length-1n时,则剩余一个子文件轮空,无须归并
     } //MergePass

)二路归并排序算法
  void MergeSort(SeqList R)
   {//
采用自底向上的方法,对R[1..n]进行二路归并排序
     int length

     for(1ength=1
length<nlength*=2) //
 趟归并
        MergePass(R
length) //有序段长度≥n时终止
   }
注意:
     
自底向上的归并排序算法虽然效率较高,但可读性较差。

2、自顶向下的方法
     
采用分治法进行自顶向下的算法设计,形式更为简洁。
1)分治法的三个步骤
     
设归并排序的当前区间是R[low..high],分治法的三个步骤是:
①分解:将当前区间一分为二,即求分裂点

                 

②求解:递归地对两个子区间R[low..mid]R[mid+1..high]进行归并排序;
③组合:将已排序的两个子区间R[low..mid]R[mid+1..high]归并为一个有序的区间R[low..high]
  
递归的终结条件:子区间长度为1(一个记录自然有序)。

2)具体算法
    void MergeSortDC(SeqList R
int lowint high)
     {//
用分治法对R[low..high]进行二路归并排序

       int mid

       if(low<high){//
区间长度大于1
          mid=(low+high)/2
 //分解

          MergeSortDC(R
lowmid); //递归地对R[low..mid]排序
          MergeSortDC(R
mid+1high) //递归地对R[mid+1..high]排序
          Merge(R
lowmidhigh) //组合,将两个有序区归并为一个有序区
        }
     }//MergeSortDC

3)算法MergeSortDC的执行过程
     
算法MergeSortDC的执行过程如下图所示的递归树。


算法分析

1
、稳定性
     
 归并排序是一种稳定的排序。

2
、存储结构要求
    
 可用顺序存储结构。也易于在链表上实现。

3
、时间复杂度
    
 对长度为n的文件,需进行 趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)

4
、空间复杂度
   
  需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序


© 著作权归作者所有

超级普华
粉丝 0
博文 6
码字总数 6874
作品 0
海淀
私信 提问
排序算法之归并排序

一、分治法的思想 把复杂的问题分解,再分解,成为很小的问题,解决这些小问题之后合并,再合并。这就是分治法的思想。 通常分治法是递归的。 二、归并排序 归并排序就是利用分治法,把无序的...

Lubby
2015/10/08
102
0
java泛型中使用的排序算法——归并排序及分析

一、引言 我们知道,java中泛型排序使用归并排序或TimSort。归并排序以O(NlogN)最坏时间运行,下面我们分析归并排序过程及分析证明时间复杂度;也会简述为什么java选择归并排序作为泛型的排序...

9龙
04/29
0
0
排序算法(7) -- 归并排序

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/87947485 一、前言 归并排序是建立...

dby_freedom
02/26
0
0
归并排序——“递归+合并”(Java版)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

十一11
2016/04/07
84
0
白话经典算法系列之五 归并排序的实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

长平狐
2012/12/10
60
0

没有更多内容

加载失败,请刷新页面

加载更多

四种解决Nginx出现403 forbidden 报错的方法

我是在在本地用虚拟机中通过yum安装nginx的,安装一切正常,但是访问时报403, 于是查看nginx日志,路径为/var/log/nginx/error.log。打开日志发现报错Permission denied,详细报错如下: 1....

dragon_tech
8分钟前
1
0
获取RestResultResponse返回的值

Springboot项目,需要调其他服务的接口,返回值类型是RestResultResponse 打断点的结果集是这个 打印出来的getData(): [{id=3336b624-8474-4dd9-bd5b-c7358687c877, paraNo=104, para=Postpo...

栾小糖
11分钟前
0
0
【小学】 生成10以内的加减法

#!/usr/bin/env python# coding: utf-8from random import randrange# 题目的最大数值R_MAX = 10# 生成的题目的数量R_PAGE = 70# 生成减法列表def get_sub_list():...

Tensor丨思悟
31分钟前
9
0
JavaScript设计模式——适配器模式

  适配器模式是设计模式行为型模式中的一种模式;   定义:   适配器用来解决两个已有接口之间不匹配的问题,它并不需要考虑接口是如何实现,也不用考虑将来该如何修改;适配器不需要修...

有梦想的咸鱼前端
39分钟前
3
0
Andorid SQLite数据库开发基础教程(1)

Andorid SQLite数据库开发基础教程(1) Android数据库访问方式 SQLite是Android系统默认支持的文件数据库。该数据库支持SQL语言,适合开发人员上手。本教程将讲解如何开发使用SQLite的Andro...

大学霸
42分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部