[分享]归并排序讲解
本帖最后由 小可爱～ 于 2016-10-26 12:20 编辑有理解错误的地方请见谅并指出错误, 一起进步 {:1_919:}
归并算法核心思想
先对数组折半分组, 分到每一个元素时, 将元素视为有序数列
再将相邻的所谓的有序数列使用默置合并成一个有序数列
而分组的过程一般使用函数递归实现的, 所以这里介绍一种思想看看什么是函数递归
这是一个简单的函数递归累加
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;
}
}
现在你知道什么是函数递归了么?
说白了函数递归就是自己调用自己, 一次一次return 出自己的值给自己用, 知道最后将值返回给主函数用
现在理解这个函数还难么???
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 小于 high1 到low小于high2 一直到 ....
每次都会调用 Merge(src, low, mid, high, des);
也就是说 从单个元素开始归并 一直归并到 mid 最后到整个数组都被归并
(2)Merge(src, low, mid, high, des);
下面这段代码可以看出它在默置
while (l <= m && i <= h)
{
if (src <= src)
{
des = src;
}
else
{
des = src;
}
}
//同上面代码
//将剩余的数组再次补充到尾部
while (l <= m)
{
des = src;
}
while (i <= high)
{
des = src;
}
下面的断码可以看出它在整合, 将归并好的 des 整合到 src 好让 MSort 再次调用
for (int n = 0; n < k; n++)
{
src = des;
}从下图中可以看出都在用 src 所以才要整合
感觉说了这么多还不如一张图
#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 < b)
// {
// c = a;
// }
// else
// {
// c = b;
// }
// }
// //将剩余的数组再次补充到尾部
// while (i < n)
// {
// c = a;
// }
// while (j < m)
// {
// c = b;
// }
// }
//看看所谓的函数递归是什么?
// 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 <= src)
{
des = src;
}
else
{
des = src;
}
}
//同上面代码
//将剩余的数组再次补充到尾部
while (l <= m)
{
des = src;
}
while (i <= high)
{
des = src;
}
//这里的作用是 将排序好的数组里面的值整理出来放在src中, 好让函数
//MSort(src, low, mid, des); 继续调用
for (int n = 0; n < k; n++)
{
src = des;
}
}
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);
}
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);
printArray(buf, len);
MergeSort(buf, len);
printArray(buf, len);
system("pause");
return ret;
}
本帖最后由 小可爱～ 于 2016-10-26 12:23 编辑
有错误的地方, 还望海涵, 并且请指出错误, 一同进步{:1_921:}这些代码都是我以前学习的时候写的, 这次拿出来, 不仅仅是为了分享, 也是为了复习
太难理解了{:1_937:} 虽然看不懂，还是谢谢楼主 好难，看文字老是看不懂，我还是回去看视频了 归是指递归，并是指合并？ 。。最近愁死了。。看算法这块。。。
页:
[1]