数据结构 ——— 归并排序算法的实现
目录
归并排序的思想
将已经有序的子序列合并，得到完全有序的序列，即先使每个子序列有序后，再使子序列段间有序
若将两个有序表合并成一个有序表，称为二路归并
归并排序步骤示意图：
由此可以看出归并排序是需要递归分治解决的，把原数组分治成各个子序列，要先让各个子序列有序，最后才能让整个数组有序
让子序列有序的步骤是：取小的尾插
举例说明：
走到最后一步时，有两个子序列：[1,6,7,10] 和 [2,3,4,9]
这两个子序列都被分解归并为有序了，只要将这两个子序列再次归并，就能有序
所以需要两个指针，指向这两个子序列的开头，找到比较小的那个值，进行尾插
那么尾插就不能在原数组上尾插，因为会覆盖数据
所以要在最开始定义一个和待排序的数据等长的 tmp 数组，来进行尾插
最后再把 tmp 数组中的内容拷贝到原数组，这样，原数组才算完成了排序
归并排序算法的实现
代码演示：
static void _MergeSort(int* tmp, int* a, int begin, int end)
{
/*结束条件*/
if (begin == end)
return;
/*分解*/
int mid = (begin + end) / 2;
// [begin,mid] [mid+1,end]
_MergeSort(tmp, a, begin, mid);
_MergeSort(tmp, a, mid + 1, end);
/*归并*/
// 第一段子区间
int begin1 = begin;
int end1 = mid;
// 第二段子区间
int begin2 = mid + 1;
int end2 = end;
int i = begin;
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 + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int size)
{
int* tmp = (int*)malloc(sizeof(int) * size);
// 判断是否开辟成功
if (tmp == NULL)
{
perror("malloc fail");
return;
}
// 归并排序子函数
_MergeSort(tmp, a, 0, size - 1);
free(tmp);
}代码解析：
MergeSort 函数用来接收指向待排序数组首元素的指针，和数组长度
要利用 tmp 数组来接收数组 a 排好后的数据
所以不能直接利用 MergeSort 函数来递归，否则每次递归都会定义一个 tmp 函数
在 MergeSort 函数中再定义一个子函数 _MergeSort 函数，利用 _MergeSort 函数递归完成归并排序
由归并排序的思想得出，要先找出中间值，分割成两个子序列
也就是 [begin,mid] [mid+1,end] 这两个区间
所以可以得出递归的结束条件是当区间只有一个值时，就返回
当 begin == end 时，说明此时区间只有一个值
再利用 _MergeSort 函数进行递归两个子序列
然后再归并两个子序列，第一个 while 循环是把序列中小的值尾插到 tmp 中，第二、三个 while 循环是把没有走完的那个序列直接尾插到 tmp 数组后面
最后再将 tmp 数组内的有效数据个数拷贝到 a 数组相对应的位置
当递归走完后，对数组 a 的排序也就完成了
代码验证：
原文地址：https://blog.csdn.net/weixin_55341642/article/details/144071478
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！