pta快速排序

PTA（Programming Test Assessment）是一个在线编程评测平台，快速排序（Quick Sort）是一种常见的排序算法。

以下是PTA上的快速排序的示例代码，仅供参考：

#include <iostream>
using namespace std;

void quicksort(int a[], int left, int right) {
    if (left >= right) return;
    int i = left, j = right, pivot = a[(left + right) / 2];
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++; j--;
        }
    }
    quicksort(a, left, j);
    quicksort(a, i, right);
}

int main() {
    int n;
    cin >> n;
    int a[100000];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    quicksort(a, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

快速排序的原理是通过递归的方式将数组不断划分为小于基准值的左半部分和大于基准值的右半部分，直到每个子数组的长度为1或0，以达到排序的目的。时间复杂度为O(nlogn)。