leetcode 链接：912. 排序数组
题目
给你一个整数数组 nums，请你将该数组升序排列。
示例：
输入：nums = [5,2,3,1]输出：[1,2,3,5]
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解答 & 代码
解法一：快速排序
参考：快速排序 - 菜鸟教程
设数组长度为 n
- 时间复杂度 O(n log n)
空间复杂度 O(h)，h 为快排递归调用的层数，递归调用需要 O(h) 的栈空间
- 最快情况需要 O(n) 的空间
最优情况每次都平衡，空间复杂度 O(log n)
class Solution { private: // 快排的分区函数 // 随机挑选数组中的一个元素作为基准 pivot，重新排列数组使得 pivot 左边的元素都比它小，右边的元素都比它大 int partition(vector<int>& nums, int left, int right) { // 随机选择一个元素作为基准 pivot，并将该元素和 left 位置的元素交换 int randomIdx = rand() % (right - left + 1) + left; swap(nums[left], nums[randomIdx]); int pivot = nums[left]; // nums[left] 作为基准元素，left 位置就是第一个空缺位置 while(left < right) { while(left < right && nums[right] >= pivot) --right; nums[left] = nums[right]; // 用 nums[right] 填补左边的空缺，right 就变成新的空缺 while(left < right && nums[left] <= pivot) ++left; nums[right] = nums[left]; // 用 nums[left] 填补右边的空缺，left 就变成新的空缺 } nums[left] = pivot; // 将基准元素填入最后的空缺，此时基准元素左边的元素都比它小，右边的元素都比它大 return left; // 返回基准元素的位置 } // 快速排序主函数 void quickSort(vector<int>& nums, int left, int right) { if(left < right) { int pivot = partition(nums, left, right); // 基准元素的位置 quickSort(nums, left, pivot - 1); // 递归将基准元素左边排序 quickSort(nums, pivot + 1, right); // 递归将基准元素右边排序 } } public: vector<int> sortArray(vector<int>& nums) { quickSort(nums, 0, nums.size() - 1); return nums; } };执行结果： ``` 执行结果：通过
执行用时：100 ms, 在所有 C++ 提交中击败了 18.37% 的用户 内存消耗：27.7 MB, 在所有 C++ 提交中击败了 55.21% 的用户
<a name="ywjhZ"></a>
## 解法二：堆排序
> 参考：[图解排序算法（三）之堆排序](https://www.cnblogs.com/chengxiao/p/6129630.html)
> [堆排序 - 菜鸟教程](https://www.runoob.com/w3cnote/heap-sort.html)
两种堆排序方法：
- **大顶堆**：每个节点的值都大于等于其左右孩子节点的值，用于**升序排序**
- **小顶堆**：每个节点的值都小于等于其左右孩子节点的值，用于**降序排序**
<br />**堆结构的存储**使用的是**数组 **`**nums**`，将上图所示的大顶堆（二叉树）各节点的值按**层序遍历**存储在数组中：
- 数组中下标为 i 的堆节点的**左孩子节点下标为 **`**2i + 1**`**，右孩子节点下标为 **`**2i + 2** `
- **最后一个非叶子节点的下标为 **`**nums.siz()/2 - 1**` ，就是上图大顶堆的“20”这个节点
本题使用大顶堆进行升序排序，**算法流程**：
1. 初始化，将无序序列构建为大顶堆
1. 就是从最后一个非叶子节点开始，从左往右，从下往上调整
2. 循环：直至当前堆只剩一个节点：
1. 将当前堆的最大值（也就是堆顶元素）和当前的堆尾元素交换，那么这个堆尾元素就已经是排好序的了，当前堆不再包含该元素（`len - 1`），重新调整新的堆
- **时间复杂度 O(n log n)**：[初始建堆调整的时间复杂度为 O(n）](https://blog.csdn.net/zhpf225/article/details/105962492)，之后 n - 1 次调整，每次调整的时间复杂度为 O(log n)
- **空间复杂度 O(1)**
```cpp
class Solution {
private:
// 交换数组 idx1 和 idx2 位置对应的元素
void swap(vector<int>& nums, int idx1, int idx2)
{
int temp = nums[idx1];
nums[idx1] = nums[idx2];
nums[idx2] = temp;
}
// 调整大顶堆
// start：要调整的二叉树的头节点在数组 nums 中的下标；
// end：要调整的二叉树的最后一个节点在数组 nums 中的下标
void adjustHeap(vector<int>& nums, int start, int end)
{
int dadIdx = start; // 父节点下标
int sonIdx = start * 2 + 1; // 子节点下标（初始化为左孩子节点）
// 如果子节点在调整范围内，循环继续调整
while(sonIdx <= end)
{
// 比较左、右孩子节点值得大小，取大的作为子节点
if(sonIdx + 1 <= end && nums[sonIdx] < nums[sonIdx + 1])
++sonIdx;
// 如果子节点的值 > 父节点的值，交换父子节点的值，继续比较、调整子节点和孙子节点
if(nums[sonIdx] > nums[dadIdx])
{
swap(nums, sonIdx, dadIdx); // 交换父子节点的值
dadIdx = sonIdx;
sonIdx = dadIdx * 2 + 1;
}
// 如果子节点的值 <= 父节点的值，代表调整完毕，直接返回跳出函数
else
return;
}
}
// 堆排序（大顶堆，升序）
void maxHeapSort(vector<int>& nums)
{
int len = nums.size();
// 1. 初始化，将无序序列构建为大顶堆
// 从最后一个非叶子节点(len / 2 - 1)开始，从左往右，从下往上调整二叉树
for(int i = len / 2 - 1; i >= 0; --i)
adjustHeap(nums, i, len - 1);
// 将堆顶元素与当前堆末尾交换
for(int i = len - 1; i > 0; --i)
{
swap(nums, 0, i); // 将堆顶元素（当前最大值）与当前堆末尾交换
adjustHeap(nums, 0, i - 1); // 调整剩下的堆（除去之前已排好序的堆尾元素）
}
}
public:
vector<int> sortArray(vector<int>& nums) {
maxHeapSort(nums);
return nums;
}
};
执行结果：通过
执行用时：132 ms, 在所有 C++ 提交中击败了 9.55% 的用户
内存消耗：27.8 MB, 在所有 C++ 提交中击败了 38.10% 的用户
解法三：归并排序
- 递归对数组左半边排序
- 递归对数组右半边排序
将排好序的左、右半边数组合并
时间复杂度 O(n log n)：
空间复杂度 O(n)：合并两个排序数组的时候需要使用额外的数组 tmp 暂存合并后的结果，空间复杂度 O(n)；递归调用需要的栈空间为 O(log n)
class Solution { private: // 归并排序 void mergeSort(vector<int>& nums, int left, int right) { // 递归结束条件 if(left >= right) return; int mid = (left + right) / 2; mergeSort(nums, left, mid); // 递归对数组左半边进行排序 mergeSort(nums, mid + 1, right); // 递归对数组右半边进行排序 // 双指针，将排序后的左、右半边数组合并 int idx1 = left; int idx2 = mid + 1; vector<int> tmp(right - left + 1, 0); // 合并后的结果暂时存储到 tmp 数组 int idx = 0; while(idx1 <= mid && idx2 <= right) { if(nums[idx1] < nums[idx2]) { tmp[idx] = nums[idx1]; ++idx1; } else { tmp[idx] = nums[idx2]; ++idx2; } ++idx; } while(idx1 <= mid) { tmp[idx] = nums[idx1]; ++idx1; ++idx; } while(idx2 <= right) { tmp[idx] = nums[idx2]; ++idx2; ++idx; } // 将 tmp 数组的值再拷贝回原数组 for(int i = 0; i < right - left + 1; ++i) nums[left + i] = tmp[i]; } public: vector<int> sortArray(vector<int>& nums) { mergeSort(nums, 0, nums.size() - 1); return nums; } };执行结果： ``` 执行结果：通过
执行用时：204 ms, 在所有 C++ 提交中击败了 5.93% 的用户 内存消耗：70.4 MB, 在所有 C++ 提交中击败了 4.99% 的用户 ```
若有收获，就点个赞吧
0 人点赞
