当前位置:  编程技术>c/c++/嵌入式

C语言实现排序算法之归并排序详解

    来源: 互联网  发布时间:2014-10-26

    本文导语:  排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。 一、实现原理: 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[...

排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

一、实现原理:

1、算法基本思路

设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。

(1)合并过程

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

(2)动态申请R1

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

二、3种方法实现:

算法1:归并函数都动态分配一个数组,两个有序数组合并成一个有序数组

//合并将两个有序序列([low,mid],[mid+1,high])合并
void Merge(int arr[],int low,int mid,int high)
{
  int i=low,j=mid+1,p=0;

  int *newarr = (int *)malloc((high-low+1)*sizeof(int));//用来暂存排序好的数据
  if(!newarr){
    printf("malloc error!n");
    exit(1);
  }

  while(i

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • c语言实现MD5算法完整代码示例
  • LM优化算法的C语言实现 levmar
  • MD5算法的C语言实现
  • c语言的金钱算法
  • c语言 汉诺塔算法代码
  • C语言快速幂取模算法小结
  • C语言实现的PNPoly算法代码例子
  • C语言 扩展欧几里得算法代码
  • c语言中使用BF-KMP算法实例
  • C语言的数字游戏算法效率问题探讨实例
  • 纯C语言:贪心Prim算法生成树问题源码分享
  • C语言实现二叉树遍历的迭代算法
  • C语言kmp算法简单示例和实现原理探究
  • c语言实现单链表算法示例分享
  • 马尔可夫链算法(markov算法)的awk、C++、C语言实现代码
  • C语言位图算法详解
  • C语言实现魔方阵算法(幻方阵 奇魔方 单偶魔方实现)
  • C语言实现的排列组合问题的通用算法、解决方法
  • 最小生成树算法C语言代码实例
  • C语言实现字符串匹配KMP算法
  • 基于一致性hash算法 C++语言的实现详解
  • 2013年7月和2013年8月编程语言排行榜
  • 如何在GTK2.0下实现国际化(语言选择根据自己设置的语言,不用系统的语言)
  • 2017 年热门编程语言排行榜出炉,你的语言上榜没?
  • C语言中有指针,因此C语言可以创建链表,那么Java语言没有指针,那Java是否可以创建链表呢?
  • 苹果OS X和IOS下最新编程语言swift介绍
  • 求助,在linux下,c语言和汇编语言的接口是什么?
  • c语言判断某一年是否为闰年的各种实现程序代码
  • C语言中间语言 CIL
  • PHP编程语言介绍及安装测试方法
  • 最近学JSP,苦于HTML语言和JAVA语言太差,请教推荐几本书,thanks.




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3