算法思想

分而治之 有点类似于二分

1. 确定分界点

​ 从数组中选取一个元素作为基准，通常可以选择第一个元素、最后一个元素、中间元素，或者通过随机化方式选择。

1. 调整区间

2. 将数组分成两部分：左侧所有元素小于等于基准，右侧所有元素大于等于基准。

3. 基准元素会被移到其正确的位置。

调整区间的实现方法有很多种

1. 递归处理左右两段

调整区间的原因（复杂度分析）：

​ 很厉害，第一次遍历n次能找到一个排好序的元素，当我调整区间后，第二次遍历n个数，可以找到两个排好序的元素，以此类推第三次遍历n个数，可以找到$2^2$个排好序的元素，即第$logn$次排序，就能找到$n$个排好序的数

​ 所以，n个数需要$logn$次排序，每次排序复杂度为$n$，最好的算法复杂度是$O(nlogn)$

+++

最简单的一个实现思路（忘记了怎么优美实现快排可以用这个方法，就是会用到额外的空间）

1. 创建两个数组a[]和b[]
2. 将小于等于基准的数放入a[]，大于基准的数放入b[]
3. 将a[]和b[]按顺序放入原数组

代码实现

普通实现

本质就是交换，先把基准值拿出来，左右双指针，先动右指针，因为此时基准值是一个空位

1. 右指针往左遍历，找到第一个小于等于基准的数，将其放到左指针的位置
2. 左指针往右遍历，找到第一个大于基准的数（也可以大于等于），将其放到右指针的位置
3. 最后的位置的放基准值
4. 递归左右两边

#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

const int N = 1e5 + 10;
int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int randomIdx = l + rand() % (r - l + 1);  // [l, r]
    swap(q[randomIdx], q[l]);
    int x = q[l], i = l, j = r;
    while(i < j)
    {
        while(i < j && q[j] > x) j --;
        q[i] = q[j];
        while(i < j && q[i] <= x) i ++;
        q[j] = q[i];
        // 结束的条件 一定是 i == j
    }
    q[i] = x;

    quick_sort(q, l, i - 1);
    quick_sort(q, i + 1, r);
}

int main()
{
    srand(time(0));
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for(int i = 0; i < n; i ++) printf("%d ", q[i]);

    return 0;
}

普通实现优化

上面的实现会导致一个最差复杂度的问题

​ 上面的实现当处理所有都为重复的数或者随机每次取到最大或者最小的数（概率很小），第一次遍历$n$次找到一个排好序的元素，第二次遍历$n - 1$次找到一个排好序的元素，以此类推直到遍历1次，找到一个排好序的元素，每次都是找到一个排好序的元素。

​ 所以，相当于需要$n$次排序，每次遍历次数从$n$递减，总遍历次数为$T(n)=n(n+1)/2$，即$O(n^2)$

优化代码

三路快排

把元素分为三部分

1. 小于基准值x的部分，q[l, lt - 1]
2. 等于基准值x的部分，q[lt, gt]
3. 大于基准值x的部分，q[gt + 1, r]

等于基准值的部分不参与递归，就可以好的优化重复数很多de

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>

using namespace std;

const int N = 10e5 + 10;
int n;
int q[N];

// 分成三部分 q[l, lt - 1] q[lt, gt] q[gt + 1, r]
void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int randomIdx = l + rand() % (r - l + 1);  // [l, r]
    swap(q[l], q[randomIdx]);
    int x = q[l], i = l + 1;
    int lt = l, gt = r;

    while(i <= gt)
    {
        if(q[i] < x) swap(q[i], q[lt ++]);
        else if(q[i] > x) swap(q[i], q[gt --]);
        else i ++;
    }

    quick_sort(q, l, lt - 1);
    quick_sort(q, gt + 1, r);
}

int main()
{
    srand(time(0));

    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for(int i = 0; i < n; i ++) printf("%d ", q[i]);

    return 0;
}

优美实现

算法思想

既然是交换，为什么不两边一起交换

1. 左指针往右走，找到第一个应该在基准值右侧（大于等于基准值）的数，注意必须有等于，如果没有等于的话，基准值不会被移动到中间，所以有可能不是基准值分割区间。
2. 右指针往左走，找到第一个应该在基准值左侧（小于等于基准值）的数
3. 交换

循环交换后，会发现i的左边（不包括i）一定是小于等于基准值的，j的右边（不包括j）一定是大于等于基准的

原因很简单，i右移的时候，要满足q[i] < x，所以i的左边一定小于基准值，但是与j指针交换的时候有可能把等于基准值的数换过来，所以i的左边（不包括i）一定是小于等于基准值的。

j同理

例如：

1. 数列3 4 2 6 5，最后i指向4，j指向3，i指向的数大于基准值3；
2. 数列3 1 2 6 4，最后i指向3，j指向1，j指向的数小于基准值3；

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>

using namespace std;

const int N = 10e5 + 10;
int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int randomId = l + rand() % (r - l + 1);

    int x = q[randomId], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    srand(time(0));

    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for(int i = 0; i < n; i ++) printf("%d ", q[i]);

    return 0;
}

边界条件：用i则不能取到左边界；用j则不能取到右边界

1. 当用quick_sort(q, l, j); quick_sort(q, j + 1, r);划分区间的时候，基准值不可以是q[r]

如排序1 2的时候，基准值为x = 2，排序后i = 1, j = 1(右边界)

quick_sort(q, 0, 1); // 死循环
quick_sort(q, 1, 1);

1. 同理，当用quick_sort(q, l, i - 1); quick_sort(q, i, r);时，基准值不可以是q[l]

如数列1 2，基准值x = 1，排序后i = 0(左边界)

quick_sort(q, 0, -1);
quick_sort(q, 0, 1);  // 死循环