快速排序

　　快速排序和归并排序都是分治法的典型应用，主要区别在于，快速排序重在分，而归并排序重在治。

　　快速排序基于以下假设：已知x，序列中一半的数据大于x，另一半小于等于x，且小于等于x的数据在数组前一半，大于x的在后一半。这种分割不需要额外的存储空间，对两侧数据分别递归进行，最终数组排序即可完成。

　　实际上，x未知时算法依然有效。对于任意支点pivot，和指向左右两端的指针L，R，指针相向而行。对任意i，i < L，有pivot>=x[i]; 任意j，j>R, 有pivot< x[j];

1) L < R, 如果X[L] <= pivot 或者 X[R] > pivot，继续右移L或左移R。否则，X[L] > pivot 并且 X[R] <= pivot，只需交换X[L]，X[R]，然后继续移动指针，直至相遇。

2) L = R时，除X[L]外，序列分割完毕。

　　剩下的问题就是选取支点pivot。以上分析可以看出，支点可以任意选取，为简单选取最左端。快速排序代码如下：

int qsort(int A[], int l, int r)
{
    int pivot;
    if (l < r)
    {   
        pivot = partition(A, l, r); 
        qsort(A, l, pivot - 1); 
        qsort(A, pivot + 1, r); 
    }   
}

int partition(int A[], int l, int r)
{
    int pivot = l;
    int L = l, R = r;
    while (L <= R)
    {   
        while ((L <= r) && (A[L] <= A[pivot]))
            L++;
        while ((R >= l) && (A[R] > A[pivot]))
            R--;
        if (L < R)
            exchange(A[L], A[R]);
    }   
    exchange(A[pivot], A[R]);
    pivot = R;

    return pivot;
}

一次辅助算法partition的时间为O(n), qsort时间复杂度为O(nlbn).

非递归算法：

    int stack[0x100];
    int top = -1; 
    
    void push(int value)
    {
        stack[++top] = value;
    }
    
    int pop()
    {
        top--;
        return stack[top + 1]; 
    }
    int empty()
    {
        return (top == -1);
    }

    void qsort(int A[], int l, int r)
    {
        int pivot, left, right;
        if (l < r)
        {
            push(l);
            push(r);
        }
    
        while (!empty())
        {
            right = pop();
            left = pop();
            pivot = partition(A, left, right);
            if (left < pivot - 1)
            {
                push(left);
                push(pivot - 1);
            }
            if (pivot + 1 < right)
            {
                push(pivot + 1);
                push(right);
            }
        }
    }