归并排序C语言实现MergeSort

是建立在归并操作上的一种有效的排序算法。该算法是采用分治法—ivide and Conquer）的一个非常典型的应用。

算法伪码：

MERGE-SORT（A，p, r）

if p < r

then q = (p + r) / 2

MERGE-SORT（A，p, q）

MERGE-SORT（A，q+1, r）

MERGE（A，p, q, r）

下面的程序中，假设A是数组，p,r 都是整数。当然可以根据问题的实际情况加以改变。

Merge函数功能主要是将两个有序的数组合并成一个，用时为线性时间。

整个归并排序的时间复杂度为nlog(n)。

#include <stdio.h>#include <stdlib.h>#include <assert.h>#define MAX 0x11111111void Merge(int* A, int p, int q, int r){int n1 = q - p + 1;int n2 = r - q;assert(n1 >= 0 && n2 >= 0);int* ltmp = malloc(sizeof(int) * (n1 + 1));int* rtmp = malloc(sizeof(int) * (n2 + 1));int i, j, k;for(i = p, j = 0; i <= q; i++, j++){ltmp[j] = A[i]; }for(i = q+1, j = 0; i <= r; i++, j++){rtmp[j] = A[i];}ltmp[n1] = MAX;rtmp[n2] = MAX;for(i = 0, j = 0, k = p; k <= r; k++){if(ltmp[i] <= rtmp[j]){A[k] =  ltmp[i];i++;}else{A[k] =  rtmp[j];j++;}}}void MergeSort(int* A, int p, int r){assert(A);if(r > p){int q = (p + r) / 2;MergeSort(A, p, q);MergeSort(A, q + 1, r);Merge(A, p, q, r);}}int main(){int A[10] = {9, 8, 7, 4, 3, 5, 6, 1, 2, 0};int k;MergeSort(A, 0, 9);for(k = 0; k < 10; k++){printf("%d\n", A[k]);}return 0;}

参考：《算法导论》Thomas H. Cormen 等著。

wiki ：http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F