归并排序（merge_sort）的C语言实现

时间：2011-01-08 来源：天地玄黄

一、归并排序算法

算法的递推关系：一个大的数列需要排序，把它从中间分成两部分，每一部分归并排序，然后把排好序的这两个部分再合并起来（合并的时候需要排序）。

算法的Base Case：如果分成的这部分只有一个数，那么这个部分就不用再排序（看做已经排好序的）。

实现这个算法用了三个函数，每个函数在一个文件中，分别为：merge.c sort.c 和 main.c，其中merge.c实现的是合并的方法，sort.c实现的是排序的方法，main.c是一个测试实例。还有三个头文件，分别指出了函数原型。

merge.c：

/*This is a merge program.
 *  Given an integer ARRAY and three numbers which indicate the begain
 *and the end of two subarrays, merge the two subarrays to a bigger
 *one. The two subarrays are alrealy sorted from small to big.
 *  For example, given an array a[10] and three numbers 0, 3 and 5. The
 *first array is from a[0] to a[2], the seconde array is from a[3] to 
 *a[4]. The number 3 and 5 are the upper side. This program merge the 
 *two arrays together.
 *
 *Author:    Eric
 *Time:        2011.01.08
 */
#include <stdio.h>
#include <stdlib.h>

#include "main.h"

void merge(int *a, int idxa, int idxb, int idxc)
{
    int i = idxa, j = idxb, k = 0;
    int total = idxc-idxa;
    //int temp[total] = {0};
    int *temp = (int *)malloc(sizeof(int) * total);
    if(temp == NULL)
    {
        fprintf(stderr, "malloc error in merge function\n");
        return;
    }
    while(i < idxb && j < idxc)
    {
        if(a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    if(i == idxb)
    {
        while(j < idxc)
            temp[k++] = a[j++];
    }
    else if(j == idxc)
    {
        while(i < idxb)
            temp[k++] = a[i++];
    }

    /*Copy the temp to the sorce array*/
    for(i = 0, k = idxa; i < total; k++, i++)
        a[k] = temp[i];

    free(temp);
}

#ifndef MAIN
/*For test*/
int main()
{
    int a[10];
    int i = 0;
    int idxa=1, idxb=5, idxc=8;

    printf("Please input 10 numbers to the array:");
    for(i = 0; i < 10; i++)
        scanf("%d", &a[i]);
    printf("Three indexes are %d, %d and %d.\nThe first subarray is:", idxa, idxb, idxc);
    for(i = idxa; i < idxb; i++)
        printf(" %d", a[i]);
    printf("\nThe second subarray is:");
    for(i = idxb; i < idxc; i++)
        printf(" %d", a[i]);
    printf("\n");

    merge(a, idxa, idxb, idxc);
    printf("The merged array is:");
    for(i = idxa; i < idxc; i++)
        printf(" %d", a[i]);
    printf("\n");

    return 0;
}
#endif

merge.h：

/*Author:    Eric
 *Time:        2011.01.08
 */

void merge(int *a, int idxa, int idxb, int idxc);

sort.c:

/*This is a function for sorting an array useing merge.c
 *
 *Author:    Eric
 *Time:        2011.01.08
 */
#include <stdio.h>

#include "main.h"
#include "merge.h"

/*Sort array a, from a[begin] to a[upend-1]*/
void sort(int *a, int begin, int upend)
{
    int n = upend - begin; /*the number to be sorted*/
    /*The first array is a[idxa] to a[idxb-1]. The second is a[idxb] to a[idxc-1]*/
    int idxa = begin,
        idxb = ((begin+upend)%2 == 0) ? (begin+upend)/2 : (begin+upend+1)/2,
        idxc = upend;

    if(n < 2)
    {
        printf("The array elements are less than two. No need to sort\n");
        return;
    }
    else if(n == 2)
        merge(a, idxa, idxb, idxc);
    else
    {
        if(idxb-idxa > 1)
            sort(a, idxa, idxb);
        if(idxc-idxb > 1)
            sort(a, idxb, idxc);
        merge(a, idxa, idxb, idxc);
    }
}

#ifndef MAIN
#define MAIN
/*For test*/
int main()
{
    int a[10] = {1, 4, 8, 5, 10, 25, 54, 15, 12, 2};
    int i = 0;

    sort(a, 0, 10);

    printf("The sorted array is:");
    for(i = 0; i < 10; i++)
        printf(" %d", a[i]);
    printf("\n");

    return 0;
}
#endif

sort.h:

void sort(int *a, int begin, int upend);

main.c:

#include <stdio.h>

#include "sort.h"

int main()
{
    int a[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int i = 0;

    sort(a, 0, 10);

    printf("The sorted array is:");
    for(i = 0; i < 10; i++)
        printf(" %d", a[i]);
    printf("\n");

    return 0;
}