2020/8/7
快速排序
关于边界条件
https://www.acwing.com/solution/content/16777/这篇题解讲的很不错，个人喜欢用 j 做边界，所以 pivot=nums[l],对于用 i 做边界，则需要同 j 的情况取反。对于数据增强的情况下 pivot 取 nums[(l+r)/2]或随机化加快速度
``` cpp
void quick_sort(vector<int>& nums, int l, int r) {
if(l >= r) {
return ;
}
// int pivot = (r + l) / 2;
int pivot = l + rand() % (r - l + 1);
// 注意基准元素应当取出来比较
int x = nums[pivot];
int i = l - 1;
int j = r + 1;
while(i < j) {
// x 不能用 nums[pivot]代替，因为 swap 会破坏 nums[pivot]
while(nums[++i] < x);
while(nums[--j] > x);
if(i < j) {
swap(nums[i], nums[j]);
}
}
quick_sort(nums, l, j);
quick_sort(nums, j+1, r);
}
```
归并排序
堆排序
（改天在学
快速选择算法
思路：直接 k-1 寻找排序后第 k-1 个元素的位置，因为每次只递归一边，所以期望复杂度时 O(n)，具体证明算导(看不懂 x
``` cpp
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return quick_select(nums, 0, nums.size() - 1, k - 1);
}
int quick_select(vector<int>& nums, int l, int r, int k) {
if(l >= r) {
return nums[l];
}
int i = l - 1;
int j = r + 1;
// int pivot = l + rand() % (r - l + 1);
int pivot = (l + r) / 2;
// int pivot = l;
int x = nums[pivot];
while(i < j) {
while(nums[++i] > x);
while(nums[--j] < x);
if(i < j) {
swap(nums[i], nums[j]);
}
}
//
// int sl = j - l + 1;
if(k <= j) {
return quick_select(nums, l, j, k);
}
return quick_select(nums, j + 1, r, k);
}
};
```
15. 三数之和
首先排序
对于 nums[i] > 0,可以直接 break ，后面不会有符合题意的三元组
注意 i 去重，jk 在取到目标三元组也需要去重，
103. 二叉树的锯齿形层序遍历
flag 标记奇 /偶