选择基准值:通常选择序列的第一个或最后一个元素作为基准值。
分区操作:重新排列序列,使得所有小于或等于基准值的元素都移到基准的左边,而所有大于基准值的元素都移到基准的右边。这一步完成后,基准值所在的位置就是其最终位置。
递归排序:递归地将小于基准值的子序列和大于基准值的子序列再次进行快速排序。
简而言之,就是将待排序集合分割成两个子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值。再对左右两子序列分别递归排序。
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int N,k,S=0,ptr = 0;
struct stu
{
string number;
int point;
int rank1;
int mark;
int rank2;
};
stu T[30005];
bool cmp(stu a,stu b)
{
if(a.point > b.point){
return true;
}
else if(a.point == b.point && a.number < b.number){
return true;
}
return false;
}
void distribute(int k,int flag = 0)
{
if(!flag){
for(int i=1;i <= k;i++){
if(i > 1 && T[ptr].point == T[ptr-1].point){
T[ptr].rank2 = T[ptr-1].rank2;
++ptr;
}
else
T[ptr++].rank2 = i;
}
}
else{
for(int i=0;i < k;i++){
if(i > 0 && T[i].point == T[i-1].point){
T[i].rank1 = T[i-1].rank1;
}
else
T[i].rank1 = i+1;
}
}
}
void ouput()
{
printf("%d\n",S);
for(int i=0;i < S;i++){
printf("%s %d %d %d\n",T[i].number.c_str(),T[i].rank1,T[i].mark,T[i].rank2);
}
}
void input()
{
int v=0;
for(int i=0;i < N;i++){
string number;
int point;
cin >> k;
S += k;
for(int j=0;j < k;j++){
cin >> number >> point;
T[v].number = number;
T[v].mark = i+1;
T[v++].point = point;
}
sort(T+S-k,T+S,cmp);
distribute(k);
}
sort(T,T+v,cmp);
distribute(v,1);
}
int main()
{
cin >> N;
input();
ouput();
return 0;
}