蔡子经数据结构3.7

#define MAXN 100
int a[MAXN] = {5,5,6,9,5,2,3,6,5,4};
int stk[MAXN];
int top = 0;

void ()
{
    top = 0;
}
void Push(int x)
{
    stk[top++] = x;
}
int Top()
{
    return stk[top-1];
}
void Pop()
{
    --top;
}
int IsEmpty()
{
    return top==0;
}

int partition(int *a, int l, int r)
{
    if(a == NULL || l < 0 || r <= 0 && l > r)
        return -1;
    int i = l, j = r;
    int axi = a[i];
    while(i != j)
    {
        if(i < j && a[j] >= axi)
            --j;
        a[i] = a[j];
        if(i < j && a[i] <= axi)
            ++i;
        a[j] = a[i];
    }
    a[i] = axi;
    return i;
}

void quickSort(int *a, int l, int r)
{
    if(a == NULL || l < 0 || r <= 0 || l > r)
        return ;
    InitStack();
    int i = l, j = r,k;
    Push(j);
    Push(i);
    while(!IsEmpty())
    {
        i = Top();
        Pop();
        j = Top();
        Pop();
        if(i < j)
        {
            k = partition(a, i, j);
            if(k > i)
            {
                Push(k-1);
                Push(i);
            }
            if(k < j)
            {
                Push(j);
                Push(k+1);
            }
        }
    }
}

int main()
{
    int n = 10;
    quickSort(a, 0, n-1);
    for(int i = 0; i < n; ++i)
        printf("%dn",a[i]);
    return 0;
}