快速排序(Quick Sort)，既然敢起这样的名字，说明它是常⻅排序算法中较为优秀的。事实上，在很多情况下，快排确实是效率较⾼的算法；c++的排序是以快排为基础，再加上堆排和插入排序做优化实现的，我们这里实现的快速排序，只是单纯的快速排序
核心算法原理可以分为两步
- 从待排序区间中选择一个基准元素，按照基准元素的大小将区间分成左右两部分
- 然后递归处理左区间和右区间，直到区间长度为1
图中第一个长方形是一个待排序区间，我们会从中选择一个基准元素p，把区间划分成小于基准元素的和大于基准元素的，如果等于基准元素就放到左边或者右边，分完区后，此时p元素已经放在排序好的最终位置上了；比如最后是个升序，左边全是小于p的，右边全是大于p的，不管左右两边是否有序，此时p元素一定放在了它的最终位置上，所以就不用管p元素了，接下来处理小于和大于基准元素的区间
再从小于基准元素区间中选择一个基准元素p，并且划分左右区间，此时p再次放到了排好序的最终位置上，接着处理它的左右区间，一直处理到不能再处理的时候，也就是区间长度为1的时候，小于基准元素区间也就是初始p元素的左区间就已经变成有序序列了，右边的大于基准元素区间也是同理
大家可以想一想处理左区间的时候，每处理一次会把一个数放到它最终的位置上，处理右区间也是，一直处理到不能再处理的时候，每个数都放到了排序好的最终位置上，他就已经变成一个有序序列了
模拟快排过程，会发现有一点先序遍历的味道，把根节点看成待排序区间，它划分出了左右区间也就是左右子树，先处理左区间，再划分左右区间，先处理左区间，把左边的例子5代入过来，此时区间长度为1就不用管它了，返回去处理右区间，只有一个节点30再返回去处理根节点的右区间，其中一个元素现在变得有序，划分出来左区间，两个元素现在变得有序，再划分出来左区间42，三个元素变得有序，因为它是一个叶子节，返回，整个序列变得有序了
先序遍历测试：
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int val;
Node* left;
Node* right;
Node(int x) : val(x), left(nullptr), right(nullptr) {}
};
void preorder(Node* root) {
if (!root) return;
cout << root->val << " "; // 访问根节点
preorder(root->left); // 遍历左子树
preorder(root->right); // 遍历右子树
}
int main()
{
Node* root = new Node(33);
root->left = new Node(25);
root->right = new Node(50);
root->left->left = new Node(5);
root->left->right = new Node(30);
root->right->left = new Node(49);
root->right->left->left = new Node(42);
//先序遍历
preorder(root);
cout << endl;
return 0;
}
朴素快排的缺陷
- 基准元素选择不当，递归层数会增加，时间复杂度变高；比如快排一个有序序列1234567，首先划分1和右区间234567接着划分2和右区间34567，以此类推，直到划分到n层，在做数组划分的时候会遍历整个数组一遍，此时时间复杂度就是O(N)级别
- 当有大量重复元素时，递归层数也会增加；比如数组里面全都是6，不管选择哪一个位置的6为基准元素，选择完后都会画划分大于等于6的区间出来，之后再选择再划分，一直划分到数组元素个数的层数就和上面的情况一样了
优化一：随机选择基准元素
先解决第一个问题：基准元素选择不当，递归层数会增加，时间复杂度变高。
解决方案：在待排序区间中，随机选择一个基准元素。利用C++提供的随机函数，在一个区间内随机选择一个元素作为基准
随机函数：
srand(time(0)):种下一个随机数种子:
rand():获得一个随机数;
rand()%(right-left +1)+ left:在 [left，right]区间内，随机选择一个数
随机函数的小demo
- 种下一个随机数种子之后，r1r2r3可以获得不同的随机数，在自己创建的函数里面也可以获取随机数
#include <iostream>
#include <ctime>
using namespace std;
void test()
{
int r4 = rand();
cout << "r4 = " << r4 << '\n';
}
int main()
{
srand(time(0)); //种下一个随机数种子
int r1 = rand();
int r2 = rand();
int r3 = rand();
cout << "r1 = " << r1 << '\n';
cout << "r2 = " << r2 << '\n';
cout << "r3 = " << r3 << '\n';
test();
//r1 = 30775
//r2 = 31851
//r3 = 10201
//r4 = 12957
return 0;
}优化代码：
- 让随机数模上元素个数（最后一个位置减去第一个位置+1 ），模出来的结果再+1，防止模出来的结果不在此区间；比如23456这五个位置，6-2+1等于5，区间是[0,4]，再加上左区间的端点2，此时区间是[2,6]，在2到6之间随便取一个数
//优化一：随机选择基准元素
//递归的时候需要知道要处理的是哪个区间
int get_random(int left, int right)
{
return a[rand() % (right - left + 1) + left];
}优化二：荷兰国旗-数组分三块
解决第二个问题:当有大量重复元素时，递归层数也会增加。
回忆一下之前在顺序表做过的一道题:《颜色分类》leetcode 75.颜色分类（详解）数组分块c++-CSDN博客，这道题的核心就是数组分成三块：左边全是 0，中间全是1，右边全是2，右边全部大于基准元素。接下来仅需如果在此基础上稍作修改，变成:左边全部小于基准元素;中间全部等于基准元素，递归处理左右区间，中间区间就可以无需考虑
比如数组里面全都是6，根据荷兰国旗思想会选择把全部的6放到等于基准元素区间上，它的左右两边就没有区间了，此时递归直接结束，用O(N)的时间复杂度就把整个数组变得有序了
优化代码：
测试链接：P1177 【模板】排序 - 洛谷
- 递归过程（假设p分别是4，2）
#include <iostream>
#include <ctime>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
// 优化一：随机选择基准元素
int get_random(int left, int right)
{
// 随机数范围在 [left, right] ，模元素个数 + 第一个位置
return a[rand() % (right - left + 1) + left];
}
void quick_sort(int left, int right)
{
// 区间长度不存在或者=1 返回
if (left >= right) return;
//1.选择一个基准元素
int p = get_random(left, right);
//2.数组分三块 = 荷兰国旗问题
int l = left - 1, i = left, r = right + 1;
while (i < r) //i和r不相遇，一直遍历
{
//分类讨论
if (a[i] < p) swap(a[++l], a[i++]); //当前位置与l+1位置交换
else if (a[i] > p) swap(a[--r], a[i]); //交换完后i还要继续判断当前位置，比如a[i] < p，所以i不动
else ++i; //属于基准元素。就应该放在当前位置，直接i++
}
//处理左右区间
// [left,1] [l+1,r-1] [r,right]
// < p p > p
quick_sort(left, l);
quick_sort(r, right);
}
int main()
{
srand(time(0));
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
quick_sort(1, n);
for (int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
} 时间复杂度:
- 如果每次基准元素都选择得当，数组划分的比较均匀，时间复杂度=递归层数*N=N*logN
- 如果划分不当，数组分布比较极端，时间复杂度退化成 N2
《算法导论》中有严谨的证明，加上优化之后的快排，时间复杂度能趋近于N*logN。因此，相较于之前的排序算法，快速是较优的。
