归并排序时间里在归并操作上的一种

归并排序（Merge Sort）是建立在归并操作上的一种高效排序算法。该算法是分治法（Divide and Conquer）的典型应用。归并排序的核心思想是将已有序的子序列合并，得到完全有序的序列。

归并排序的基本步骤如下：

1. 分解：将待排序序列分成若干个子序列。
2. 排序：对每个子序列进行排序。
3. 合并：将已排序的子序列合并成一个完整的有序序列。

其中，将两个有序表合并成一个有序表的过程称为二路归并。

效果图：

回放步骤：

分解：

二分用递归_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);}