1015 德才论 (25)（25 分）
宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”
现给出一批考生的德才分数，请根据司马光的理论给出录取排名。
输入格式：
输入第1行给出3个正整数，分别为：N（<=10^5^），即考生总数；L（>=60），为录取最低分数线，即德分和才分均不低于L的考生才有资格被考虑录取；H（<100），为优先录取线——德分和才分均不低于此线的被定义为“才德全尽”，此类考生按德才总分从高到低排序；才分不到但德分到线的一类考生属于“德胜才”，也按总分排序，但排在第一类考生之后；德才分均低于H，但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者，按总分排序，但排在第二类考生之后；其他达到最低线L的考生也按总分排序，但排在第三类考生之后。
随后N行，每行给出一位考生的信息，包括：准考证号、德分、才分，其中准考证号为8位整数，德才分为区间[0, 100]内的整数。数字间以空格分隔。
输出格式：
输出第1行首先给出达到最低分数线的考生人数M，随后M行，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。
输入样例：
14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60
输出样例：
12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90
思考
c语言底下有algorithm这么方便的东西吗？
246-253页讲sort
GSview 6.0导出部分页pdf，再导出png，得到一页一页的png格式。
再配合chrome新浪微博图床插件，批量模式，一键复制markdown代码
c语言的cmp函数写法，与c++的cmp写法逻辑刚好相反，
c语言 return a>b，条件成立，则小的b在前，大的a在后，升序
c++如果return a>b，条件成立，则大的a在前，小的b在后，降序
AC代码
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
//#include <algorithm>
struct Student {
char id[10];
int de, cai, sum;
int flag;
}stu[100010];
int cmp(const void *a,const void *b) {
/*TDM-GCC 4.9.2 64-bit Release*/
//struct Student* aa=(Student*)a;
//struct Student* bb=(Student*)b;
/*c(gcc)*/
// struct Student* aa=a;这里有PAT编译器和本地编译器的区别
// struct Student* bb=b;
struct Student* aa=a;
struct Student* bb=b;
if(aa->flag != bb->flag) return (aa->flag > bb->flag)?1:-1;//类别小的在前面
else if(aa->sum != bb->sum) return (aa->sum < bb->sum)?1:-1;
else if(aa->de != bb->de) return (aa->de < bb->de)?1:-1;//到这没问题
else return strcmp(aa->id, bb->id);
}
int main() {
int n, L, H;
scanf("%d%d%d", &n, &L, &H);
int m = n;
for(int i = 0; i < n; i++) {
scanf("%s%d%d", stu[i].id, &stu[i].de, &stu[i].cai);
stu[i].sum = stu[i].de + stu[i].cai;
if(stu[i].de < L || stu[i].cai < L) {
stu[i].flag = 5;
m--;
}
else if(stu[i].de >= H && stu[i].cai >= H) stu[i].flag = 1;
else if(stu[i].de >= H && stu[i].cai < H) stu[i].flag = 2;
else if(stu[i].de >= stu[i].cai) stu[i].flag = 3;
else stu[i].flag = 4;
}
//sort(stu, stu + n, cmp);
/*void __cdecl qsort(void *_Base,size_t _NumOfElements,size_t _SizeOfElements,int (__cdecl *_PtFuncCompare)(const void *,const void *));*/
// int num = sizeof stu / sizeof (struct Student);
/*待排序的学生个数出问题了，num把开的数组所有元素都排序了一遍，是无意义的*/
qsort(stu,n,sizeof (struct Student),cmp);
printf("%d
", m);
for(int i = 0; i < m; i++) {
printf("%s %d %d
", stu[i].id, stu[i].de, stu[i].cai);
}
return 0;
}
胡凡讲sort
这里面讲了sort的方便的用法，可是纯c语言是不能写得这么方便的，要用指针。
c++用引用回避了指针，使入门更加简单。
c语言qsort例子
/*int数组从小到大排序*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int compare_ints(const void* a, const void* b){
int arg1 = *(const int*)a;
int arg2 = *(const int*)b;
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
// return (arg1 > arg2) - (arg1 < arg2); // possible shortcut // return arg1 - arg2; // erroneous shortcut (fails if INT_MIN is present)}
}
int main(void){
int ints[] = { -2, 99, 0, -743, 2, INT_MIN, 4 };
int size = sizeof ints / sizeof *ints;
qsort(ints, size, sizeof(int), compare_ints);
for (int i = 0; i < size; i++) {
printf("%d ", ints[i]);
}
printf("
");
}
qsort函数、sort函数 (精心整理篇)
qsort函数、sort函数 (精心整理篇)
先说明一下qsort和sort，只能对连续内存的数据进行排序，像链表这样的结构是无法排序的。
首先说一下， qsort
qsort（基本快速排序的方法，每次把数组分成两部分和中间的一个划分值，而对于有多个重复值的数组来说，基本快速排序的效率较低，且不稳定）。集成在C语言库函数里面的的qsort函数，使用 三 路划分的方法解决排序这个问题。所谓三路划分，是指把数组划分成小于划分值，等于划分值和大于划分值的三个部分。
具体介绍：-^^
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )
int compare (const void *elem1, const void *elem2 ) );
qsort（即，quicksort）主要根据你给的比较条件给一个快速排序，主要是通过指针移动实现排序功能。排序之后的结果仍然放在原来数组中。
参数意义如下:
第一个参数 base 是 需要排序的目标数组名（或者也可以理解成开始排序的地址，因为可以写&s[i]这样的表达式）
第二个参数 num 是 参与排序的目标数组元素个数
第三个参数 width 是单个元素的大小（或者目标数组中每一个元素长度），推荐使用sizeof(s[0]）这样的表达式
第四个参数 compare 就是让很多人觉得非常困惑的比较函数啦。
我们来简单讨论compare这个比较函数（写成compare是我的个人喜好，你可以随便写成什么，比如 cmp 什么的，在后面我会一直用cmp做解释）。
典型的compare的定义是int compare(const void *a,const void *b);
返回值必须是int，两个参数的类型必须都是const void *，那个a,b是随便写的，个人喜好。假设是对int排序的话，如果是升序，那么就是如果a比b大返回一个正值，小则负值，相等返回0，其他的依次类推，后面有例子来说明对不同的类型如何进行排序。
qsort 的使用方法：
一、对int类型数组排序
int num[100];
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b; //升序排序
//return *(int *)b - *(int *)a; //降序排序
/*可见：参数列表是两个空指针，现在他要去指向你的数组元素。所以转型为你当前的类型，然后取值。
升序排列时，若第一个参数指针指向的“值”大于第二个参数指针指向的“值”，则返回正；若第一个参数指针指向的“值”等于第二个参数指针指向的“值”，则返回零；若第一个参数指针指向的“值”小于第二个参数指针指向的“值”，则返回负。
降序排列时，则刚好相反。
*/
}
qsort(s,n,sizeof(s[0]),cmp);
示例完整函数（已在 VC6.0上运行通过）：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int s[10000],n,i;
int cmp(const void *a,const void *b)
{
return(*(int *)b-*(int *)a); //实现的是降序排序
}
int main()
{
// 输入想要输入的数的个数
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&s[i]);
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%d ",s[i]);
return(0);
}
二、对char类型数组排序（同int类型）
char word[100];
int cmp( const void *a , const void *b )
{
//注意，网上很多版本是 “ return *(char *)a - *(int *)b; ”
//因为编辑者的不用心，盲目copy，以讹传讹，传的一直是错的 *(int *)b
//应该是return *(char *)a - *(char *)b;
return *(char *)a - *(char *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
//附，可能 getchar(); 会派上用场
三、对double类型数组排序（特别要注意）
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
//返回值的问题，显然cmp返回的是一个整型，所以避免double返回小数而被丢失，用一个判断返回值。
}
qsort(in,100,sizeof(in[0]),cmp);
//附：排序结果的输出，一般建议用 “ %g ” 格式
/* 在这里多嘴一句，"%g"格式输出 虽然书上是说系统会自动选择 " %f " 格式 和 " %e " 格式 中长度较短的格式，并去掉无意义的0，但实际上系统如果选择了" %e "，系统会输出比 “ %e " 格式更省一位的格式输出。（此结论，来自VC6.0的实际操作）*/
四、对结构体一级排序
struct In{
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写
int cmp( const void *a ,const void *b){
return (*(In *)a).data > (*(In *)b).data ? 1 : -1;
//注意，这条语句在VC6.0环境下运行可能会出错，但是并不是语句错了，而是你要先 Build ，或者全部重建。总之语句是对的。
//或者你可以将这上面1条语句改成下面这3条语句
//struct In *aa = (In *)a;
//struct In *bb = (In *)b;
//return aa->data > bb->data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);
五、对结构体二级排序
struct In{
int x; //你可以比喻成：失败次数
int y; //你可以比喻成：成功次数
}s[100];
//按照x从小到大排序，当x相等时按照y从大到小排序。 你可以想象成：失败是主要因素的一个问题，先比较 失败次数少，失败次数相同 再看 成功次数多。
int cmp( const void *a , const void *b ){
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
六、对字符串进行排序
struct In{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
注意！qsort 中的 cmp 得自己写 。
再说说 sort （常用于 C++ ）
sort 使用时得注明：using namespace std; 或直接打 std::sort() 还得加上 #include
例：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[20];
for(int i=0;i<20;++i)
cin>>a[i];
sort(a,a+20); //范围，很明显这里是a+20 注意，这是必要的，如果是a+19
for(i=0;i<20;i++) //最后一个值a[19]就不会参与排序。
cout<<a[i]<<endl;
return 0;
}
std::sort是一个改进版的qsort. std::sort函数优于qsort的一些特点：对大数组采取9项取样，更完全的三路划分算法，更细致的对不同数组大小采用不同方法排序。
最后，我们来说说sort、qsort的区别：
sort是qsort的升级版，如果能用sort尽量用sort，使用也比较简单，不像qsort还得自己去写 cmp 函数，只要注明 使用的库函数就可以使用，参数只有两个（如果是普通用法）头指针和尾指针；
默认sort排序后是升序，如果想让他降序排列，可以使用自己编的cmp函数
#include<iostream>
#include<algorithm>
using namespace std;
int cmp(int a,int b)
{
if(a<b)
return 1; //升序排列，如果改为 a >b，则为降序,要注意sort()中cmp()的返值只有1和0，不像qsort中存在－1！！！！
else
return 0;
}
int main(){
int i;
int a[20];
for(int i=0;i<5;++i)
cin>>a[i];
sort(a,a+5,cmp); //范围，很明显这里是a+5 注意，这是必要的，如果是a+4最后一个值a[4]就不会参与排序。
for(i=0;i<5;i++)
cout<<a[i]<<endl;
system("pause");
return 0;
}
对二维数组的排序：
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
bool cmp(int *p,int *q)
{
if(p[0]==q[0])
{
if(p[1]==q[1])
{
return p[2]<q[2];
}
else return p[1]<q[1];
}
else return p[0]<q[0];
}
int main()
{
srand(time(0));
int i;
int **a=new int*[1000];
for(i=0;i<1000;++i)
{
a[i]=new int[3];
a[i][0]=rand()%1000;
a[i][1]=rand()%1000;
a[i][2]=rand()%1000;
//printf("%d %d %d
",a[i][0],a[i][1],a[i][2]);
}
sort(a,a+1000,cmp);
/*cout<<"After sort"<<endl;
for(i=0;i<1000;++i)
{
printf("%d %d %d
",a[i][0],a[i][1],a[i][2]);
}*/
return 0;
}
所以呢，有事没事，咱们也可以看看 C++
C语言标准库函数qsort那点小事
qsort包含在<stdlib.h>头文件中，此函数根据你给的比较条件进行快速排序，通过指针移动实现排序。排序之后的结果仍然放在原数组中。使用qsort函数必须自己写一个比较函数。
函数原型：
void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );
函数一共四个参数，没返回值。一个典型的qsort的写法如下:
void qsort(s,n,sizeof(s[0]),cmp);
其中第一个参数是参与排序的数组名（或者也可以理解成开始排序的地址，因为可以写&s[i]，这个问题下面有说明）；第二个参数是参与排序的元素个数； 第三个参数是单个元素的大小（推荐使用sizeof(s[0])这样的表达式，下面也有说明）；第四个参数就是很多人觉得非常困惑的比较函数，关于这个函数,还要说的比较麻烦...
下面来讨论cmp这个比较函数（写成cmp是我的个人喜好,你可以随便写成什么，比如qcmp什么的）。典型的cmp的定义是:
int cmp(const void *a,const void *b);
返回值必须是int，两个参数的类型必须都是const void *，那个a,b是我随便写的两个参数。 假设是对int排序的话，如果是升序，那么就是如果a比b大返回一个正值，小则负值，相等返回0，后面有例子来说明对不同的类型如何进行排序。
在函数体内要对a，b进行强制类型转换后才能得到正确的返回值，不同的类型有不同的处理方法。具体情况请参考后面的例子。
关于快排的一些小问题
1、快排是不稳定的，这个不稳定一个表现在其使用的时间是不确定的，最好情况(O(n))和最坏情况(O(n^2))差距太大，我们一般说的O(nlog(n))都是指的是其平均时间。
2、快排是不稳定的，这个不稳定表现在如果相同的比较元素，可能顺序不一样，假设我们有这样一个序列,3,3,3,但是这三个3是有区别的，我们标记为3a,3b,3c,快排后的结果不一定就是3a,3b,3c这样的排列，所以在某些特定场合我们要用结构体来使其稳定（No.6的例子就是说明这个问题的）。
3、快排的比较函数的两个参数必须都是const void *的,这个要特别注意，写a和b只是我的个人喜好，写成cmp也只是我的个人喜好。推荐在cmp里面重新定义两个指针来强制类型转换， 特别是在对结构体进行排序的时候。
4、快排qsort的第三个参数，那个sizeof，推荐是使用sizeof(s[0])这样，特别是对结构体，往往自己定义2*sizeof(int)这样的会出问题，用sizeof(s[0)既方便又保险。
5、如果要对数组进行部分排序，比如对一个s[n]的数组排列其从s[i]开始的m个元素，只需要在第一个和第二个参数上进行一些修改:
void qsort(&s[i],m,sizeof(s[i]),cmp);
标程，举例说明
No.1、手工实现QuickSort:
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
#include<stdio.h>
#include<stdlib.h>
void QuickSort(int *A,int left,int right)
{
if(left>=right) return;
int x=A[(left+right)>>1],low=left,high=right;
while(low<high)
{
while(A[low]<x)
low++;
while(A[high]>x)
high--;
if(low<=high)
{
int Temp=A[low];
A[low]=A[high];
A[high]=Temp;
low++;
high--;
}
}
QuickSort(A,left,high);
QuickSort(A,low,right);
}
int main()
{
int length,i,r[10000];
scanf("%d",&length);
for(i=1;i<=length;i++)
scanf("%d",&r[i]);
QuickSort(r,1,length);
for(i=1;i<=length;i++)
printf(" %d",r[i]);
printf("
");
system("pause");
return 0;
}
或者：
#include<stdio.h>
#include<stdlib.h>
int QKPass(int r[],int left,int right)
{
int low,high,x;
x=r[left];//选择基准记录
low=left;
high=right;
while(low<high)
{
while(low<high&&r[high]>=x)//从右到左找到小于x的记录
high--;
if(low<high)
{
r[low]=r[high];//找到后进行替换
low++;
}
while(low<high&&r[low]<x)
{
low++;
}
if(low<high)
{
r[high]=r[low];
high--;
}
r[low]=x;//将基准记录保存在low=high的位置
return low;//返回基准记录的位置
}
}
int QKSort(int r[],int low,int high)
{
int pos;
if(low<high)
{
pos=QKPass(r,low,high);
QKSort(r,low,pos-1);
QKSort(r,pos+1,high);
}
}
int main()
{
int length,i,r[10000];
scanf("%d",&length);
for(i=1;i<=length;i++)
scanf("%d",&r[i]);
QKSort(r,1,length);
for(i=1;i<=length;i++)
printf("%-3d",r[i]);
printf("
");
system("pause");
return 0;
}
No.2、最常见的，对int数组排序 :
#include<stdio.h>
#include<stdlib.h>
int s[10000],n,i;
int cmp(const void *a, const void *b)
{
return(*(int *)a-*(int *)b); //升序
//return(*(int *)b-*(int *)a); //降序
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&s[i]);
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%d ",s[i]);
printf("
");
system("pause");
return 0;
}
No.3、对double型数组排序，原理同int：
这里做个注释，本来是因为要判断如果a==b返回0的，但是严格来说，两个double数是不可能相等的，只能说fabs(a-b)<1e-20之类的这样来判断，所以这里只返回了1和-1
#include<stdio.h>
#include<stdlib.h>
double s[1000];
int i,n;
int cmp(const void * a, const void * b)
{
return((*(double*)a-*(double*)b>0)?1:-1); //升序
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf",&s[i]);
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%.2lf ",s[i]);
printf("
");
system("pause");
return(0);
}
No.4、对一个字符数组排序.原理同int:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[10000],i,n;
int cmp(const void *a,const void *b)
{
return(*(char *)a-*(char *)b); //升序
}
int main()
{
scanf("%s",s);
n=strlen(s);
qsort(s,n,sizeof(s[0]),cmp);
printf("%s",s);
printf("
");
system("pause");
return 0;
}
No.5、对结构体排序（一级排序）:
很多时候我们都会对结构体排序，比如2010年校赛的那个根据几个参数排序，一般这个时候都在cmp函数里面先强制转换了类型，不要在return里面转换，我也说不清为什么，但是这样程序会更清晰，并且绝对是没错的。 这里同样请注意double返回0的问题:
#include<stdio.h>
#include<stdlib.h>
struct node {
double data;
int no;
} s[100];
int i,n;
int cmp(const void *a,const void *b) {
struct node *aa=(node *)a;
struct node *bb=(node *)b;
return(((aa->data)>(bb->data))?1:-1);//升序
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
s[i].no=i+1;
scanf("%lf",&s[i].data);
}
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%d %lf
",s[i].no,s[i].data);
system("pause");
return 0;
}
No.6、对结构体排序（二级排序）。
加入no来使其稳定（即data值相等的情况下按原来的顺序排）:
#include<stdio.h>
#include<stdlib.h>
struct node
{
double data;
int no;
} s[100];
int i,n;
int cmp(const void *a,const void *b)
{
struct node *aa=(node *)a;
struct node *bb=(node *)b;
if(aa->data!=bb->data)
return(((aa->data)>(bb->data))?1:-1);
else
return((aa->no)-(bb->no));
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
s[i].no=i+1;
scanf("%lf",&s[i].data);
}
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%d %lf
",s[i].no,s[i].data);
printf("
");
system("pause");
return 0;
}
如果有字符串的话，就这样写：
int cmp(const void *a,const void *b)
{
struct node *aa=(node *)a;
struct node *bb=(node *)b;
if(aa->data!=bb->data)
return(((aa->data)>(bb->data))?1:-1);
else
return((aa->no)-(bb->no));
else
return strcmp(aa.str,bb.str);
//return strcmp(aa->str,bb->str);
//按照结构体中字符串str的字典顺序排序
}
No.7、对字符串数组的排序（char s[][]型）:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[100][100];
int i,n;
int cmp(const void *a,const void *b)
{
return(strcmp((char*)a,(char*)b));
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s",s[i]);
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%s
",s[i]);
printf("
");
system("pause");
return 0;
}
No.8、对字符串数组排序（char *s[]型）:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char *s[100];
int i,n;
int cmp(const void *a,const void *b)
{
return(strcmp(*(char**)a,*(char**)b));
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
s[i]=(char*)malloc(sizeof(char*));
scanf("%s",s[i]);
}
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
printf("%s
",s[i]);
printf("
");
system("pause");
return 0;
}