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

题目链接

题目:

分析:

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

代码:

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];}}
}