经典排序--快速排序、合并排序、堆排序

（一）快速排序

思想：用枢纽元素pivot将待排数组分成两个子表，左表中元素全都小于右表元素，，递归执行

int partition(int a[],int low,int high){
	int pivot=a[low];
	while(low=pivot) high--;
		a[low]=a[high];
		while(low

 （二）合并排序
思想：将数组分为两段，段内已经有序，主体部分就是将两个有序的子表借助一个辅助数组B合并成一个

void merge(int a[],int low,int mid,int high){ //A[low-mid],A[mid+1-high]已经分别有序 
	for(int k=low;k<=high;k++){
		b[k]=a[k];
	}
	for(int i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
		if(b[i]<=b[j]){
			a[k]=b[i];
			i++;
		}
		else{
			a[k]=b[j];
			j++;
		}
	}
	while(i<=mid) a[k++]=b[i++]; //注意：k+已经在上一个for循环里实现
	while(j<=high) a[k++]=b[j++]; 
} 
void mergesort(int a[],int low,int high){
	if(low>high) return ;
	int mid=(low+high)/2;
	mergesort(a,low,mid);       //一直划分子表 
	mergesort(a,mid+1,high);
	merge(a,low,mid,high);     //合并排序 
}


　（三）堆排序
思想：初始建立一个大根堆，后输出最大值后不断调整成堆的过程，三个函数实现

void adjustdown(int a[],int k,int len){  //以k为根的子树！，len为元素个数 
	int temp=a[k]; //暂存要向下调整的根结点的值
	for(int i=2*k;i<=len;i*=2){     //主体！！！！！！ 
		if(a[i]=a[i]) break; //跳出本轮循环，不需要下调 
		a[k]=a[i];
		k=i;         //k已经走到它的孩子结点，还要继续往下走 
	} 
	a[k]=temp;    
} 
void BuildMaxheap(int a[],int len){  //建立大根堆的实体代码 
	for(int i=len/2;i>0;i--){       //从第一个非叶子结点开始调整 
		adjustdown(a,i,len); 
	}
}
void heapsort(int a[],int len){
	BuildMaxheap(a,len);  //初始建堆
	for(int i=len;i>1;i--){
		swap(a[1],a[i]);  //根节点总是到最后
		adjustdown(a,1,i-1);  //将剩余结点调整成堆 
	} 
}