归并排序
在这里插入图片描述
归并排序
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
什么是的分治（divide-and-conquer）策略：
分解：把一个问题分解成多个子问题，这些子问题是更小实例上的原问题。 解决：递归地求解子问题，当子问题足够小时，按照基础情况来求解。 合并：把子问题的解合并成原问题的解。
下面是归并排序，采用分治法的过程图，下面将对每个过程做详细说明。
在这里插入图片描述
下面使用递归对数组进行了递归分解，直到startIndex < endIndex条件不成立，才进行合并，当然，在合并之前，应完成排序，但目前我们不考虑排序，只需要看懂如何分解即可。
在这里插入图片描述
下面是排序示意图
在这里插入图片描述
归并操作的工作原理
归并操作的工作原理如下：
[1]申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。 [2]设定两个指针，最初位置分别为两个已经排序序列的起始位置 [3]比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 [4]重复步骤3直到某一指针超出序列尾 [5]将另一序列剩下的所有元素直接复制到合并序列尾
注意：归并排序不是原址的，它必须将整个输入数组进行完全的拷贝，而前面说过的冒泡排序，选择排序，或者是插入排序，在任何时间都是不拷贝或者只拷贝一个数组项，而不是对整个数组的拷贝。
代码
void MergeSort(int * arr, int * arr_copy,int s,int n)
{
int min;
if (s < n)
{
min = s+(n-s) / 2;
//不要写成n/2
MergeSort(arr, arr_copy, s, min);
MergeSort(arr, arr_copy, min + 1, n);
int i = s, j = min + 1, k = s;
while (i != min + 1 && j != n + 1)
{
if (arr[i] > arr[j])
arr_copy[k++] = arr[j++];
else
arr_copy[k++] = arr[i++];
}
while (i != min + 1)
{
arr_copy[k++] = arr[i++];
}
while (j != n + 1)
{
arr_copy[k++] = arr[j++];
}
for (i = s; i <= n; i++)
{
arr[i] = arr_copy[i];
cout << "arr" << i << "是" << arr[i]<<endl;
}
cout << endl;
}
}
int main()
{
int arr[] = { 1,5,69,8,10,6 };
int arr_copy[6] = { 0 };
//将数组分解,排序
//原数组，复制数组 数组长度
MergeSort(arr, arr_copy,0,5);
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-02-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录