1、为什么要引入归并排序
在之前介绍的排序算法中，冒泡排序和选择排序的时间复杂度过高（O(n2)）原因是因为在冒泡排序时，一轮下来进行了多次比较但是只排好了一个最大数放在尾部，在选择排序中，同样也是进行多次比较，选最小的放在了头部，这期间浪费了很多时间，多余的比较做了无用功。
至于插入排序，解决的是对比较次数进行了优化，不再进行不必要的比较。插入排序的思想类似于摸扑克牌，自左向右遍历，当遍历到新元素时，我们向前去比较（此时前面已经是有序序列了），找到第一个比它小的，就放于此处，因为算法设计的巧妙性，我们可以降低时间复杂度，在整体都有序的情况下时间复杂度最低为O(n),在整个序列都逆序的时候时间复杂度最高为O（n2)。
为了将比较次数降到最低，我们将比较范围进行了划分，小范围排序后再合并，引入了归并排序。
//插入排序
for (size_t i = 1; i < nums.size(); i++)
{
for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--)//如果不满足条件，则不执行循环
{
swap(nums,j,j-1);
}
}
2、归并排序的思想
归并排序是一种分治思想，首先将大问题划分为多个小问题，也就是将长序列经过多次划分成单个元素的序列，8变4、4变2、2变1，在1个元素时天然有序，此时不再划分而是进行合并，也就是先分后治的套路。
void mergesort(vector<int>&nums, int l, int r, vector<int>& temp)
{
if (l<r)
{
int mid = l + (r - l) / 2;
mergesort(nums, l, mid, temp);
mergesort(nums, mid + 1, r, temp);
merge(nums,l,r, temp);
}
}
在两部分合并时候，令指针i指向左侧的最左边，j指向右侧的最左边，因为两个序列在各自内部已经有序，所以i与j指向的元素肯定有一个是全局最小的，通过比较将其放到temp数组（为什么要引入额外辅助数组？）中，然后指针后移，继续比较，直到有一个序列为空时止。在谁小移谁后，如果有一个序列还没比较完即i或j没有到尾部，则将剩余的元素直接拷贝到temp数组中。这样就完成了一轮[L,R]的排序。多次递归，将得到整个有序的序列。
void merge(vector<int>&nums, int l, int r, vector<int>& temp)
{
int mid = l + (r - l) / 2;
int i = l, j = mid + 1;
int index = l;
temp.assign(nums.begin(), nums.end());
while (i<=mid&&j<=r)
{
if (nums[i] > nums[j])
{
temp[index++] = nums[j++];
}
else
temp[index++] = nums[i++];
}
while (i <= mid)
{
temp[index++] = nums[i++];
}
while (j <= r)
{
temp[index++] = nums[j++];
}
for (size_t i = 0; i < nums.size(); i++)
{
cout << temp[i]<<" ";
}
for (size_t i = l; i <= r; i++)
{
nums[i] = temp[i];
}
}
[注意]：引入temp数组的意义
我们在merge时，需要一个辅助数组来临时保存中间变量的值，如下图所示，先排1、5再排1、5、3，以此类推，因为涉及交换，如果无辅助数组，交换值的时候会对nums数组进行替换，影响下一轮排序。
3、归并排序所有代码
#include "stdafx.h"
#include<vector>
#include<iostream>
using namespace std;
//合并算法
void merge(vector<int>&nums, int l, int r, vector<int>& temp)
{
int mid = l + (r - l) / 2;
int i = l, j = mid + 1;
int index = l;
while (i<=mid&&j<=r)
{
if (nums[i] > nums[j])
{
temp[index++] = nums[j++];
}
else
temp[index++] = nums[i++];
}
while (i <= mid)
{
temp[index++] = nums[i++];
}
while (j <= r)
{
temp[index++] = nums[j++];
}
for (size_t i = 0; i < nums.size(); i++)
{
cout << temp[i]<<" ";
}
cout << endl;
for (size_t i = l; i <= r; i++)
{
nums[i] = temp[i];
}
}
//归并排序
void mergesort(vector<int>&nums, int l, int r, vector<int>& temp)
{
if (l<r)
{
int mid = l + (r - l) / 2;
mergesort(nums, l, mid, temp);
mergesort(nums, mid + 1, r, temp);
merge(nums,l,r, temp);
}
}
int main()
{
vector<int>nums = { 1,5,3,6,9,8,7,4,55,66};
vector<int>temp(nums.size());
cout << "排序前数组"<<endl;
for (size_t i = 0; i <= nums.size() - 1; i++)
{
cout << nums[i] << " ";
}
cout << endl;
cout << "----------temp数组------------"<<endl;
mergesort(nums, 0, nums.size() - 1, temp);
getchar();
return 0;
}
