快排非递归

思想

我所例举的情况比较特殊，恰巧，binary左边有序，有兴趣的可以试一下别的测试用例。

代码实现

int Partition(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;

    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]);
    return prev;
}
void quickSortNonRecursive(int* a, int left, int right)
{
    assert(a);
    stack<int> Stack;
    if (left >= right)
    {
        return;
    }
    if (left < right)
    {
        int binary = Partition(a, left, right);

        if (binary - 1 >= left)
        {
            Stack.push(left);
            Stack.push(binary - 1);
        }
        if (binary + 1 <= right)
        {
            Stack.push(binary + 1);
            Stack.push(right);
        }

        while (!Stack.empty())
        {
            int Right = Stack.top();
            Stack.pop();
            int Left = Stack.top();
            Stack.pop();

            binary = Partition(a, Left, Right);

            if (binary - 1 > Left)
            {
                Stack.push(Left);
                Stack.push(binary - 1);
            }
            if (binary + 1 < Right)
            {
                Stack.push(binary + 1);
                Stack.push(Right);
            }
        }
    }
}