quicksort.cpp

快速排序 基本思想：通过一趟排序

#include <iostream>
#include<iomanip>
#include <stdlib.h>
#define NUM 20
using namespace std;
cmp(const void *a, const void *b)
{
	if(*(int *)a>*(int *)b) return 1;
	else if(*(int *)a==*(int *)b) return 0;
	else return -1;
}
void main()
{
	int i;
	int a[NUM];
	for(i=0;i<NUM;i++)
		a[i]=rand()%100;
	qsort(a,sizeof(a)/sizeof(int),sizeof(int),cmp);
	for(i=0;i<sizeof(a)/sizeof(int);i++)
		cout<<setw(5)<<a[i]<<',';
	cout<<endl;
}
int partion(int r[],int i,int j)
{  
	int x;
	x=r[i];
	while(i<j)
	{  
		while(i<j && x<=r[j])  
			j--;
		if(i<j) 
		{ 
			r[i]=r[j]; 
	        i++; 
		}
		while(i<j && r[i]<=x)  
			i++;
        if(i<j) 
		{ 
			r[j]=r[i]; 
	        j--;
		}
   }
   r[i]=x;
   return i;
}
void qsort(int r[],int l,int h)
{
   int m;
   if(l<h) 
   { 
	   m=partion(r,l,h);
	   qsort(r,l,m-1);
	   qsort(r,m+1,h); 
   }
}

void quiksort(int r[],int n)
{
	qsort(r,0,n-1);
}