归并排序

浏览数：25 / 时间：2015年06月08日

归并排序就是把数组A分成2个数组A1和A2,再对A1和A2也分别平分,直到不能分为止,即只有1个元素了.再依次合并.是一个分和合的过程.

代码是在ubuntu下的vim里写的.我加了很多打印,从打印结果里面可以看出程序是怎么一步一步执行的,本来要画个图的,因为没找到比较好的工具(ubuntu下),比较好是说可以画的漂亮,而且有剪切功能.

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


void mergesort(int source[], int ordered[], int startIndex, int endIndex);
void merge(int source[], int ordered[], int startIndex, int midIndex, int endIndex);


int main()
{
        int a[8] = {3,2,1,6,7,4,8,5};
        int b[8];
    int i;
    printf("排序前的乱序数组:");
    for(i = 0; i < 8; ++i)
        printf("%d ",a[i]);
    printf("\n\n");

        mergesort(a,b,0,7);

        printf("排序后的有序数组:");
    for(i = 0; i < 8; ++i)
                printf("%d ",b[i]);
        printf("\n");

        return 0;
}

void mergesort(int source[], int ordered[], int startIndex, int endIndex)
{
    if(startIndex == endIndex)
    {
        ordered[startIndex] = source[startIndex];
    }
    else
    {
        int *tmp = (int*)malloc((endIndex-startIndex+1)*sizeof(int));
        int mid = (startIndex + endIndex)/2;
        printf("(startIndex,midIndex,endIndex) = ");
        printf("(%d,%d,%d)\n",startIndex,mid,endIndex);
        mergesort(source,tmp,startIndex,mid);
        mergesort(source,tmp,mid+1,endIndex);
        
        printf("需要排序的两个数组是:");
        
        int i;
        for(i = startIndex; i <= endIndex; ++i)
        {    
            printf("%d ",tmp[i]);
            if(i == mid)
                printf("和 ");
        }
        printf("\n");
        //保证用来合并的数组有序,所以第一个参数是tmp.
        merge(tmp,ordered,startIndex,mid,endIndex);
    }
}

void merge(int source[], int ordered[], int startIndex, int midIndex, int endIndex)
{
    int i = startIndex, j = midIndex + 1,k = startIndex;
    while(i <= midIndex && j <= endIndex)
    {
        
        if(source[i] < source[j])
        {
            ordered[k++] = source[i++];
        }
        else
        {    
            ordered[k++] = source[j++];
        }
    }

    while(i<=midIndex)
        ordered[k++] = source[i++];

    while(j<=endIndex)
        ordered[k++] = source[j++];

    printf("合并后的结果是:");
    for(i = startIndex; i <= endIndex; ++i)
        printf("%d ",ordered[i]);
    printf("\n\n");
}

编译结果:

排序前的乱序数组:3 2 1 6 7 4 8 5 

(startIndex,midIndex,endIndex) = (0,3,7)
(startIndex,midIndex,endIndex) = (0,1,3)
(startIndex,midIndex,endIndex) = (0,0,1)
需要排序的两个数组是:3 和 2 
合并后的结果是:2 3 

(startIndex,midIndex,endIndex) = (2,2,3)
需要排序的两个数组是:1 和 6 
合并后的结果是:1 6 

需要排序的两个数组是:2 3 和 1 6 
合并后的结果是:1 2 3 6 

(startIndex,midIndex,endIndex) = (4,5,7)
(startIndex,midIndex,endIndex) = (4,4,5)
需要排序的两个数组是:7 和 4 
合并后的结果是:4 7 

(startIndex,midIndex,endIndex) = (6,6,7)
需要排序的两个数组是:8 和 5 
合并后的结果是:5 8 

需要排序的两个数组是:4 7 和 5 8 
合并后的结果是:4 5 7 8 

需要排序的两个数组是:1 2 3 6 和 4 5 7 8 
合并后的结果是:1 2 3 4 5 6 7 8 

排序后的有序数组:1 2 3 4 5 6 7 8