经典算法题之成绩排序C-526互联

#include<stdio.h>
typedef struct node{
    int num;
    int data;
}student;

int divide1(student A[],int head,int tail){
    if(head==tail) return head;
    int t=A[head].data;
    int x=A[head].num;
    while(head<tail){
        while(head < tail && A[tail].data > t) tail--;
        if(head != tail) A[head++]=A[tail];
        while(head < tail && A[head].data < t) head++;
        if(head != tail) A[tail--]=A[head];
    }
    A[head].num = x;
    A[head].data= t;
    return head;
}

int divide2(student A[],int head,int tail){
    if(head==tail) return head;
    int t=A[head].num;
    int x=A[head].data;
    while(head<tail){
        while(head < tail && A[tail].num > t) tail--;
        if(head != tail) A[head++]=A[tail];
        while(head < tail && A[head].num < t) head++;
        if(head != tail) A[tail--]=A[head];
    }
    A[head].num = t;
    A[head].data= x;
    return head;
}

void quicksort(student A[],int head,int tail,int tag){
    if(head >= tail) return;
    int t ;
    if(tag==1){
        t= divide1(A,head,tail);
    }else{
        t= divide2(A,head,tail);
    }
    if(t>head)  quicksort(A,head,t-1,tag);
    if(t<tail) quicksort(A,t+1,tail,tag);
}

int main (){
    student A[101];
    int n = 0 ;
    while(scanf("%d",&n) != EOF){
        for(int i = 0 ; i < n ; i++){
            scanf("%d %d",&A[i].num,&A[i].data);
        }
        quicksort(A,0,n-1,1);
        int head = 0 ;
        while(head<n){
            int t=head+1;
            while(A[head].data==A[t].data && t < n) {
                t++;
            }
            if( t!=head+1 ) quicksort(A,head,t-1,0);
            head=t;
        }
        for(int i = 0 ; i < n ; i++){
            printf("%d %d\n",A[i].num,A[i].data);
        }
    }

    return 0;
}

结果如下：

算法