排序算法——归并排序

归并排序基本思想

归并排序的是分治法的一个典型体现。

分治法的核心思想在于——将一个复杂的问题分解，化为多个相同或相似的子问题，然后进一步将子问题分解，直至能够将问题直接求解，在得到子问题的解后，将其归并，便得到了原来复杂问题的解。

由分治法的思想可以看出，归并排序的本质就是将数组的元素划分开来，分解成一个个单独的个体，然后进行整理排序，最后再合成一个整体。

举例详解

以一个无序数组：8，9，7，11，4，1，14，84，3，18，21为例

归并排序的第一步，就是将这个无序数组进行分解

首先将数组一分为二：

->  8，9，7，11，4，1        |      14，84，3，18，21

两边同步继续分解：

->  8，9，7      |      11，4，1            14，84，3    |      18，21

->  8，9，7      |      11，4，1            14，84，3    |      18，21

->  8，9    |    7            11，4    |    1            14，84   |     3           18     |      21

分解直至原数组所有的元素都变成一个单独的个体：

->  8    |   9       7           11    |    4       1         14     |     84         3         18         21

最终分解如下：

8         9       7        11        4        1        14          84        3         18        21

以上就是归并排序第一部分分解元素的过程

而用代码来实现的话

//分解数组
//arr:无序数组，在c++中作为形参时被弱化成指针形式
//left:当前长度数组首个元素的下标
//right:当前长度数组最后一个元素的下标
void divided(int*arr,int left,int right)
{
    //递归退出条件：分解到只有一个元素
    if(left>=right)
    {
        return;
    }
    //数组的中间点
    int mid = (left + right)/2;
    //左边继续分解
    divided(arr,left,mid);
    //右继续分解
    divided(arr,mid +1,right);
}
​

在分解完以后，第二步便是将所有的元素归并

在之前的分解过程中，由于每个分解出的子数组有且只有一个元素，因此，对于每个子数组来说，它们都是有序的

而归并，则就是要让两个数组都有序的情况下，使其在合并后依然保持优序

以刚才分解完后的数组为例：

8     9    7     11     4     1     14       84     3      18     21

选取最后一次分解时的各节点进行合并

->  8   |  9       7       11  |  4      1      14    |   84      3    18   |   21

两个子数组进行比较，然后各自合并

在这以降序排序为例：

8比9小所以合并后8排在9后面，由于与7进行比较的另一个子数组不存在，因此7依旧为单个，同理，完成其他子数组之间的合并

第一次归并后结果如下所示

->9，8     7      11，4     1     84，14     3     21，18

由此返回了上一层的排序

第二次继续合并

两两数组相互合并

->9，8   |   7     11，4  |   1     87，14  |   3      21，18

结果如下：

->9，8，7     11，4，1       87，14，3          21，18

继续合并：

->9，8，7  |   11，4，1      87，14，3   |    21，18

第三次合并结果：

->11，9，8，7，4，1         87，21，18，14，3

第四次合并：

-> 11，9，8，7，4，1  |   87，21，18，14，3

结果如下：

->  87，21，18，14，11，9，8，7，4，3，1

由此，将一个个子数组合并为一个数组，归并完成

用代码实现则如下所示：

//合并数组
//arr :左右两边各自有序的一个数组
//start：第一个有序数组的首元素下标
//mid：第一个数组的尾元素下标，+1后是第二个有序数组的首元素下标
//end：第二个数组的尾元素下标
void merge(int *arr,int start, int mid, int end)
{
    //创建临时数组存储归并后数组的值
    int *ptempArr = new int[end - start +1];
    //左边有序数组的首元素的下标
    int i = start;
    //右边有序数组首元素的下标
    int j = mid +1;
    //临时数组要存储的元素的位置的下标
    int k = start;
    //当左数组和右数组当前下标皆有值时
    while(i<=mid && j<=end)
    {
        //将值更大的那个存储进去
        if(arr[i] > arr[j])
        {
            ptempArr[k++] = arr[i++];
        }
        else
        {
            ptempArr[k++] = arr[j++];
        }
    }
    //若循环结束后左数组依旧有值时，将剩下的元素添加至临时数组的尾端
    while(i<=mid)
    {
        ptempArr[k++] = arr[i++];
    }
    //若循环结束后右数组依旧有值时，将剩下的元素添加至临时数组的尾端
    while(j<=end)
    {
        ptempArr[k++] = arr[j++];
    }
    //将排序后的元素返回整合到原数组中去
    for(int i = 0; i< k;i++)
    {
        a[start + i] = ptempArr[i];
    }
    //释放堆区内存，防止造成内存泄漏
    delete[] ptempArr;
}

整体代码

由以上两个步骤，我们最终得出了归并排序的代码

如下所示：

void mergeSort(int *arr,int left,int right)
{
    if(left>=right)
    {
        return;
    }
    int mid = (left + right)/2;
    mergeSort(arr,left,mid);
    mergeSort(arr,mid + 1,right);
    //执行归并
    merge(arr,left,mid,right);
}
void merge(int *arr,int start, int mid, int end)
{
    int *ptempArr = new int[end - start +1];
    int i = start;
    int j = mid +1;
    int k = start;
    while(i<=mid && j<=end)
    {
        if(arr[i] > arr[j])
        {
            ptempArr[k++] = arr[i++];
        }
        else
        {
            ptempArr[k++] = arr[j++];
        }
    }
    while(i<=mid)
    {
        ptempArr[k++] = arr[i++];
    }
    while(j<=end)
    {
        ptempArr[k++] = arr[j++];
    }
    for(int i = 0; i< k;i++)
    {
        a[start + i] = ptempArr[i];
    }
    delete[] ptempArr;
}