歸并排序C語言實現MergeSort

是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide

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

#include

#include

#define MAX 0x11111111

void 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

總結

以上是生活随笔為你收集整理的c语言mergesort 参数,归并排序C语言兑现MergeSort的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。