【问】：

下面这段代码（快速排序算法）的复杂度是多少？和sort函数相比呢？

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

    int i = l - 1, j = r + 1, x = q[l + 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(q, l, j), quick_sort(q, j + 1, r);
}

【答】：

这段代码是快速排序算法的一个实现，其平均时间复杂度为 O(n log n)，其中 n 是数组的长度。在最坏情况下，当数组已经是有序的或者是逆序的，快速排序的时间复杂度会退化为 O(n^2)。

标准库中的 sort 函数通常使用一种称为内省排序（introsort）的排序算法，这是一种结合了快速排序、堆排序和插入排序的混合排序算法。内省排序的平均时间复杂度也是 O(n log n)，但是它的最坏情况时间复杂度被优化为 O(n log n)，这使得它在实际应用中比纯粹的快速排序更加稳定和可靠。

总的来说，这段快速排序代码在平均情况下的性能与 sort 函数相当，但在最坏情况下性能不如 sort 函数。