关于java:持续输出面试题之算法归并排序

开篇介绍

大家好，我是 Java 最全面试题库 的提裤姐，明天这篇是数据结构与算法的第四篇，次要介绍 归并排序；在后续，会沿着第一篇开篇的常识线路始终总结上来，做到日更！如果我能做到百日百更，心愿你也能够跟着百日百刷，一百天养成一个好习惯。

归并排序

归并排序（Merge sort）是建设在归并操作上的一种无效的排序算法。该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用。
作为一种典型的分而治之思维的算法利用，归并排序的实现由两种办法：

• 自上而下的递归（所有递归的办法都能够用迭代重写，所以就有了第 2 种办法）；
• 自下而上的迭代；

算法步骤：
1、申请空间，使其大小为两个曾经排序序列之和，该空间用来寄存合并后的序列；
2、设定两个指针，最后地位别离为两个曾经排序序列的起始地位；
3、比拟两个指针所指向的元素，抉择绝对小的元素放入到合并空间，并挪动指针到下一地位；
4、反复步骤 3 直到某一指针达到序列尾；
5、将另一序列剩下的所有元素间接复制到合并序列尾。

个性：

• 工夫复杂度：O(nlogn)
• 空间复杂度：O(n)
• 稳定性：稳固

实现：

public class MergeSort {public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不扭转参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {return arr;}
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {if (left[0] <= right[0]) {result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }
}