快排

#include <cstdio>
#include <ctime>
#include <cstdlib>

void swap(int *arr, int i, int j) {
    if (i == j) return;                                    
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

void partition(int *arr, int left, int right, int *help) {
    srand((int)time(NULL));
    int ind = left + (int)((double)rand() / RAND_MAX * (right - left));
    swap(arr, ind, right);
    int less = left - 1, more = right;
    while (left < more) {
        if (arr[left] < arr[right]) swap(arr, ++less, left++);
        else if (arr[left] == arr[right]) ++left;
        else swap(arr, --more, left);
    }
    swap(arr, more, right);
    help[0] = less + 1;
    help[1] = more;
}

void quickSort(int *arr, int left, int right) {
    if (left >= right) return;
    int help[2];
    partition(arr, left, right, help);
    quickSort(arr, left, help[0] - 1);
    quickSort(arr, help[1] + 1, right);
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; ++i) printf("%d ", arr[i]);
    return 0;
}