各种排序方法

本文转自http://blog.csdn.net/cnyali/article/details/43447771

//堆排序
#include<stdio.h>
#include<stdlib.h>
int a[100010],len=0;

void insert(int x){
	a[++len]=x;
	int k=len,t;
	while(k>1 && a[k]<a[k/2]){
		t=a[k];a[k]=a[k/2];a[k/2]=t;
		k=k/2;
	}
}
int main(){
	int i,j,k,m,n,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&k);
		insert(k);
	}
	for(i=1;i<=n;i++){
		printf("%d ",a[1]);
		a[1]=a[len];
		len--;
		k=1;
		while((a[k]>a[2*k] && 2*k<=len)|| (a[k]>a[2*k+1] && 2*k+1<=len)){
			m=2*k;
			if(a[m]>a[m+1] && m+1<=len)m++;
			t=a[k];a[k]=a[m];a[m]=t;
			k=m;
		}		
		for(j=1;j<=len;j++)printf("%d ",a[j]);
		puts("");
	}
	system("pause");
	return 0;
}

//高速排序
#include<stdio.h>
#include<stdlib.h>
int a[10000];
void qsort(int x,int y){
	int u,v,m,t;
	m=a[(x+y)/2];
	u=x;v=y;
	while(u<v){
		while(u<=v && a[u]<m)u++;
		while(u<=v && a[v]>m)v--;
		if(u<=v){
			t=a[u];a[u]=a[v];a[v]=t;
			u++;v--;
		}	
	} 
	if(x<v)qsort(x,v);
	if(u<y)qsort(u,y);
	
}
int main(){
	int i,j,k,m,n,max=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	srand(5143);
	int x,y;
	for(i=1;i<=n/2;i++){
		x=rand()%n;
		y=rand()%n;
		k=a[x];a[x]=a[y];a[y]=k;
	}
	qsort(1,n);
	for(i=1;i<=n;i++)
		printf("%d%c",a[i],i==n?'
':' ');
	system("pause");
	return 0;
}

//归并排序
#include<stdio.h>
#include<stdlib.h>
int a[10000];
void gbpx(int x,int y){
	int u,v,m,i;
	int t[10000];
	if(x==y)return;
	m=(x+y)/2;
	if(x<=m)gbpx(x,m);
	if(m+1<=y)gbpx(m+1,y);
	u=x;v=m+1;
	int k=0;
	while(u<=m && v<=y){
		if(a[u]<a[v]){
			t[++k]=a[u];
			u++;
		}else{
			t[++k]=a[v];
			v++;
		}
	}
	for(i=u;i<=m;i++)t[++k]=a[i];
	for(i=v;i<=y;i++)t[++k]=a[i];
	for(i=1;i<=k;i++)a[x+i-1]=t[i];
}
int main(){
	int i,j,k,m,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);	
	gbpx(1,n);	
	system("pause");
	return 0;
}

//二分查找
#include<stdio.h>
#include<stdlib.h>
int a[1000000+10];
int main(){
	int i,j,k,m,n,max=0;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int l=1,r=n;
	while(l<=r){
		m=(l+r)/2;
		if(a[m]==k){
			printf("%d",m);
			break;
		}else if(a[m]<k)
			l=m+1;
		else if(a[m]>k)
			r=m-1;		
	}
	if(l>r)printf("-1
");
	system("pause");
	return 0;
}

//统计排序
#include<stdio.h>
#include<stdlib.h>
int a[1000000+10];
int main(){
	int i,j,k,m,n,max=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&k);
		a[k]++;
		max=k>max?k:max;
	}
	for(i=0;i<=max;i++){
		for(j=1;j<=a[i];j++)
			printf("%d ",i);
	}	
	system("pause");
	return 0;
}

//冒泡排序
#include<stdio.h>
#include<stdlib.h>
int a[10000];
int main(){
	int i,j,k,m,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	for(i=n-1;i>=1;i--)
		for(j=1;j<=i;j++)
			if(a[j]>a[j+1]){
				k=a[j];a[j]=a[j+1];a[j+1]=k;
			}
	for(i=1;i<=n;i++)
		printf("%d%c",a[i],i==n?
'
':' ');
	system("pause");
	return 0;
}

//选择排序
#include<stdio.h>
#include<stdlib.h>
int a[10000];
int main(){
	int i,j,k,m,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
			if(a[i]>a[j]){
				k=a[i];a[i]=a[j];a[j]=k;
			}
	for(i=1;i<=n;i++)
		printf("%d%c",a[i],i==n?'
':' ');
	system("pause");
	return 0;
}