一、题目描述

示例 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++);}}
};