[分享]归并排序讲解

小可爱～

有理解错误的地方请见谅并指出错误, 一起进步
归并算法核心思想
         先对数组折半分组, 分到每一个元素时, 将元素视为有序数列
         再将相邻的所谓的有序数列使用默置合并成一个有序数列


而分组的过程一般使用函数递归实现的, 所以这里介绍一种思想看看什么是函数递归
这是一个简单的函数递归累加

[C] 纯文本查看 复制代码

int add(int a)
{
        int w = 1;
        if (a == w)
        {
                return w;
        }
        else
        {
                return add(a - 1) + a;
        }
}

再看看这两个函数

[C] 纯文本查看 复制代码

int add1(int a)
{
        int w = 1;
        if (a == w)
        {
                return w;
        }
        else
        {
                return add2(a - 1) + a;
        }
}

int add2(int a)
{
        int w = 1;
        if (a == w)
        {
                return w;
        }
        else
        {
                return add1(a - 1) + a;
        }
}

现在你知道什么是函数递归了么?




说白了函数递归就是自己调用自己, 一次一次return 出自己的值给自己用, 知道最后将值返回给主函数用




现在理解这个函数还难么???

[C] 纯文本查看 复制代码

void MSort(int *src, int low, int high, int *des)
{
        if (low < high)
        {
                int mid;
                mid = (low + high) / 2;
                MSort(src, low, mid, des);
                MSort(src, mid + 1, high, des);
                Merge(src, low, mid, high, des);
        }
}

上面这个函数就是通过函数递归来分组
每次调用 MSort 就是调用自己
比如: MSort(src, low, mid, des);
这个时候可以尝试着将下面的 MSort(src, mid + 1, high, des); 屏蔽不看
就会看到
(1)MSort(src, low, mid, des);
对于(1)这个函数来说  这里的mid就是 high 而这个high在不断的借助mid 在缩小直到 low < high 不满足后开始返回 不断的将值传给自己
而且在每次调用MSort函数来看, 每次这个函数都会调用Merge(src, low, mid, high, des); 进行默置, 就是将两个有序数列合并
从 low 小于 high  1 到low小于high  2 一直到 ....
每次都会调用 Merge(src, low, mid, high, des);
也就是说 从单个元素开始归并 一直归并到 mid 最后到整个数组都被归并
(2)Merge(src, low, mid, high, des);
下面这段代码可以看出它在默置

[C] 纯文本查看 复制代码

        while (l <= m && i <= h)
        {
                if (src[l] <= src[i])
                {
                        des[k++] = src[l++];
                }
                else
                {
                        des[k++] = src[i++];
                }
        }
        //同上面代码
        //将剩余的数组再次补充到尾部
        while (l <= m)
        {
                des[k++] = src[l++];
        }
        while (i <= high)
        {
                des[k++] = src[i++];
        }

下面的断码可以看出它在整合, 将归并好的 des 整合到 src 好让 MSort 再次调用

[C] 纯文本查看 复制代码

for (int n = 0; n < k; n++)
        {
                src[low + n] = des[n];
        }

从下图中可以看出都在用 src 所以才要整合





感觉说了这么多还不如一张图

感觉说了这么多还不如一张图

[C] 纯文本查看 复制代码

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>																					  
// 这是将两个有序的数组合并成一个数组的方法
// void MemeryArray(int *a, int n, int *b, int m, int *c)
// {
// 	int i, j, k;
// 	i = j = k = 0;
// 	while (i < n && j < m)
// 	{
// 		if (a[i] < b[j])
// 		{
// 			c[k++] = a[i++];
// 		}
// 		else
// 		{
// 			c[k++] = b[j++];
// 		}
// 	}
// 	//将剩余的数组再次补充到尾部
// 	while (i < n)
// 	{
// 		c[k++] = a[i++];
// 	}
// 	while (j < m)
// 	{
// 		c[k++] = b[j++];
// 	}
// }

//看看所谓的函数递归是什么?

// int add(int a)
// {
// 	int w = 1;
// 	if (a == w)
// 	{
// 		return w;
// 	}
// 	else
// 	{
// 		return add(a - 1) + a;
// 	}
// }
// 
// int add1(int a)
// {
// 	int w = 1;
// 	if (a == w)
// 	{
// 		return w;
// 	}
// 	else
// 	{
// 		return add2(a - 1) + a;
// 	}
// }
// 
// int add2(int a)
// {
// 	int w = 1;
// 	if (a == w)
// 	{
// 		return w;
// 	}
// 	else
// 	{
// 		return add1(a - 1) + a;
// 	}
// }


//从上面的函数推演出下面这段函数
//默置
void Merge(int *src, int low, int mid, int high, int *des)
{
	int l = low;
	int m = mid;
	int h = high;
	int i = mid + 1;
	int k = 0;

	while (l <= m && i <= h)
	{
		if (src[l] <= src[i])
		{
			des[k++] = src[l++];
		}
		else
		{
			des[k++] = src[i++];
		}
	}
	//同上面代码
	//将剩余的数组再次补充到尾部
	while (l <= m)
	{
		des[k++] = src[l++];
	}
	while (i <= high)
	{
		des[k++] = src[i++];
	}
	//这里的作用是 将排序好的数组里面的值整理出来放在src中, 好让函数
	//MSort(src, low, mid, des); 继续调用
	for (int n = 0; n < k; n++)
	{
		src[low + n] = des[n];
	}
}

void MSort(int *src, int low, int high, int *des)
{
	if (low < high)
	{
		int mid;
		mid = (low + high) / 2;
		MSort(src, low, mid, des);
		MSort(src, mid + 1, high, des);
		Merge(src, low, mid, high, des);
	}
}

void MergeSort(int *pArray, int len)
{
	int *p = NULL;
	p = (int *)malloc(sizeof(int) * len);
	if (NULL == p)
	{
		return;
	}
	MSort(pArray, 0, len - 1, p);
	free(p);
}

void printArray(int *pArray, int len)
{
	int i = 0;

	for (i = 0; i < len; i++)
	{
		printf("%d ", pArray[i]);
	}
	puts("");
}

int main(int argc, char *argv[])
{
	int ret = 0;
	//int sum = add1(10);
	//printf("sum = %d\n", sum);
	int buf[] = { 5, 64, 531, 23, 15, 3, 2, 1, 53, 4, 8, 6, 5, 31, 2, 38, 4 };
	int len = sizeof(buf) / sizeof(buf[0]);
	printArray(buf, len);
	MergeSort(buf, len);
	printArray(buf, len);
	system("pause");
	return ret;
}

小可爱～

有错误的地方, 还望海涵, 并且请指出错误, 一同进步这些代码都是我以前学习的时候写的, 这次拿出来, 不仅仅是为了分享, 也是为了复习

菠萝吹雪

太难理解了

m99044032

虽然看不懂，还是谢谢楼主

魔术使nqy

好难，看文字老是看不懂，我还是回去看视频了

聊胜于无丶

归是指递归，并是指合并？

wushaojienigesb

。。最近愁死了。。看算法这块。。。