当前位置: 编程技术>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