quicksort.c

快速排序

#include <stdio.h>
#include "buildarray.c"
#include "sort.h"

unsigned long int compare=0,move=0;


swap(int *p1,int *p2)
{
	int temp;
	temp=*p1;
	*p1=*p2;
	*p2=temp;
	move+=3;	
}


int Median3(int *p,int Left,int Right)
{
	int Center=(Left+Right)/2;
	if(*(p+Left)>*(p+Center)){
		compare++;
		swap(p+Left,p+Center);
	}
	if(*(p+Left)>*(p+Right)){
		compare++;
		swap(p+Left,p+Right);
	}
	if(*(p+Center)>*(p+Right)){
		compare++;
		swap(p+Center,p+Right);
	}
	swap(p+Center,p+Right-1);
	return *(p+Right-1);
}


void QuickSort(int *p,int n,int Left,int Right)
{
	int i,j;
	int Pivot;
	if(Left+2<=Right){
		Pivot=Median3(p,Left,Right);
		i=Left;j=Right-1;
		for(;;){
			while(*(p+(++i))<Pivot){compare++;}
			while(*(p+(--j))>Pivot){compare++;}
			if(i<j)
				swap((p+i),(p+j));
			else break;
		}
		swap((p+i),(p+Right-1));
		QuickSort(p,n,Left,i-1);
		QuickSort(p,n,i+1,Right);
	}
	else{
		(*(p+Left)<*(p+Right))?:swap((p+Left),(p+Right));
		compare++;
	}
}


main()
{
	//int n=9;
	int i,count=0;
	int *p;
	p=BuildArray();
	//int Queue[9]={8,5,6,9,2,1,3,4,7};
	QuickSort(p,NUM,0,NUM-1);
	printf("the queue sorted by quicksort is:\n");
	for(i=0;i<NUM;i++){
		printf("%d	",*(p+i));
		count++;
		if(count%10==0)
		printf("\n");
	}
	printf("QuickSort compare=%ld,move=%ld",compare,move);
	printf("\n");	
}