hudaixa.cpp

常见算法

#include <iostream.h>
#include <stdlib.h>
Partition(int *a,int p,int r)
{
	int x,i,j;
	i=p;
	j=r;
	x=*(a+p);          //x is the flag
	while(i!=j){
		while(j>i && *(a+j)>x){j--;}
		*(a+i)=*(a+j);//the more befor flag
		while(i<j && *(a+i)<x){i++;}
		*(a+j)=*(a+i);// the less  after  flag
	}
	*(a+i)=x;         
	return i;
}
Randomized_partition(int *a,int p,int r)
{
	int tmp,i;
	i=p+rand()%r;
	tmp=*(a+p);//exchange a[p] and a[i]
	*(a+p)=*(a+i);
	*(a+i)=tmp;
	return Partition (a,p,r);
}
Quicksort(int A[],int p,int r)
{
	int q;
	if(p<r)
	{
		q=Randomized_partition(A,p,r);
		Quicksort(A,p,q);                  //divided
		Quicksort(A,q+1,r);
	}
	return 0;
}
main()
{
	int i;
	int a[8]={5,8,7,1,3,2,6,4};
	int A[9];
	for(i=0;i<=7;i++){
		A[i+1]=a[i];
	}                        //make the array from A[1]
	Quicksort(A,1,8);
	for(i=1;i<=8;i++)
	{
		cout<<A[i]<<" ";     //output the array
	}
	return 0;
}
//the process of partiton
//5 8 7 1 3 2 6 4  j=8,i=1
//4 8 7 1 3 2 6 4  j=8,i=1
//4 8 7 1 3 2 6 8  j=8,i=2
//4 2 7 1 3 2 6 8  j=6,i=2
//4 2 7 1 3 7 6 8  j=6,i=3
//4 2 3 1 3 7 6 8  j=5,i=3
//4 2 3 1 3 7 6 8  j=5,i=5  break;
//4 2 3 1 5 7 6 8  a[5]=x=5