排序数组 ---- 分治-归并

题目链接

题目:

分析:

• 用这道题来回顾一下归并排序的思想
• 找到中间结点, 将数组分成两半, 运用递归的思想, 继续对一半进行分半, 分到最后剩一个元素, 再将左右数组合并, 合并两个有序数组, 是先分解, 再合并的过程
• 在合并两个有序数组时, 需要一个额外的数组来记录, 为了避免每次递归都要创建一个新数组浪费空间, 可以将数组定义在全局变量

代码:

class Solution {
        int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right)
            return;
//找中间点
        int mid = left + ((right - left) >> 1);
//划分左边
        mergeSort(nums, left, mid);
//划分右边
        mergeSort(nums, mid + 1, right);
//对有序数组进行合并
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        while (cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while (cur2 <= right)
            tmp[i++] = nums[cur2++];
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }

    }
}