学步园

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。

　　如　设有数列{6，202，100，301，38，8，1}

　　初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数

　　i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　3

　　i=2 [ 6 100 202 301 ] [ 1 8 38 ]　4

　　i=3　[ 1 6 8 38 100 202 301 ] 4

　　总计：　11次

c语言实现如下：

#include <stdio.h>
#include <string.h>
#include <malloc.h>

void display(int array[],int size){
        printf("the array is:");
        int i;
        for(i=0;i<size;i++){
                printf("%d ",array[i]);
        }
        printf("\n");
}

//将a数组中first开始mid结束的数组，mid+1开始last结束的数组 进行合并，再存放回a中
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}

void sort(int a[], int first, int last, int temp[]){
        if (first < last)
    {
        int mid = (first + last) / 2;
	//左侧的数组进行排序
        sort(a, first, mid, temp);
	//右侧的数组进行排序
        sort(a, mid + 1, last, temp);
	//将左右数组进行合并
        mergearray(a, first, mid, last, temp);
    }
}

int main(void){
        int array[10]={34,45,1,39,21,68,65,100,4,51};
        display(array,10);
	//申请临时数组，用于存放合并的数组
        int* temp = (int *)malloc(sizeof(int)*10);
        memset(temp,0,10);
	//归并算法函数
        sort(array,0,10-1,temp);
	free(temp);
	temp = null;
        display(array,10);
        return 0;
}