归并排序（C语言）

归并排序的基本思想：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

一、步骤

1.首先，建立一个随机数组，如：以该数组为例

2.采用分治的思想对数组中的元素进行比较，将数组一份为二，midi = (left + right) / 2,分为[left,midi] [midi + 1,right]

3.重复第二步采用递归算法往深处递归，直到数组中只包含一个元素(不包含数组不存在的情况)，故递归的结束条件是left == right

4.然后函数返回到上一层，对两个数进行比较，然后按照顺序插入临时数组tmp

5.当tmp数组有序时，拷贝到原数组中结束

归并排序的思想和二叉树的后序遍历类似

图片详述：

二、代码

void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin == end)
{
return;
}

int midi = (begin + end) / 2;
//[begin,midi] [midi+1,end]，一个数组一分为二

_MergeSort(a, begin, midi, tmp);
_MergeSort(a, midi + 1, end, tmp); //后序遍历递归

int begin1 = begin, end1 = midi; //第一个数组
int begin2 = midi + 1, end2 = end; //第二个数组
int i = 0;

while (begin1 <= end1 && begin2 <= end2) //只要有一个数组为空就结束
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}

while (begin1 <= end1) //第一个数组不为空，插入到第二个数组后面
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2) //第二个数组不为空，插入到第一个数组后面
{
tmp[i++] = a[begin2++];
}

memcpy(a + begin, tmp, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp); //由于tmp是malloc出来的，因此要建立一个子函数
                                    来递归，避免每一层都需要malloc
free(tmp);
}

若看不懂，可以画图，一层一层的调试

原文地址：https://blog.csdn.net/N_N12/article/details/143804177

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！