建议参考这张图和下面的注释来看，图画得很垃圾
顺序是左-》右-》左下-》下-》下-》右上-》下-》下

#include <iostream>
using namespace std;
/*q是传上来的数组 l是0，q[0]就是第一个元素，也就是x（基准数）
* i和j分别代表左指针和右指针，左指针负责找比x小的数，右指针负责找比x大的数
* 因为当两个指针都停下来的时候，会交换两个数值，然后指针各自往前一步，所以i和j分别左移一位
* 如果左指针小于右指针。那么这两个指针就还没有交换，执行while循环
* 先让左指针左移，如果指向的数字小于基准数，满足条件，继续让左指针右移
* 如果大于或者等于基准数，跳出循环，也就是让左指针i停下来
* 接下来移动右指针j,让j指针左移，判断j指针指向的值是不是大于基准数x,如果大于，满足条件，继续左移
* 直到移动到指向不大于x的数，跳出循环，判断左指针i和右指针j的大小，如果i < j，那说明左指针还在右指针的左侧
* 说明二者并没有错开，就把两个指针指向的值进行交换
* 直到二者指向错开，跳出循环
* 再把第一次排好的排序传值到quicksort函数之中，把基准数左边的数进行快速排序，然后再把基准数右边的数进行快速排序
* 这样，我们就把一个数组排好序了
*/
void quicksort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[l], 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]);
    }
    quicksort(q, l, j);
    quicksort(q, j + 1, r);
}
int main(void)
{
    int n;
    const int N = 1e6 + 10;
    static int q[N];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    quicksort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}

2024

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

/*
具体来说，partition函数执行以下步骤：

选择一个基准值（pivot），通常是数组的最后一个元素。
初始化两个指针，一个指向基准值左侧的第一个位置（通常称为i），另一个指向数组的最后一个位置（通常称为j）。
通过j指针从右向左遍历数组，找到第一个小于或等于基准值的元素，然后将其与i指针指向的位置交换。
通过i指针从左向右遍历数组，找到第一个大于基准值的元素，然后将其与j指针指向的位置交换。
当i和j指针相遇时，停止遍历，此时i指针指向的位置就是基准值应该放置的位置。
将基准值与i指针指向的元素交换位置。
返回i指针的值，即基准值的新索引。
在sort函数中，partition返回的值p表示基准值在划分后的数组中的索引。
然后，sort函数递归地对基准值左侧和右侧的子数组进行排序。
这样，每次递归调用都会处理一个更小的子数组，直到子数组的大小减小到1或0，此时递归结束，整个数组就排序完成了。
*/
int partition(int arr[], int low, int high) {
    int pivot = arr[high];// pivot取为数组的最后一个元素 
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void sort(int arr[], int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high); //基准值的新索引
        sort(arr, low, p - 1);
        sort(arr, p + 1, high);
    }
}

int main() {
    int arr[7] = {5, 1, -1, 12, 44, 0, 2};
    int length = sizeof(arr) / sizeof(int);
    cout << "Original array: ";
    printArray(arr, length);
    sort(arr, 0, length - 1);
    cout << "Sorted array: ";
    printArray(arr, length);
    return 0;
}