912. 排序数组——归并排序Java时间复杂度空间复杂度稳定性分析

目录

1.题目

2.思路

归并排序——nlogn

思想——递归

代码

时间复杂度——O（nlogn）

空间复杂度——O（n）

稳定性——稳定

3.结果

1.题目

2.思路

这个题可以作为练习手写各种排序的场景题。这里回顾一下归并排序。

归并排序——nlogn 思想——递归

每次都把这个数组分成两堆【0， mid】和 【mid + 1， end】，分别对两堆进行排序，然后再合并两个有序的数组，中间借助了一个temp[]数组。这里借助的是递归的思想，每次都把数组分成两堆。比如在排序前半部分的时候，也就是【0， mid】的时候，同样的也是把这个数组分成两堆，然后分别排序好之后，然后再合并。所以会不断地递归下去。直到不能分成两堆为止。

代码

• 归并排序主函数为public void mergeSort(int[]nums, int start, int end)
• 合并两个有序数组的函数：public void merge(int[]nums, int start, int mid, int end)
• 注意归并排序结束条件：if(start >= end) return ;
• 注意借助了一个暂时的数组存放合并好的数组temp[]

class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        mergeSort(nums, 0, n - 1);
        return nums;
    }
    // 归并排序
    public void mergeSort(int[]nums, int start, int end){
        if(start >= end) return;

        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);

        // 合并到一起
        merge(nums, start, mid, end);
        return ;
    }

    // 合并两个有序的数组到一起
    public void merge(int[]nums, int start, int mid, int end){
        int[]temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;
        while(i <= mid && j <= end){
            if(nums[i] <= nums[j]){  //如果这里<= ,那么就是稳定的，如果是<,那么就是非稳定的
                temp[k++] = nums[i++];
            }
            else{
                temp[k++] = nums[j++];
            }
        }

        // 跳出循环有两个可能
        while(i <= mid){
            temp[k++] = nums[i++];
        }

        while(j <= end){
            temp[k++] = nums[j++];
        }

        // 更新nums
        for(int l = start; l < start + temp.length; l++){
            nums[l] = temp[l - start];
        }
        return ;
    }
}

时间复杂度——O（nlogn）

我们可以把时间分成两块乘积，一个是把一个数组分成两堆的时间。一个是合并两个有序数组的时间。分别来简单计算一下，首先是第一次会把数组分成两堆，下一次总共就会有4堆，一直往下，相当于是一颗满二叉树，这个满二叉树的深度为logn,也就是需要nlogn时间.

对于另外一块，合并两个有序数组的时间，因为会遍历这两个数组的元素各一次，所以是O（n）, 不管分成多少堆，每一次的合并数组的时间都是O（n）,因为数组总元素没有变化。

所以最终就是nlogn的时间复杂度。

空间复杂度——O（n）

因为借助了临时数组来保存结果。所以是O（n）

稳定性——稳定

稳定性：就是如果两个值相同，排序完后，这两个元素的相对位置没变化，那么就说明是稳定的。

这里归并的稳定性主要取决于合并两个有序数组的函数merge()的写法。

比如我这里写得是<=，那么就是稳定的。因为假如nums[i] == nums[j],那么我们是先把nums[i]放在temp数组的前面的，所以相对顺序并不会改变。所以是稳定的。

我们在讨论归并排序的时候，因为他可以是稳定的，所以这个方法一般被称为稳定的排序算法。

3.结果