归并排序——保研刷题随记

（如果误入这篇帖子，不建议将其作为讲解帖学习，因为本质是自我复盘而非讲解向，所以比较粗糙且极有可能有错误，如发现错误，恳请指正）
归并排序的核心思想是：分而治之
顶层思想计算步骤：
1.对数组从中拆分，两边分别排序得到两个排好的数组。（分）
2.对这两个有序数组合成一个有序数组。（合）
对于1.我们采用递归思想。对于2.我们采用双指针以及一个tem数组。具体实施步骤(以升序排序为例）：分别指向两个数组的头部的指针相互比较数值，更小的那个可以放进tem，然后顺势向后移动，继续比较，以此类推最终结束于一个指针指向了该数组的最后一个，但是另一个还没有走到，这时候再加一个将另一个的剩余数直接加进tem的操作，最终实现在tem数组中得到有序数列。然后再将tem数组复制到原数组。
时间复杂度：T[n] = 2T[n/2] + O(n)->T[n] = O( nlogn )；空间复杂度：n + logn->Q(n)。
代码：
因为写成两个函数太麻烦了 这里合成一个函数：
void merge_sort(int q[], int l, int r)
{
if(l >= r)
return;
int mid = (l+r)/2, k = 0, i = l, j = mid+1, tem[r-l+1];
merge_sort(q, l, mid);
merge_sort(q, mid+1, r);
while(i<=mid&&j<=r)
{
if(q[i]<q[j]) tem[k++] = q[i++];
else tem[k++] = q[j++];
}
while(i<=mid) tem[k++] = q[i++];
while(j<=r) tem[k++] = q[j++];
for(int i = l, k = 0;i <= r; i++, k++)
{
q[i] = tem[k];
}
}