算法笔记(18)：较为完美的快排代码

void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

// 返回拆分后a[p]的索引
int Partition(vector<int> &a, int p, int r)
{
    int i = p + 1;
    int j = r - 1;
    int x = a[p];
    // 将[p+1,r)拆分为两部分，左边小于等于a[p]，右边大于x，中间为a[p]
    while (i < j)
    {
        while (a[i] <= x && i < j)
            i++;
        while (a[j] > x && i < j)
            j--;
        swap(a[i], a[j]);
    }
    while (a[i] > x)
        i--;
    swap(a[i], a[p]);
    return i;
}

void QuickSort(vector<int> &a, int l, int r)
{
    if (l == r - 1 || l == r)
        return;
    int mid = (l + r) / 2; // 此处可以改为选择随机索引值
    swap(a[l], a[mid]);
    int p = Partition(a, l, r);
    QuickSort(a, l, p);
    QuickSort(a, p + 1, r);
}