$O(NlogN)$

void quick_sort(int &a[], int l, int r) {
    if (l >= r)
        return 0;
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j)
            swap(a[i], a[j]);
    }
    quick_sort(a, l, j), quick_sort(a, j + 1, r);
}

据说下方写法速度快一些。
$O(NlogN)$

int partition(int &a[], int left, int right) {
    int temp = a[left];
    while (left < right) {
        while (left < right & a[right] > temp)
            right--;
        a[left] = a[right];
        while (left < right & a[left] <= temp)
            left++;
        a[right] = a[left];
    }
    a[left] = temp;
    return left;
}
void quick_sort(int &a[], int left, int right) {
    if (left < right) {
        int pos = partition(a, left, right);
        quick_sort(a, left, pos - 1);
        quick_sort(a, pos + 1, right);
    }
}