快速排序实现二

思想

以下为具体的排序情况：

代码实现

void QuickSort2(int* a, int left, int right)
{
    assert(a);
    int mid = ThreeMid(a, left, right); //遍历
    swap(a[mid], a[right]);
    int key = a[right];
    int cur = left;
    int prev = left - 1;
    if (cur >= right)
    {
        return;
    }

    while (cur < right)
    {
        if (a[cur] < key && ++prev != cur)
        {
            swap(a[cur], a[prev]);
        }
        ++cur;
    }
    if (a[prev + 1] > a[right])
    {
        swap(a[++prev], a[right]);
    }

    if (prev - 1 >= 0) //防止下标越界
    {
        QuickSort2(a, left, prev - 1);
    }
    QuickSort2(a, prev + 1, right);
}

链接

ThreeMid(三数取中法）见QuickSort实现一.