算法---7.归并排序

1. 归并排序

1.2 代码

#include <stdio.h>
#include <stdlib.h>
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
#define SWAP(x,y) (x=(x)+(y),y=(x)-(y),x=(x)-(y))
int dump_array(int* arr, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}
void merge(int* arr, int* temp, int first, int mid, int last)
{
    int i=first, j=mid+1;
    int m=mid, n = last;
    int k=0;
    printf("first=%d=%d,mid=%d=%d,last=%d=%d\n", first, arr[first], mid, arr[mid], last, arr[last]);
    while( (i<=m) && (j<=n) )
    {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    printf("in mid dump\n");
       dump_array(temp, k);
    while(i<=m)
        temp[k++] = arr[i++];

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

    printf("in last dump\n");
       dump_array(temp, k);
    for(i=0; i<k; i++)
        arr[first + i] = temp[i];
}
void msort(int* arr, int* temp, int first, int last)
{
    if (first<last)
    {
        int mid = (first + last)/2;
        msort(arr, temp, first, mid); //left
        msort(arr, temp, mid + 1, last); //right
        merge(arr, temp, first, mid, last); //merge left right
    }
}

int merge_sort(int* arr, int len)
{
    int *temp = (int*) malloc(sizeof(int)*len);
    if (temp == NULL)
        return -1;
    msort(arr, temp, 0, len-1);
    free(temp);
    return 0;
}

int main ( int argc, char *argv[] )
{
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    //int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int len = sizeof(arr)/sizeof(int);
    dbmsg("array len=%d", len);
    dump_array(arr, len);
    merge_sort(arr, len);
    printf("after HeapSort\n");
    dump_array(arr, len);
    return EXIT_SUCCESS;
}

1.3 运行结果

merge.c:main[68]: array len=10
49 38 65 97 76 13 27 49 55 4
first=0=49,mid=0=49,last=1=38
in mid dump
38
in last dump
38 49
first=0=38,mid=1=49,last=2=65
in mid dump
38 49
in last dump
38 49 65
first=3=97,mid=3=97,last=4=76
in mid dump
76
in last dump
76 97
first=0=38,mid=2=65,last=4=97
in mid dump
38 49 65
in last dump
38 49 65 76 97
first=5=13,mid=5=13,last=6=27
in mid dump
13
in last dump
13 27
first=5=13,mid=6=27,last=7=49
in mid dump
13 27
in last dump
13 27 49
first=8=55,mid=8=55,last=9=4
in mid dump
4
in last dump
4 55
first=5=13,mid=7=49,last=9=55
in mid dump
4 13 27 49
in last dump
4 13 27 49 55
first=0=38,mid=4=97,last=9=55
in mid dump
4 13 27 38 49 49 55
in last dump
4 13 27 38 49 49 55 65 76 97
after merge sort
4 13 27 38 49 49 55 65 76 97

1.4 分析
49 38 65 97 76 13 27 49 55 4  第一趟(49)(38)    (97)(76)     (13)(27)    (55)(4)       

49 38 65 97 76 13 27 49 55 4  第二趟 (49,38)(65)           (13,27)(49) 

49 38 65 97 76 13 27 49 55 4  第三趟(49,38,65)(97,76)         (13,27,49)(55,4)   

49 38 65 97 76 13 27 49 55 4  第四趟(49,38,65,97,76) (13,27,49,55,4) 

4 13 27 38 49 49 55 65 76 97   完成后就是结果了