法一：快速排序

注意边界问题。下面用j，上面不能取到 q[r]。下面用i,上面不能取到 q[l]，可以用q[r]或q[(l+r)/2]

#include <iostream>
using namespace std;

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

void quick_sort(int l,int r)
{
    if(l >= r)  return;
    int x = q[(l+r)/2],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(l,j);
    quick_sort(j+1,r);
}

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

    quick_sort(0,n-1);

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

法二：改进的快速排序

取中间值，并按照三段(< = >)划分

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int n;

void swap(vector<int>& arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

vector<int> partiton(vector<int>& arr, int l, int r)    //荷兰国旗问题
{
    int less = l - 1;
    int more = r;
    while (l<more)
    {
        if (arr[l] < arr[r])
        {
            swap(arr, ++less, l++);
        }
        else if (arr[l] > arr[r])
        {
            swap(arr, --more, l);
        }
        else
        {
            l++;
        }
    }
    swap(arr, more, r);         //默认以arr[r]做划分，不可遗漏最后一位数！
    return { less + 1,more };
}

void quickSort(vector<int>& arr, int l, int r)      //改进的快排，随机取数字做划分值
{
    if (l < r)
    {
        swap(arr, l + rand() % (r - l + 1), r);     
        vector<int>p = partiton(arr, l, r); //返回划分区域（如[5 5 5]）的左边界和右边界
        quickSort(arr, l, p[0] - 1);    //<区
        quickSort(arr, p[1] + 1, r);    //>区
    }
}

int main()
{
    scanf("%d", &n);
    vector<int> q(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;
}