归并排序算法(思路分析) [数据结构][Java]

归并排序算法(思路分析)

归并排序介绍:

归并排序(MERGE-SORT)是利用归并的思想实现的排序方式,该算法采用经典的分治策略,分治法(divide-and-conquer)中先将问题分(divide)成一些小的问题,然后递归求解,而治(conquer)的阶段是将分的阶段得到的各个答案"修补"在一起,即分而治之.

归并排序算法示意图:

• 可以看到这种结构像是一种完全二叉树,我们这里的归并排序算法是使用递归来实现的,当然我们也可以通过迭代来实现

归并排序算法思路分析:

归并排序我们分成两个部分来讲(“分” 和 “治”):

• 我们先来讲"分"的部分: 我们先拿到一个带排序数组,我们要定义一个变量 left来记录数组中的最左侧的元素的下标,然后再通过一个变量right来记录数组中最右边元素的下标,然后还要定义一个数组类型的临时变量temp,这个temp会作为参数继续传入到我们的"治"的操作中去,因为我们在分的过程中其实是使用不到我们的temp数组的,我们只有在治的过程中才会使用到我们的临时变量数组,因为我们是在"分"的方法中调用"治"的方法,所以我们只能是通过将变量声明在方法中的方法形参的位置 – > 这样我们就可以在外界调用这个分的方法的时候就传入一个临时的创建好的数组,然后我们再最终将这个临时数组传入到我们的"治"的方法中被使用

  • 注意 : 上面我们说的这些变量都是一些方法的形参变量 ( 待排序数组 , 分序列的左位置 , 分序列的右位置, 以及临时数组)

    • 那么这些为什么要作为方法的形参变量,不能直接声明在方法的里面?
      • 因为这些变量值我们都是要通过用户传入的,我们不能知道这些值是多少,比如我们的待排序数组我们那里能知道用户的待排序数组是什么? --> 我们显然是不知道的,但是有的人这个时候会说: 那么我们的分序列的左位置和我们的分序列的右位置我们按理是可以知道的呀?
        • 真的吗?
          • 其实不是的,我们的左位置和右位置的变换方式我们的确是知道的,但是这个时候我们的左位置是从哪里开始的,我们的右位置又是从哪里开始的? --> 这个显然就不知道,我们即使可以通过用户传入的参数知道,但是这个时候我们是使用的"递归",我们使用递归的时候递归的内部只能是一些我们的通用操作 -> 那么如果我们第一次调用的时候我们自己获取分序列的左位置和右位置,那么第二次呐? 我们这个时候不能获得,通过获得的值是一个错的值,我们只能是在第一次的基础上变换,这个时候说明我们这个想法就是错的,所以我们只能是将我们的分序列的左位置和右位置通过形参位置传入进来
            • 这个时候我们得出一个结论: 如果我们是在递归中遇到了第一次可以获得的值,但是第二次不能获得的值,这个时候我们就要将这个值的获得放到方法的形参处

  • 我们在分的时候还要定义一个临时变量mid,这个mid的值是我们的(left+right)/2,这个mid就是中间索引,因为我们每次都要将一个序列分为两个分序列,这个时候我们要如何分?

  • 这个时候我们只能是通过中间位置隔开,我们一般都是将中间位置归到左边,所以如果是原本的left - mid之间的我们就看做是一个新的序列(左边的), 如果是mid +1 到原本的right之间的我们就看做是另一新序列(右边的) ,这个时候只用一只递归,知道递归到我们的待"分"的序列的left和right是相等的的时候,这个时候我们就不用再分了,因为这个时候我们已经是将我们的一个大的序列分为了多个分序列为了

    • 但是注意: 我们的分操作中的mid临时变量是用通过治操作的形参位置传入的,我们的治操作中每次都要使用对应的mid值

• 这个时候当我们的每个分序列中都是只有一个元素的时候这个时候我们的分就完成了这个时候就要进行治的操作了,那么我么的治的操作是在哪里进行? 又是如何进行? 下面我们就来一一进行分析:

  • 我们的"治"的操作在哪里进行?

    • 这个时候我们就要思考一个问题了: 我们的归并排序中真的是"分"的操作彻底完成了之后才开始"治"的操作?

      • 其实是不对的,我们在算法实现的时候可以发现我们的归并排序其实是在"分"的过程中嵌套了"治"的操作,那么是如何嵌套的?又是嵌套在了那里?

        • 这里我们可以思考: 我们说过了: 我们这里是要通过使用递归来实现归并排序的,这个时候我们如果是使用递归,我们如果是先向左递归,然后向右递归,这个时候我们的向左递归就会一直执行,知道执行到我们的左边最后一次分序列中只有一个元素为止,这个时候才会退出最后一次的左递归,这个时候才会执行我们的右递归,这个时候右递归是从下往上执行的,因为我们已经进入到了很深的一个栈中,我们的栈中有很多我们的递归调用的方法,而我们的这个右递归是在最深的左递归中调用的,这个时候我们的这一次就是只执行一次右递归,执行之后就会发现这个分序列中就是满足只有一个条件了

          • 这个时候其实我们已经有了一组待"治"的序列了,这个时候其实我们就是执行治操作的时候了 —> 那么这个是一个什么时候?

            • 这个就是左递归执行完,然后右递归执行一次的时候,那么在算法中什么是左递归执行完,右递归开始执行的时候?

              • 其实就是将我们的"治"的操作放到我们的左递归和右递归的后面

                • 这个时候有的人可能又会问: 我们将"治"的操作放到了左递归和右递归的后面,这个时候不应该是左递归和右递归都执行完之后才执行我们"治"的操作?