博文
分治法的应用之一：合并排序算法
||
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
void merge(int a[], int p, int q, int r)
{
int i, j, k;
int *tmp = (int *)malloc((r - p + 1) * sizeof(int));
i = p;
j = q + 1;
k = 0;
while(i <= q && j <= r)
{
if(a[i] < a[j])
{
tmp[k] = a[i++];
}
else
{
tmp[k] = a[j++];
}
k++;
}
while(i <= q)
{
tmp[k++] = a[i++];
}
while(j <= r)
{
tmp[k++] = a[j++];
}
for (i = 0; i < k; i++)
{
a[p + i] = tmp[i];
}
free(tmp);
}
void merge_sort(int a[], int p, int r)
{
if(p < r)
{
int q = (p + r) / 2; //分解成两组
merge_sort(a, p, q); //递归的对前一组排序
merge_sort(a, q + 1, r); //递归的对后一组排序
merge(a, p, q, r); //合并结果
}
}
void main()
{
int A[10] = {5, 2, 4, 7, 1, 3, 2, 6, 6, 20};
merge_sort(A, 0, 9);
for (int i=0; i<10; i++)
{
printf("%d ", A[i]);
}
printf("nn");
}
https://blog.sciencenet.cn/blog-298201-410739.html
上一篇：严蔚敏《数据结构（C语言版）》第二章代码
