简介
快速排序使用分治法策略把一个串行分为两个字串行。
算法步骤
- 从数列中挑出一个元素，称为“基准”；
- 重新排序数组，所有元素比基准值小的拜访在基准前面，大的放在后面。在这个分区退出之后，该基准就处于数列的中间位置。这个成为分区操作；
- 递归地把小于基准值元素的子数列和大于的子数列排序；
代码实现
```cpp
// 打乱数组
void shuffle(vector& nums) {
for (int i = 0; i < nums.size(); ++i) { int j = i + rand() % (nums.size() - i); swap(nums[i], nums[j]);
}
}
int partition(vector& nums, int low, int high) {
int pivot = nums[low];
while (low < high) {
while (low < high && nums[high] >= pivot) {
—high;
}
nums[low] = nums[high];
while (low < high && nums[low] <= pivot) {
++low;
}
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}
void quicksort(vector& nums, int low, int high) {
if (low < high) {
int pivot = partition(nums, low, high);
quicksort(nums, low, pivot - 1);
quicksort(nums, pivot + 1, high);
}
}
// 快速排序
void quick(vector& nums) {
shuffle(nums);
quicksort(nums, 0, nums.size() - 1);
}
// 快速选择
int findKthLargest(vector& nums, int k) {
shuffle(nums);
k = nums.size() - k;
int low = 0, high = nums.size() - 1;
while (low <= high) {
int p = partition(nums, low, high);
if (p < k) {
low = p + 1;
} else if (p > k) {
high = p - 1;
} else {
return nums[p];
}
}
return -1;
}
```
