快速排序算法的证明与边界分析：原文

问题：

给定你一个长度为 n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n

第二行包含 n个整数（所有整数均在 1∼10^9范围内），表示整个数列。

输出格式
输出共一行，包含 n个整数，表示排好序的数列。

数据范围
1≤n≤100000

#include <iostream>

using namespace std;

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

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

    int i = l - 1, j = r + 1;
    int x = q[l + r >> 1];
    while (i < j)         //此处不可以i <= j;否则会无限划分
    {
        do i ++ ; while (q[i] < x);   //此处不可以q[i]<=x;当数列中所有元素相等时，会无限循环
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);  
    }

    quick_sort(q, l, j); //以j为划分时，x不能选q[r],否则会无限划分;以i为划分时，x不能选q[l]
    quick_sort(q, j + 1, r);
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ ) cin >> q[i];

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) cout << q[i] << ' ';

    return 0;
}