前情回顾-冒泡排序（语言篇）
冒泡排序是排序中最基本的一种方法，虽然在写题时我们一般不会去使用它，但我觉得了解冒泡排序算法的实现原理确实非常必要的。
冒泡排序的本质在于交换，即每次通过交换的方式把当前剩余元素的最大值移动到一端，当剩余元素为0时，排序结束。
1.简单选择排序
① 数组A中元素A[1]~A[N]，
② 令 i 从 1 到 n 进行 n 趟操作，每趟操作从A[i]~A[N]中选出一个最小的元素，
③ 令其与待排序部分的第一个元素A[i]交换，最后所有元素有序。
#include<stdio.h> int main(){ int a[100]; int n; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } int min=9999; for(int i=0;i<n;i++){ int mi; for(int j=i;j<n;j++){ if(a[j]<min){ min=a[j]; mi=j; } } int temp=a[i]; a[i]=a[mi]; a[mi]=temp; } for(int i=0;i<n;i++){ printf("%d ",a[i]); } return 0; }
2.直接插入排序
前一部分为有序数列，后一部分为无序数列，
把无序部分的第一个元素放入有序部分，找到合适的位置，
这个过程中有序部分可能需要进行后移操作，直至操作n-1趟。
#include<stdio.h> int main(){ int n; int a[100]; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=2;i<=n;i++){ int temp=a[i],j=i; while(j>1&&temp<a[j-1]){ a[j]=a[j-1]; j--; } a[j]=temp; } for(int i=1;i<=n;i++){ printf("%d ",a[i]); } return 0; }
3.sort排序（排序神器）
sort()函数是C++中用于排序的一个函数，比较高效。
如何使用sort排序：
①需加头文件#include<algorithm>和using namespace std;
②sort(首元素地址，尾元素的下一个地址，比较函数（可选）)
sort函数的参数有三个，其中前两个是必填的，比较函数可以根据需要填写。
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int a[6]={9,4,2,5,6,-1}; sort(a,a+4);//将a[0]-a[3]从小到大排序 for(int i=0;i<4;i++){ printf("%d ",a[i]); } printf(" "); sort(a,a+6); for(int i=0;i<6;i++){ printf("%d ",a[i]); } return 0; }
如何实现比较函数cmp：
sort函数默认是将数组进行从小到大的排序，如果想要从大到小排序，则需要使用比较函数cmp来实现。
#include<stdio.h> #include<algorithm> using namespace std; bool cmp(int a,int b){ return a>b; } int main(){ int a[6]={9,4,2,5,6,-1}; sort(a,a+4,cmp);//将a[0]-a[3]从大到小排序 for(int i=0;i<4;i++){ printf("%d ",a[i]); } printf(" "); sort(a,a+6,cmp); for(int i=0;i<6;i++){ printf("%d ",a[i]); } return 0; }
结构体数组的排序：
可以按照结构体内的元素的大小进行排序
#include<stdio.h> #include<algorithm> using namespace std; struct node{ int x,y; }ssd[10]; bool cmp(node a,node b){ return a.x>b.x;//按照x从大到小排序 } int main(){ ssd[0].x=2; ssd[0].y=2; ssd[1].x=1; ssd[1].y=3; ssd[2].x=3; ssd[2].y=1; sort(ssd,ssd+3,cmp); for(int i=0;i<3;i++){ printf("%d %d ",ssd[i].x,ssd[i].y); } return 0; }
如果想先按x从大到小排序，如果x相等，则按y从小到大排序（二级排序），则cmp的写法为：
bool cmp(node a,node b){ if(a.x!=b.x) return a.x>b.x;//按照x从大到小排序 else return a.y<b.y; }
4.复杂的结构体排序：
自己尝试了几次，没有通过全部样例，id我原本采用long long 存储，无法通过，只能用字符串。
题目大意：
n个考场，每个考场m个学生，输入学生学号和成绩，进行考场内排序和总的排序。输出内容：学号，总名次，考场号，考场内名次
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct student{ char id[15]; int loc_num; int loc_rank; int score; }stu[30010]; bool cmp(student a,student b){ if(a.score!=b.score) return a.score>b.score; else return strcmp(a.id,b.id)<0; } int main(){ int n;//n为考场数 int m;//m为考场内人数 int k=0;//k为考生总数 scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&m); for(int j=0;j<m;j++){ scanf("%s %d",stu[k].id,&stu[k].score); stu[k].loc_num=i; k++; } sort(stu+k-m,stu+k,cmp); stu[k-m].loc_rank=1; for(int j=k-m+1;j<k;j++){ if(stu[j].score==stu[j-1].score){ stu[j].loc_rank=stu[j-1].loc_rank; }else{ stu[j].loc_rank=j+1-(k-m); } } } printf("%d ",k); sort(stu,stu+k,cmp); int r=1; for(int i=0;i<k;i++){ if(i>0&&stu[i].score!=stu[i-1].score) r=i+1; printf("%s ",stu[i].id); printf("%d %d %d ",r,stu[i].loc_num,stu[i].loc_rank); } return 0; }