学步园

详细见算法导论，直接上实现；

最坏情况运行时间O(n*n)  ,平均/期望运行时间O(nlgn)

/*
快速排序 参考算法导论 
qucikSort 

数组的关系坐标都要减1 
*/
#include<iostream>
#include<stdio.h>
using namespace std;

int len;

void swap(int A[],int a,int b)
{
	int temp=A[a];
	A[a]=A[b];
	A[b]=temp;
} 

int partition(int A[],int p,int r)
{
	int x,i,j;
	x=A[r];
	i=p-1;
	for(j=p;j<=r-1;j++)
	{
		if(A[j]<=x)
		{
			i++;
			swap(A,i,j);
		}
	}
	swap(A,i+1,r);
	return i+1;
}

void quickSort(int A[],int p,int r)
{
	int q;
	if(p<r)
	{
		q=partition(A,p,r);
		quickSort(A,p,q-1);
		quickSort(A,q+1,r);
	}
} 

int main()
{
	int A[100];

    while(scanf("%d",&len))
    {
        int i;
        for(i=1;i<=len;i++)
            cin>>A[i];
        quickSort(A,1,len);
        for(i=1;i<=len;i++)
            cout<<A[i]<<" ";
        cout<<endl;
    }
	
	return 0;
}

void Swap(ElementType *left, ElementType *right)    
{    
    ElementType temp = *left;    
    *left = *right;    
    *right = temp;    
}    
    
int Partition(ElementType A[], int low, int high)    
{    
    ElementType pivotkey = A[low];    
    
    while(low < high){    
        while(low < high && A[high] >= pivotkey)      
            high--;    
        Swap(&A[low], &A[high]);    
    
        while(low < high && A[low] <= pivotkey)    
            low++;    
        Swap(&A[low], &A[high]);    
    }    
    
    return low;    
}    
    
void QSort(ElementType A[], int low, int high)    
{    
    int pivotloc;    
    
    if(low < high){    
        pivotloc = Partition(A, low, high);     
        QSort(A, low, pivotloc - 1);    
        QSort(A, pivotloc + 1, high);    
    }    
}    
    
void QuickSort(ElementType A[], int low, int high)    
{    
    QSort(A, low, high);    
}