c语言归并排序

1.源码实现

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

#define min(x, y) ((x < y ? x : y))

/* 归并排序: 迭代法 
 * 1.申请空间, 使其大小为两个已经排序序
 *   列之和, 该空间用来存放合并后的序列
 * 2.设定两个指针, 最初位置分别为两个已
 *   经排序序列的起始位置.
 * 3.比较两个指针所指向的元素, 选择相对
 *   较小的元素放入到合并空间, 并移动指
 *   针到下一位置.
 * 4.重复步骤3, 直到某一指针到达序列尾.
 * 5.将另一序列剩下的所有元素直接复制到
 *   合并序列尾.                         */

void merge(int *arr, int len)
{
    int *a = arr;
    int *b = (int *)malloc(len * sizeof(int));  /*步骤1*/
    int seg;
    int start;
    int i;
    int *temp;

    for(seg=1; seg<len; seg+=seg)
    {
        for(start=0; start<len; start+=seg+seg)
        {
            int low = start;
            int mid = min(start+seg, len);
            int high = min(start+seg+seg, len);
            int k = low;

            /*步骤2*/
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;

            /*步骤3和步骤4*/
            while(start1 < end1 && start2 < end2)
            {
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            }

            /*步骤5*/
            while(start1 < end1)
            {
                b[k++] = a[start1++];
            }

            /*步骤5*/
            while(start2 < end2)
            {
                b[k++] = a[start2++];
            }
        }

        temp = a;
        a = b;
        b = temp;
    }

    if(a != arr)
    {
        for(i=0; i<len; i++)
        {
            b[i] = a[i];
        }

        b = a;
        a = arr;
    }

    free(b);
}

void print(int *a, int n)
{
    int i = 0;

    for(i=0; i<n; i++)
    {
        printf("%d ", a[i]);
    }

    printf("\n");
}

int main()
{
    int a[] = {40, 8, 15, 18, 12};

    merge(a, 5);

    print(a, 5);

    return 0;
}

2.编译源码

$ gcc -o example example.c -std=c89

3.运行及其结果

$ ./example
8 12 15 18 40