【算法】逻辑十分缜密，思路清晰的带大家一次性学会常见的排序算法系列ヾ(≧▽≦*)o。（四）归并排序-蒲公英云

【算法】逻辑十分缜密，思路清晰的带大家一次性学会常见的排序算法系列ヾ(≧▽≦*)o。（四）归并排序

✨前言✨：

算法是一个程序员的内功，能很好的体现程序员的编程思维，通过学习和掌握常见的算法，不仅能提高coding能力，还能更加容易在笔面试中脱颖而出。本专栏将记录博主刷算法题的过程，不定期的会更新一些优质的算法题。如果对大家有帮助，别忘了三连支持哟！

✨前言✨：

✨归并排序的思想✨

?归并排序的总思路?

?具体是如何归并的呢？?

✨归并排序的总代码✨

✨归并排序的时间复杂度的分析✨

✨归并排序的思想✨

?：我们常见的归并排序大都是用递归写就的。归并排序是基于比较的排序，而归并排序所有的交换都是在归并阶段完成的，所以要理解归并排序，就要在把握归并排序的总思路下，深挖掘归并的具体操作！

相信通过上述内容，大家已经知道了如何学习归并排序，那么接下来我来讲解归并的总思路。

?归并排序的总思路?

?：大家应该都熟悉递归的本质了，递归其实就是一种将问题逐步简化的方法，因此我们在写递归时一定要宏观把握，把握住化简问题的总思路。

归并排序的总思路是我们想让一个范围内有序，我们只需要将这个范围一分为二，先让这个范围内的左半部分有序，再让这个范围的右半部分有序，然后我们只需要把两个有序的序列合并成整个序列全有序（归并操作）。我们只需要沿着这个总思路，将整个数组不断二分，不断递进，直到最后一次二分导致一个半区只有一个元素时停止，我们只需要通过回溯时不断合并，最终就能让整体有序。

?具体是如何归并的呢？?

?：我们通过上述学习知道了我们在递归回溯时进行归并，而每次归并前都已经保证了左半部分和右半部分均有序，在这个前提下问题就转化成了如何将两个有序的序列合并成一个整体并保证其有序。

那如何解决这个问题呢？

这个问题很简单相信大家很快就能想到，我们知道合并出来的最小值必定在左右两部分的最小值中产生，这样我们就得到了最小值，我们再从左右两半部分中去掉这个最小值。同理可得，第二小的数值必定在此时左右两半部分中现存最小值中产生。以此类推我们就得到了，整体有序，当然因为要存放这个整体，所以我们需要开辟一个辅助数组来储存整体。

?：听到这里相信大家仍然有很多疑惑，毕竟光说不上代码永远是空架子，接下来我给出代码，希望大家能认真分析代码，并自己手敲多练几次，很多疑惑在练习中就能解决。

✨归并排序的总代码✨

#include<stdio.h>
#include<stdlib.h>
void print_arr(int arr[], int sz)
{
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
}
void merge(int arr[], int L, int M, int R)
{
    int p1 = L;
    int p2 = M + 1;
    int i = 0;
    int* help = (int*)malloc((R + 1 - L) * sizeof(int));
    while (p1 <= M && p2 <= R)
    {
        //比较左右两部分 小的放入（现存整体最小值放入）
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];//创建一个辅助数组
    }
    while (p1 <= M)
    {
        help[i++] = arr[p1++];
    }
    while (p2 <= R)
    {
        help[i++] = arr[p2++];
    }
    for (int i = 0; i < (R + 1 - L); i++)
    {
        arr[L + i] = help[i];
    }
    free(help);
    help= NULL;
}
void process(int arr[], int L, int R)
{
    if (L == R)
    {
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);//递归让左边有序
    process(arr, mid + 1, R);//递归让右边有序
    merge(arr,L,mid,R);//归并操作
}
void mergeSort(int arr[], int sz)
{
    process(arr,0,sz-1);
}
int main()
{
    //这是一次测试
    int arr[10] = { 2,7,5,1,3,9,10,2,8,4 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, sz);//归并排序
    print_arr(arr, sz);
    return 0;
}