【数据结构算法】归并排序
归并排序时间里在归并操作上的一种
归并排序（Merge Sort）是建立在归并操作上的一种高效排序算法。该算法是分治法（Divide and Conquer）的典型应用。归并排序的核心思想是将已有序的子序列合并，得到完全有序的序列。
归并排序的基本步骤如下：
- 分解：将待排序序列分成若干个子序列。
- 排序：对每个子序列进行排序。
- 合并：将已排序的子序列合并成一个完整的有序序列。
其中，将两个有序表合并成一个有序表的过程称为二路归并。
效果图：
回放步骤：
分解：
二分用递归_MergeSort（结束条件：lefd≥right）分到只有一个元素为止
递归左区间，递归右区间
begin1：每个区间开始
end1：每个左区间结束
begin2：每个右区间开始
end2：每个右区间结束
tmp和原数组一样大
mid=（left+right）/2
合并：合并时，重新创建一个数组数组，下标index，二分完之后，将排序完的元素放到临时数组内，然后拷贝到原数组
- 先调顺序在合并，放回的时候根据下标区间放回合并，左区间【 left，mid】右区间【mid+1，right】
- 合并完之后，向上回溯，继续排序，两个有序数组合并
- 循环，递归结束。
- 注意，递归到底之后，先排序，在回溯，回溯也可以认为是合并，下面可以表示总体的排序
代码
void _MergeSort(int* arr, int left,int right,int *tmp)
{
if (left>=right)
{
return;//结束条件
}
int mid = (left + right) / 2;
//[left,mid][mid+1,right]
_MergeSort(arr, left, mid, tmp);//不断的进行二分
_MergeSort(arr, mid+1, right, tmp);//一直二分到左区间的叶子结点，在回溯到父节点，才会执行右节点
//合并
int begin1 = left,end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 < end1 && begin2 < end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2];
}
//把tmp中的数据拷贝到arr中
for (int i = left; i < right; i++)
{
arr[i] = tmp[i];
}
}
int MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int));
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
