/*
*=====================================================================================
*
* Filename: merge_sort.c
*
* Description:
*
* Version: 1.0
* Created: 2011年08月16日 10时15分45秒
* Revision: none
* Compiler: gcc
*
* Author: WangRan (), Wangran51@126.com
* Company:
*
*=====================================================================================
*/
#include "stdlib.h"
#include "stdio.h"
#define MAX65535
void merge(int array[], int p, int q, int r)
{
int n1 =q-p+1;//left数组的长度
int n2 =r-q;//right数组的长度
int *left =(int *)malloc((n1+1) * sizeof(int));//多申请一个单位存放MAX
int *right =(int *)malloc((n2+1) * sizeof(int));
int i = 0;
int j = 0;
int k = 0;
/*将array中的数据存入*/
for(i=0;i<n1; i++)
{
left[i]= array[p+i];
}
for(j=0;j<n2; j++)
{
right[j]= array[q+j+1];
}
/*在数组结尾加哨兵*/
left[n1] =MAX;
right[n2] =MAX;
i = 0;
j = 0;
/*比较堆顶的两个数,当执行r-p+1次后停止,堆顶小的存入array,当一个堆存完了,则MAX在堆顶则每次都会去存另外一个堆*/
for(k=p;k<r+1; k++)//注意这里r+1
{
if(left[i]<= right[j])
{
array[k]= left[i];
i++;
}
else
{
array[k]= right[j];
j++;
}
}
free(left);
free(right);
}
void merge_sort (int array[], int p, int r)
{
int q = -1;
if (p <r)
{
q =(p+r)/2;
merge_sort(array,p, q);
merge_sort(array,q+1, r);
merge(array,p, q, r);
}
} /*----- end of function merge_sort ----- */
void main (void)
{
intarray[10]={9,8,7,6,5,4,3,2,1,0};
int p =0;//begin
int r =9;//end
int i = 0;
merge_sort(array,p, r);
for(i=0;i<10; i++)
{
printf("%d ", array[i]);
}
} /*----- end of function main ----- */
相关推荐
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"...
定义:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子...
归并排序
本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并...
实现归并排序的一个类
根据算法导论实现的归并排序算法
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
内部排序之归并排序的代码实现,代码风格简单 易于看懂
C/C++语言实现归并排序算法,递归调用,算法设计与分析。