절 대기 시험 2007: EXCEL 정렬

http://acm.hdu.edu.cn/showproblem.php?pid=1862
 
Problem 설명 Excel 은 한 그룹의 기록 을 임의로 지정 한 열 에 따라 정렬 할 수 있 습 니 다.지금 프로그램 을 작성 하여 유사 한 기능 을 실현 하 십시오.  Input 테스트 입력 에는 몇 가지 테스트 용례 가 포함 되 어 있 습 니 다.각 테스트 용례 의 첫 번 째 줄 은 두 개의 정수 N (< = 100000) 과 C 를 포함 하 는데 그 중에서 N 은 기 록 된 개수 이 고 C 는 정렬 된 열 번 호 를 지정 합 니 다.다음은 N 줄 로 각 줄 에 학생 기록 이 하나씩 포함 되 어 있다.각 학생 기록 은 학 번 (6 자리 숫자, 같은 그룹 테스트 에서 중복 되 는 학 번 이 없 음), 이름 (8 자 를 넘 지 않 고 빈 칸 이 포함 되 지 않 은 문자열), 성적 (폐 구간 [0, 100] 내의 정수) 으로 구성 되 며 항목 마다 1 개의 빈 칸 으로 분리 된다.N = 0 까지 읽 었 을 때 모든 입력 이 끝나 면 해당 결 과 는 출력 하지 마 십시오.
Output 은 모든 테스트 용례 에 대해 먼저 1 줄 의 "Case i:" 를 출력 합 니 다. 그 중에서 i 는 테스트 용례 의 번호 (1 부터) 입 니 다.그 다음 에 N 줄 에서 요구 에 따라 정렬 한 결 과 를 출력 합 니 다. 즉, C = 1 일 때 학 번 에 따라 정렬 합 니 다.C = 2 시 이름 의 비 체감 사전 순서에 따라 정렬 합 니 다.C = 3 시 성적 의 비 체감 에 따라 정렬 합 니 다.몇몇 학생 들 이 같은 이름 이나 같은 성적 을 가지 고 있 을 때, 그들의 학 번 에 따라 점차 순 위 를 매 긴 다.
Sample Input 3 1 000007 James 85 000010 Amy 90 000001 Zoe 60 4 2 000007 James 85 000010 Amy 90 000001 Zoe 60 000002 James 98 4 3 000007 James 85 000010 Amy 90 000001 Zoe 60 000002 James 90 0 0
Sample Output Case 1: 000001 Zoe 60 000007 James 85 000010 Amy 90 Case 2: 000010 Amy 90 000002 James 98 000007 James 85 000001 Zoe 60 Case 3: 000001 Zoe 60 000007 James 85 000002 James 90 000010 Amy 90
 
이 문 제 는 오줌 을 쌌 습 니 다. 자신 이 쓴 슬 래 그 코드 는 거품 을 일 으 키 고 양 방향 거품 + flag 를 최적화 시 켰 습 니까? 아니면 TLE 를 사 용 했 습 니까?
역시 황소 키보드 에 있 는 댄서 의 알고리즘 을 봤 어 요.http://blog.csdn.net/libin56842/article/details/8509658라 이브 러 리 함수 qsort () 도 사용 할 수 있다 는 것 을 알 게 되 었 습 니 다. 코드 가 상당히 간결 하고 직접 AC 입 니 다.이름 으로 보아 빠 른 줄 일 것 이다.
그럼 문제 가 생 겼 습 니 다. 거품 이 아무리 최적화 되 더 라 도 간 의 복잡 도 는 n ^ 2 입 니까?나중에 연구 해.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 100001
typedef struct{
	int id;
	char name[9];
	int grade;
}STU;
STU stu[MAXN];

int cmp1(const STU* a,const STU* b){
	return ((*a).id - (*b).id);
}
int cmp2(const STU* a,const STU* b){
	if(strcmp((*a).name,(*b).name) < 0)
		return -1;
	if(strcmp((*a).name,(*b).name) == 0){
		if((*a).id < (*b).id)
			return -1;
	}
	return 1;
}
int cmp3(const STU* a,const STU* b){
	if((*a).grade < (*b).grade) 
		return -1;
	if((*a).grade == (*b).grade){
		if((*a).id < (*b).id)
			return -1;
	}
	return 1;
}
int main(){
	int N,C,i;
	int _case = 0;
	while(scanf("%d%d",&N,&C) && N){
		for(i = 1;i <= N;++i){
			scanf("%d%s%d",&stu[i].id,&stu[i].name,&stu[i].grade);
		}
		switch(C){
		case 1:
			qsort(&stu[1],N,sizeof(STU),cmp1);
			break;
		case 2:
			qsort(&stu[1],N,sizeof(STU),cmp2);
			break;
		case 3:
			qsort(&stu[1],N,sizeof(STU),cmp3);
			break;
		}
		printf("Case %d:
",++_case);
		for(i = 1;i <= N;++i){
			printf("%.6d %s %d
",stu[i].id,stu[i].name,stu[i].grade);
		}
	}
	return 0;
}