蓝桥杯---归并排序算法题目（leetcode第912题）

1.题目概述

还是最基础款的这个排序数组的这个题目：之前我们是使用的快速排序的思路，也就是数组划分为三块，实现了快排的过程；

这次我们是介绍分治思想里面的另外的一个排序的方法：就是归并排序

2.算法原理的介绍

快速排序：数组分为三块，随机选择基准元素，然后就开始排序了；

归并排序：确定这个mid数值，对于这个mid的左右两边分别进行排序，最后合并，依次递归下去，在这个基础上面继续划分下去；

下面举一个例子说明一下这个过程：

这个过程其实是很容易理解的，就是不断的对半排序，对半排序，知道这个排序结果可以看出来，然后再向上进行合并的过程；

3.代码的详细说明

• 我们还是封装了一个函数mergeSort，翻译就是合并排序，merge就是合并的意思，因此这个函数的名字就是归并排序；
• 这个里面其实就有递归的思想，函数里面调用函数自己，就是我们的这个mergesort函数里面再次调用这个mergesort函数本身；
• 我们的这个mid把我们的这个整体的数组划分为两个部分，下标分别是这个left到mid，和mid+1到right两个区间；
• 两边排序完成之后，就要进行这个合并的过程了，实际上这个过程很简单：两个区间left,right双指针遍历，创建一个临时的数组，小的放到我们的数组里面去；
• 这个里面使用的是三目运算符的语法，比较之后cur1++,cur2++,i++,i表示的是我们的临时数组下标，cur1和cur2分别表示的左右两边的数组的下标；
• 当我们的某一边遍历完成的时候，剩下的本来就是有序地，直接挪动即可，比如1 2 3 5 4 6 7 8，四个是一组，两边的比较，进入临时数组的顺序分别是1 2 3 4 5，这个时候左边的这个cur1便利的内容结束了，我们的右边的cur2遍历的内容直接放到我们的临时数组里面就可以了；
• 但是因为这个最后的返回值是我们的Nums数组，所以需要挪一下，就是把temp数组元素挪到nums里面去，使用j控制这个过程，因为这个j是从left到right，nums【j】就等于这个temp数组的每一个元素，一次复制，赋值是从第一个元素开始的，因此这个temp而言，需要j-left就是0下标，也就是第一个元素；

4.代码的小小优化

• 这个优化主要是针对于我们的临时数组temp而言的，因为上面的代码我们使把temp创建写在了mergesort里面，因此只要调用这个函数，就需要新开辟空间，这个时候空间开销很大；
• 优化做法，就是把这个数组的创建写在全局的，在sortArray里面开创空间，这个时候可以降低算法的空间复杂度，减小空间资源的消耗；