【排序算法】6.归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

分支思想
image.png

java 实现：

public class MergeSortTest {
    public static void main(String[] args) {
        int[] input = {2,5,4,89,20,89,6,0,54,78,2};
        int[] temp = new int[input.length];
        mergeSort(input, 0, input.length-1, temp);
        PrintUtils.print(input);
        PrintUtils.print(temp);
    }

    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        //拆分到只剩下一个元素（也就是left == right）就跳过
        if (left < right){
            /*
             * 1.拆分
             * 将数组的 left 到 right 区间的元素，逻辑上拆分为左右两部分 2,5,4,89,20,89 和 6,0,54,78,2
             */
            int middle = (right + left)/2;
            mergeSort(arr, left, middle, temp);
            mergeSort(arr, middle + 1, right, temp);
            int t = 0;
            /*
             * 2.合并
             * left 到 right 区间的元素，在逻辑上已经分为了左右两部分
             * 并且，这两个部分经过重新排列，各自都是有序的，例如：左侧是 2,4,5,20,89,89 ，右侧是 0,2,6,54,78
             * 然后，分别从左侧和右侧取出一个元素，并将采用数值小的一个放入 temp，被采用的一方再取出一个元素，和刚才未被采用的元素比较，再选一个小的放到temp
             * 再然后，如果一方的元素已经都放入到了temp，那么把另一方的元素依次放入到temp中即可（因为单个看某一侧都是有序的）
             * 最后，将temp中的元素回写到 arr 中，arr就完成了 left 到 right 区间的排序，如此往复即可完成排序
             */
            int l = left;
            int r = middle + 1;
            //从左右两侧各取出一个元素，将小的放入temp
            while (l <= middle && r <= right){
                if (arr[l] < arr[r]){
                    temp[t++] = arr[l++];
                }else {
                    temp[t++] = arr[r++];
                }
            }
            //退出循环，说明由一方已经将全部元素存入temp，需要将另一方剩余的元素存入temp
            while (l <= middle){
                temp[t++] = arr[l++];
            }
            while (r <= right){
                temp[t++] = arr[r++];
            }
            //最后将temp回写到arr
            int copyPointer = left;
            t = 0;
            while (copyPointer <= right){
                arr[copyPointer++] = temp[t++];
            }
        }
    }
}

时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 稳定性：稳定