快速排序
基础快速排序
快速排序基于分治法，我们选定一个元素为枢轴(pivot，通常第一轮选择首元素为枢轴)，从两端开始比较，设左端为low，右端为high。
在每轮遍历前，我们把枢纽放到当前区间最后一位，然后从倒数第二位置作为右端
- nums[low] < pivot， low++ (low不能超过最后一位)
- nums[high] > pivot, high–（high不能小于0）
- 找到第一个不小于枢纽，和第一个不大于枢纽的值，若两值位置
注意事项：
- 注意边界问题
- 每轮枢纽尽量随机选择，可以提高效率（尤其是针对已经有一定序的对象）
练习：215. 数组中的第K个最大元素
class Solution {
public:int findKthLargest(vector<int>& nums, int k){if (nums.size() == 1)return nums[0];// 第k位正确的位置int target = nums.size() - k;int answer = kTh(nums, 0, nums.size() - 1, target);return answer;}int kTh(vector<int>& nums, int low, int high, int target){// 代表只有一个了if (low == high) {return nums[low];}int pivot = nums[low], l = low - 1, r = high;// 把枢纽存储到最后一个位置去std::swap(nums[low], nums[high]);while (l < r) {do l++;while (l < high && nums[l] < pivot);do r--;while (r >= 0 && nums[r] > pivot);if (l < r)std::swap(nums[l], nums[r]);}std::swap(nums[l], nums[high]);if (l == target)return nums[l];else if (l > target) {return kTh(nums, low, l - 1, target);}else {return kTh(nums, l + 1, high, target);}}
};{return kTh(nums, l + 1, high, target);}}
};
