动画排序过程

执行流程

归并排序采用了 分治（Divide and Conquer）和 递归（Recursion）的思想（快速排序也是一样，这里你可以和快速排序比较一下他们的区别）

流程：

1. 划分：将待排序列二分，一直向下划分，直到只有一个元素为止（只有一个元素相当于已排序）
2. 合并：将已排序的两个子序列合并为一个新的有序序列（主要逻辑）

实现代码

归并排序实现代码：

/** * 归并排序 * @param arr：待排序的数组 * @param tempArr：辅助的临时数组 * @param left：最左边下标 * @param right：最右边下标 */
public static void sort(int[] arr, int[] tempArr, int left, int right) {
    // 如果只有一个元素，那么就不需要再继续划分了 （只有一个元素本身就是有序的，只需要被合并即可）
    // 如果 left<right则表示至少有两个元素，则需要继续划分 递归调用sort
    if (left < right) {
        int mid = (left+right)/2;   // 找到中间点
        // 递归划分左半区域
        sort(arr, tempArr, left, mid);
        // 递归划分右半区域
        sort(arr, tempArr, mid+1, right);
        // 将划分后的排序合并（排序的主要逻辑在这个方法里）
        merge(arr, tempArr, left, mid, right);
    }
}
/** * 将划分后的排序合并（排序的主要逻辑在这个方法里） * @param arr * @param tempArr * @param left * @param mid * @param right */
public static void merge(int[] arr, int[] tempArr, int left, int mid, int right) {
    // 标记左半区第一个未合并的元素下标
    int l_pos = left;
    // 标记右半区第一个未合并的元素下标
    int r_pos = mid+1;
    // 临时数组元素的下标
    int pos = left;
    // 合并（左半区、有半区都存在未合并的元素）
    while (l_pos<=mid && r_pos<=right) {
        if (arr[l_pos] < arr[r_pos])    // 左半区第一个未合并的元素 小于 右半区第一个未合并的元素
            tempArr[pos++] = arr[l_pos++]; // 将更小的那个数放到临时数组中 且pos、l_pos下标后移
        else
            tempArr[pos++] = arr[r_pos++];   // 同上
    }
    // 合并左半区剩余的元素（如果右半区已经合并完）
    while (l_pos <= mid)
        tempArr[pos++] = arr[l_pos++];
    // 合并右半区剩余的元素（如果左半区已经合并完）
    while (r_pos <= right)
        tempArr[pos++] = arr[r_pos++];
    // 把临时数组中合并后的元素复制回原来的数组
    while (left <= right) {
        arr[left] = tempArr[left];
        left++;
    }
}

测试代码：

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("请输入你想生成随机数的个数");
    int num = sc.nextInt();
    int[] arr = new int[num];
    int[] tempArr = new int[num];
    for (int i=0; i<num; i++) arr[i] = (int)(Math.random()*100);
    System.out.println("排序前的数据：");
    for (int i=0; i<arr.length; i++)
        System.out.print(arr[i]+" ");
    long begin = System.currentTimeMillis();
    sort(arr, tempArr, 0, arr.length-1);
    long end = System.currentTimeMillis();
    System.out.println();
    System.out.println("总耗时为："+(end-begin));
    System.out.println("排序后的数据：");
    for (int i=0; i<arr.length; i++)
        System.out.print(arr[i]+" ");
    System.out.println();
}

总结

空间复杂度：O(n)

• 因为创建一个相同大小的临时数组嘛

时间复杂度：O(NlogN)

1. 每一层归并的时间复杂度为O(N)
2. 归并层数最大为O(logN+1)