一、题目描述

给你一个整数数组 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.快速排序

快速排序，时间复杂度 $O(n\log n)$，空间复杂度 $O(\log n)$：

class Solution {
public:
    vector<int> sortArray(vector<int> &nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    void quickSort(vector<int> &nums, int begin, int end) {
        if (begin < end) {
            int pivot = partition(nums, begin, end);
            quickSort(nums, begin, pivot - 1);
            quickSort(nums, pivot + 1, end);
        }
    }

    int partition(vector<int> &nums, int begin, int end) {
        int pivot_num = nums.at(begin);

        while (begin < end) {
            while (begin < end && nums.at(end) >= pivot_num) {
                end--;
            }
            nums.at(begin) = nums.at(end);
            while (begin < end && nums.at(begin) <= pivot_num) {
                begin++;
            }
            nums.at(end) = nums.at(begin);
        }

        nums.at(begin) = pivot_num;
        return begin;
    }
};

2.堆排序

堆排序，时间复杂度 $O(n\log n)$，空间复杂度 $O(1)$：

class Solution {
public:
    vector<int> sortArray(vector<int> &nums) {
        buildMaxHeap(nums);
        for (int i = static_cast<int>(nums.size() - 1); i >= 0; i--) {
            swap(nums.at(0), nums.at(i));
            heapAdjust(nums, 0, i);
        }
        return nums;
    }

private:
    /**
     * 构建大根堆
     */
    void buildMaxHeap(vector<int> &nums) {
        for (int i = static_cast<int>(nums.size()) / 2 - 1; i >= 0; i--) {
            heapAdjust(nums, i, static_cast<int>(nums.size()));
        }
    }

    /**
     * 调整以root为根的二叉树
     * @param nums 存储二叉树元素的数组
     * @param root 根节点
     * @param len 包括根节点在内要调整的元素总数
     */
    void heapAdjust(vector<int> &nums, int root, int len) {
        int tmp = nums.at(root);  // 本轮需要被筛选的值

        /* 从root的孩子开始逐层向下调整 */
        for (int child = 2 * root + 1; child < len; child = 2 * child + 1) {
            /* 选取两个孩子中值较大的那个节点与父节点进行比较 */
            if ((child + 1) < len && nums.at(child + 1) > nums.at(child)) {
                child++;
            }

            /* 如果两个孩子都不大于当前根节点，则结束当前层的调整
             * 如果某一个孩子大于当前根节点，则将该孩子换到当前根上 */
            if (nums.at(child) <= tmp) {
                break;
            } else {
                nums.at(root) = nums.at(child);
                root = child;  // 提前准备下一层循环
            }
        }

        /* 将筛选的值放到最终位置上 */
        nums.at(root) = tmp;
    }
};

3.二路归并排序

二路归并排序，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, static_cast<int>(nums.size() - 1));
        return nums;
    }

private:
    void mergeSort(vector<int> &nums, int begin, int end) {
        if (begin < end) {
            int mid = begin + (end - begin) / 2;
            mergeSort(nums, begin, mid);
            mergeSort(nums, mid + 1, end);
            merge(nums, begin, mid, end);
        }
    }

    /**
     * 将两个子数组合并为一个大数组
     * @param nums 数据
     * @param begin 第一个子数组的起始元素下标
     * @param mid 第一个子数组的结束元素下标，它后面一个元素即为第二个子数组的起始元素
     * @param end 第二个子数组的结束元素下标
     */
    void merge(vector<int> &nums, int begin, int mid, int end) {
        vector<int> supply(nums.size());  // 辅助数组
        int i, before, after;

        /* 将数据从nums中拷贝到records中 */
        for (i = begin; i <= end; i++) {
            supply.at(i) = nums.at(i);
        }

        /* 依次将两个子数组的最小值复制到大数组中 */
        for (before = begin, after = mid + 1, i = begin; before <= mid && after <= end; i++) {
            if (supply.at(before) < supply.at(after)) {
                nums.at(i) = supply.at(before++);
            } else {
                nums.at(i) = supply.at(after++);
            }
        }

        /* 处理剩余数据 */
        while (before <= mid) {
            nums.at(i++) = supply.at(before++);
        }
        while (after <= end) {
            nums.at(i++) = supply.at(after++);
        }
    }
};