Java——归并排序

在讲解归并排序之前，我们必须先知道什么是递归，因为在归并排序中我们用到了递归。

递归

什么是递归呢？递归方法就是直接或者间接调用自身的方法。简单来说就是自己调用自己的方法，用一个条件去控制这个递归，防止进入死循环。
用一个例子来说明递归。我们都学过阶乘，当我们计算一个一个数字的阶乘的时候不可能在程序中自己手动一个个去计算，这个时候就可以根据阶乘的规律性去写一个递归的方法：

核心方法：

if(n == 0){
  return 1;
}else{
  return n*factorial(n-1);
}

一个递归调用可以导致更多的递归调用，因为这个方法继续把每个子问题分解成新的子问题。要终止一个递归方法，问题最后必须达到一个终止条件。当问题达到这个终止条件时，就将结果返回给调用者。然后调用者进行计算并将结果返回给他自己的调用者。这个过程持续进行，直到结果传回原始的调用者为止。
关于递归更多的内容本人不过多解释，有兴趣的可以翻阅书籍，本章重点在归并排序的讲解。

归并排序

归并排序是一种比较另类一点的排序，既不属于选择排序，也不属于交换排序，更不属于插入排序。这种方法是运用分治法解决问题的类型。
归并排序的基本思想是基于合并操作，即合并两个已有的有序的序列是容易的，不论这两个序列是顺序存储的还是链式存储的，合并操作都可以在O(m+n)时间内完成（假设两个有序表的长度分别为m和n）。

思想图.png

public static void mergeSort(int[] list) {
            if(list.length > 1) {
                int[] firstList = new int[list.length/2];
                System.arraycopy(list, 0, firstList, 0, list.length/2);//把list前半部分赋值给firstList
                mergeSort(firstList);//重复调用本身的方法进行递归，不断的把数组分隔成只有一个元素的数组（前半部分）
            
                int[] secondList = new int[list.length - list.length/2];
                System.arraycopy(list, list.length/2, secondList, 0, list.length - list.length/2);
                mergeSort(secondList);
                
                int[] temp = merge(firstList,secondList);
                System.arraycopy(temp, 0, list, 0, temp.length);
            }
        }
        //对两个分隔的有序数组进行排序
        public static int[] merge(int[] first,int[] second) {
            int[] temp = new int[first.length+second.length];//新建一个新的数组，把合并的数组赋值给新的数组
            int fistposition = 0;
            int secondposition = 0;
            int tempposition = 0;
            //因为first和second是有序的，所以每次都和第一个数字进行比较
            while(fistposition < first.length && secondposition < second.length) {
                if(first[fistposition] < second[secondposition]) {
                    temp[tempposition] = first[fistposition];
                    tempposition = tempposition + 1;
                    fistposition = fistposition + 1;
                }else {
                    temp[tempposition] = second[secondposition];
                    tempposition = tempposition + 1;
                    secondposition = secondposition + 1;
                }
            }
            
            while(fistposition < first.length) {
                temp[tempposition] = first[fistposition];
                tempposition = tempposition + 1;
                fistposition = fistposition + 1;
            }
            while(secondposition < second.length) {
                temp[tempposition] = second[secondposition];
                tempposition = tempposition + 1;
                secondposition = secondposition + 1;
            }
            return temp;
        }

方法mergeSort创建一个新数组firstList，该数组是list前半部分。算法在firstList上递归调用mergeSort。firstList的length是list的length的一半，而secondList 是list的前半部分，和firstList的操作一样。在firstList和secondList 都排序好以后把他合并成一个新的数组temp。最后将temp赋给原始数组list。