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

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

主要介绍了C语言实现排序算法之归并排序,对归并排序的原理及实现过程做了非常详细的解读,需要的朋友可以

参考下

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

件。

一、实现原理：一、实现原理：

1、算法基本思路

设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂

最后，将结果赋值的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));//用来暂存排序好的数据

newarr[p++] = arr[i++];

else

newarr[p++] = arr[j++];

}

while(i<=mid)

newarr[p++] = arr[i++];

while(j<=high)

newarr[p++] = arr[j++];

for(i=low,p=0;p<(high-low+1);i++,p++) //将结果复制到原数组当中

arr[i] = newarr[p];

* File: mergesort.c

* Time: 2014-07-19 HJJ

*/

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

static void merge1(int array[], int tmp[], int lpos, int rpos, int rend);