歸並排序的C語言實現

歸並排序的核心思想是 Divide-and-Conquer 算法，即將要解決的size為n的問題，分成a個size為n/b的子問題，這些子問題的結果經過O(n^d)的時間復雜度合並，即可解決最初的問題。所以，這一類的算法，復雜度計算公式為 T(n) = a*T(n/b) + O(n^b)。

經過幾天的努力，終於將歸並排序用C語言實現了出來：

mergesort.h:

#define BUFF_SIZE 3

typedef struct _array {
        int length;
        int active;
        int *elements;
} array;

int mergesort(array *);
int merge(array , array , array *);

mergesort.c:

#include <stdio.h>
#include <stdlib.h>
#include "mergesort.h"

int main()
{
        int arr[BUFF_SIZE] = {1, 9, 3};
        array arr_main;

        arr_main.length = BUFF_SIZE;
        arr_main.active = 0;
        arr_main.elements = arr;
        mergesort(&arr_main);

        int i = 0;
        for (i = 0; i<BUFF_SIZE; i++)
        {
                printf("%d\n", arr_main.elements[i]);
        }
}

int mergesort(array *array_p)
{
        if (array_p->length > 1)
        {
                // Split the array into two part
                int size_l = array_p->length >> 1;
                int size_r = array_p->length - size_l;

                // the structure to store the left part
                array arr_l;
                arr_l.length = size_l;
                arr_l.active = 0;
                arr_l.elements = (int *)malloc(sizeof(int *) * size_l);
                int length_l = arr_l.length;
                while (length_l-- > 0)
                        arr_l.elements[length_l] = array_p->elements[length_l];

                // the structure to store the right part
                array arr_r;
                arr_r.length = size_r;
                arr_r.active = 0;
                arr_r.elements = (int *)malloc(sizeof(int *) * size_r);
                int length_r = arr_r.length;
                while (length_r-- > 0)
                        arr_r.elements[length_r] = array_p->elements[length_r + arr_l.length];

                // sort the left part of array
                mergesort(&arr_l);
                // sort the left part of array
                mergesort(&arr_r);

                // the structure to store the merge result
                array arr_m;
                arr_m.length = arr_l.length + arr_r.length;
                arr_m.active = 0;
                arr_m.elements = (int *)malloc(sizeof(int *) * arr_m.length);

                // merge the left part and right part
                merge(arr_l, arr_r, &arr_m);

                // return the sort result
                array_p->length = arr_m.length;
                int length_m = arr_m.length;
                while (length_m-- > 0)
                {
                        array_p->elements[length_m] = arr_m.elements[length_m];
                }
        }
}
int merge(array arr_l, array arr_r, array *arr_m)
{
        if (arr_l.length == 0)
        {
                if (arr_r.length == 0) return;
                // return the arr_l array
                while (arr_r.length-- > 0)
                        arr_m->elements[arr_m->active++] = arr_r.elements[arr_r.active++];

                return;
        }

        if (arr_r.length == 0)
        {
                if (arr_l.length == 0) return;
                // return the arr_r array
                while (arr_l.length-- > 0)
                        arr_m->elements[arr_m->active++] = arr_l.elements[arr_l.active++];

                return;
        }

        if (arr_l.elements[arr_l.active] > arr_r.elements[arr_r.active])
        {
                // the next elements of the merge array is bigger one
                arr_m->elements[arr_m->active++] = arr_l.elements[arr_l.active++];
                arr_l.length--;

                // recursively merge the rest array
                merge(arr_l, arr_r, arr_m);
        }
        else
        {
                // the next elements of the merge array is bigger one
                arr_m->elements[arr_m->active++] = arr_r.elements[arr_r.active++];
                arr_r.length--;

                // recursively merge the rest array
                merge(arr_l, arr_r, arr_m);
        }
}

上周日開始寫的這個程序，遇到了很多問題，也有很多收獲。只要不選擇放棄，肯定能解決遇到的問題～！