Medium

题目描述

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

你必须在不使用任何内置函数的情况下解决问题，时间复杂度为 O(n log n)，并且空间复杂度尽可能小。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：排序后，某些数字的位置没有改变（例如 2 和 3），而另一些数字的位置发生了改变（例如 1 和 5）。

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：注意 nums 的值不一定是唯一的。

提示：

  • 1 <= nums.length <= 5 * 10^4
  • -5 * 10^4 <= nums[i] <= 5 * 10^4

解题思路

本题要求在不使用内置排序函数的情况下，以 O(n log n) 时间复杂度对数组进行排序。根据约束条件，有几种经典的排序算法可以选择：

方法一：归并排序（推荐） 归并排序采用分治思想，将数组递归地分成两半，分别排序后再合并。它保证稳定的 O(n log n) 时间复杂度，空间复杂度为 O(n)。归并排序的优点是性能稳定，不受输入数据影响。

方法二：快速排序 快速排序通过选择基准值进行分区，平均时间复杂度为 O(n log n)，但最坏情况下为 O(n²)。为了避免最坏情况，可以使用随机化或三数取中法选择基准。

方法三：堆排序 构建最大堆后依次取出堆顶元素，时间复杂度稳定为 O(n log n)，空间复杂度为 O(1)。

方法四：计数排序 由于题目给出了数值范围（-50000 到 50000），可以使用计数排序达到 O(n + k) 的时间复杂度，其中 k 为值域大小。

考虑到题目要求空间复杂度尽可能小且时间复杂度稳定，这里推荐使用归并排序作为主要解法。

代码实现

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    
private:
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    
    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        
        for (int i = 0; i < temp.size(); i++) {
            nums[left + i] = temp[i];
        }
    }
};

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(arr, left, right):
            if left >= right:
                return
            
            mid = (left + right) // 2
            merge_sort(arr, left, mid)
            merge_sort(arr, mid + 1, right)
            merge(arr, left, mid, right)
        
        def merge(arr, left, mid, right):
            temp = []
            i, j = left, mid + 1
            
            while i <= mid and j <= right:
                if arr[i] <= arr[j]:
                    temp.append(arr[i])
                    i += 1
                else:
                    temp.append(arr[j])
                    j += 1
            
            while i <= mid:
                temp.append(arr[i])
                i += 1
            while j <= right:
                temp.append(arr[j])
                j += 1
            
            for k in range(len(temp)):
                arr[left + k] = temp[k]
        
        merge_sort(nums, 0, len(nums) - 1)
        return nums

public class Solution {
    public int[] SortArray(int[] nums) {
        MergeSort(nums, 0, nums.Length - 1);
        return nums;
    }
    
    private void MergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        MergeSort(nums, left, mid);
        MergeSort(nums, mid + 1, right);
        Merge(nums, left, mid, right);
    }
    
    private void Merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        
        for (int idx = 0; idx < temp.Length; idx++) {
            nums[left + idx] = temp[idx];
        }
    }
}

var sortArray = function(nums) {
    function mergeSort(arr, left, right) {
        if (left >= right) return;
        
        const mid = Math.floor((left + right) / 2);
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    
    function merge(arr, left, mid, right) {
        const temp = [];
        let i = left, j = mid + 1;
        
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp.push(arr[i++]);
            } else {
                temp.push(arr[j++]);
            }
        }
        
        while (i <= mid) temp.push(arr[i++]);
        while (j <= right) temp.push(arr[j++]);
        
        for (let k = 0; k < temp.length; k++) {
            arr[left + k] = temp[k];
        }
    }
    
    mergeSort(nums, 0, nums.length - 1);
    return nums;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
归并排序O(n log n)O(n)
快速排序（平均）O(n log n)O(log n)
快速排序（最坏）O(n²)O(n)
堆排序O(n log n)O(1)
计数排序O(n + k)O(k)

其中 n 为数组长度，k 为值域范围（本题中 k = 100001）。