LeetCode 912.排序数组

题目描述:

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]

输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]

输出：[0,0,1,1,2,5]

提示：

1. 1 <= nums.length <= 50000

2. -50000 <= nums[i] <= 50000

题目分析:

假设有以下数组需要排序，我们采用归并排序解法。

首先将数组分割成两个部分。

分别对其进行归并排序。排完序得到以下两个数组。排序的方法同样是分割数组，直到不能再分割为止，然后合并两个子数组，合并方法与最后一次合并同理，这里不再赘述，最后的合并方法如下。

定义两个指针分别指向两个数组的首元素。比较两个值的大小，将小的数依次赋给临时数组。如下图，10小于40，将10赋给临时数组，并使临时数组的索引指针以及右边数组的指针移动，继续进行下一轮检查。

同理，40小于70，把40赋给临时数组，移动指针。

直到两个数组的值都赋给了临时数组，排序也就完成。

题解:

执行用时: 10 ms

内存消耗: 47.8 MB

class Solution {    public int[] sortArray(int[] nums) {        // 创建临时数组，用于归并        int[] temp = new int[nums.length];        // 调用归并排序方法        mergeSort(nums, 0, nums.length - 1, temp);        // 返回排序完的结果        return nums;    }
    public void mergeSort(int[] nums, int start, int end, int[] temp) {        // 递归结束条件        if (start >= end)            return;        // 获取中点        int mid = (start + end) / 2;        // 递归排序        mergeSort(nums, start, mid, temp);        mergeSort(nums, mid + 1, end, temp);        // 合并排完序的两个数组        merge(nums, start, mid, end, temp);    }
    public void merge(int[] nums, int start, int mid, int end, int[] temp) {        // 定义左右指针分别指向两个待合并的数组头        int left = start;        int right = mid + 1;        // 定义索引指针指向临时数组头        int index = start;        // 同时遍历两个数组，把小的元素依次放入临时数组        while (left <= mid && right <= end) {            // 当左数组指向元素 小于 右数组指向元素时，把左数组指向的元素放入            if (nums[left] < nums[right])                temp[index++] = nums[left++];            // 否则，把右数组指向元素放入            else                temp[index++] = nums[right++];        }        // 如果左数组还有剩余元素，直接追加到临时数组后面        while (left <= mid)            temp[index++] = nums[left++];        // 如果右数组还有剩余元素，直接追加到临时数组后面        while (right <= end)            temp[index++] = nums[right++];        // 用临时数组的值覆盖原数组        for (index = start; index <= end; index++)            nums[index] = temp[index];    }}

题目来源:力扣(LeetCode)