归并排序的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);
}
}

上周日开始写的这个程序,遇到了很多问题,也有很多收获。只要不选择放弃,肯定能解决遇到的问题~!

上一篇:【指南】本地如何搭建IPv6环境测试你的APP


下一篇:day038 navicat pymysql