mergesort.c

二路合并排序算法

#include "Stdio.h"
#include "stdlib.h"

#define NUM 100

void MergeSort();
void Merge();

int main(void)
{
    int i;
    int source[NUM];
    int target[NUM];

    for(i=0; i<NUM; i++){
        source[i] = rand() % 100;
        printf("%3d ", source[i]);
    }
    printf("\n");
    MergeSort(source, target, 0, NUM-1);
    for(i=0; i<NUM; i++){
        printf("%3d ", target[i]);
    }
    printf("\n");

    getch();
    return 0;
}

/*二路合并排序算法，使用分治策略,时间复杂度O(nlog2n),
需要和待排记录等数量的辅助空间，是一种稳定的排序算法。*/
void MergeSort(int source[], int target[], int s, int t)
{
    int middle;
    int temp[NUM];
    if(s == t){
        target[s] = source[s];
    }
    else{
        middle = (s + t)/2;
        MergeSort(source, temp, s, middle);
        MergeSort(source, temp, middle+1, t);
        Merge(temp, target, s, middle, t);
    }
}
/*将两个内部已排好序的序列合并成一个序列*/
void Merge(int temp[], int target[], int s, int middle, int t)
{
    int j;
    int k;
    int i;

    for(j=middle+1, k=s; s<=middle && j<=t; ++k){
        if(temp[s] < temp[j]){
            target[k] = temp[s++];
        }
        else{
            target[k] = temp[j++];
        }
    }
    if(s <= middle){
        for(i=s; i<=middle; i++){
            target[k++] = temp[i];
        }
    }
    if(j <= t){
        for(i=j; i<=t; i++){
            target[k++] = temp[i];
        }
    }
}