输入输出应该没问题，不知道快排算法坏在哪里？


//b1002.c
//printf("%.xd",y)就会输出y,宽度为x，不足则补零
#include <stdio.h>
void input(long *number,long k){
	char ch;
	int i;
	long a,b,sum;
	b=1000000;
	sum=0;
	for(i=0;i<7;i++){
		while((ch=getchar())=='-');
		if(ch<58)
			a=(ch-48);
		else if(ch<=80)
				a=(ch-59)/3;
		else
				a=(ch-60)/3;
		sum=sum+b*a;
		b/=10;
	}
	number[k]=sum;
	while((ch=getchar())!='\n');
}

void make_x_mid(long *b,long x,long y,long z){  //使b[x]取b[x],b[y],b[z]居中的值
	long mid ,temp;
	if(b[y]<=b[x]&&b[x]<=b[z])
		return;
	if(b[z]<=b[x]&&b[x]<=b[y])
		return;
	if(b[x]>b[y]){
		if(b[y]>=b[z])
			mid =y;
		else
			mid=z;
	}
	else{
		if(b[y]>=b[z])
			mid =z;
		else
			mid=y;
	}
	temp=b[x];
	b[x]=b[mid];
	b[mid]=temp;
}

void sort(long *number,long begin,long end){
	long low,high;
	long pivotkey;
	if(begin==end)
		return;
	low=begin;
	high=end;
	make_x_mid(number,low,(low+high)/2,high);
	pivotkey=number[low];//枢轴值
	while(low<high){
		while(low<high && number[high]>=pivotkey) 
			high--;
		number[low]=number[high];
		while(low<high && number[low]<=pivotkey)
			low++;
		number[high]=number[low];
	}
	number[low]=pivotkey;
	if(begin<low-1)
		sort(number,begin,low-1);
	if(low+1<end)
		sort(number,low+1,end);
}

void output(long *number,long n){
	long i;
	long time=0;
	long a=number[0];
	int tag=0;
	for(i=0;i<n;i++)
		if(number[i]==a)
			time++;
		else{
			if(time>1){
				printf("%.3ld-%.4ld %ld\n",a/10000,a%10000,time);
				tag=1;
			}
			a=number[i];
			time=1;
	}
	if(time>1){
		printf("%.3ld-%.4ld %ld\n",a/10000,a%10000,time);
		tag=1;
	}
	if(tag==0)
		printf("No duplicates.\n");
}
			
int main(){
	long n;
	long i;
	long number[100000];
	scanf("%ld",&n);
	getchar();
	for(i=0;i<n;i++)
		input(number,i);
	sort(number,0,n-1);
	output(number,n);
}
		

• 从这题和1113可以看出系统自带的qsort比自己写的快排效率要高很多啊!! (14) hoho 2004-05-05 17:18:41
  • 库函的效率不应该高太多 (92) farui 2004-05-05 22:06:19