入门篇（2）-算法初步-排序
1， 选择排序
对一个序列A中的元素A[1]~A[n],令i从1到n枚举，进行n趟操作，
每趟从待排序部分[i,n]中选择最小的元素。令其与其待排序部分的第一个元素A[i]进行交换，
这样元素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]，于是在n趟操作后，所有元素就会是有序的。
总共进行n趟操作（1<=i<=n）,每趟操作选出排序部分[i,n]中最小的元素，令其与A[i]交换
#include<cstdio>
using namespace std;
void selectSort(){
for(int i=1;i<=n;i++){
int k=i;
for(int j=i;j<=n;j++){
if(A[j]<A[k]){
k=j;
}
}
int temp=A[i];
A[i] =A[k];
A[k]=temp;
}
}
4.1插入排序
? 插入排序中的直接插入排序。
直接插入排序是对序列A的n个元素A[1]~A[n],令i从2到n枚举，进行n-1趟操作。
假设某一趟时，序列A的前i-1个元素A[1]A[i-1]已经有序，而范围[i,n]还未有序，那么从该趟从范围[1,i-1]中寻找某个位置j，使得将A[i]插入位置j后（此时A[j]A[i-1]会后移一位至A[j+1]~A[i]）,范围[1,i]有序
插入排序是将待插入元素一个个插入初始已有序部分的过程，而插入位置的选择遵循了是插入后仍然保持有序的原则，具体做法一般是从后往前枚举已有序部分来确定插入位置
int A[maxn],n;
void insertSort(){
for(int i=2;i<=n;i++){
int temp=A[i],j=i;
while(j>1&&temp<A[j]){
A[j]=A[j-1];
j--;
}
A[j]=temp;
}
}
4.1.3 C++中的sort()函数
（1）结构体：
const int M=100010;
struct Student{
char name[10]; //姓名
char id[10]; //准考证号
int score ; //分数
int rank; //排名
}stu[M];
（2）cmp函数的编写
bool cmp(Student a, Student b) {
if(a.score != b.score)
return a.score >b.score;
else
return strcmp(a.name,b.name)<0;
// return strcmp(a.name,b.name)==-1 是错误的写法。
}
strcmp（）函数是string.h头文件下用来比较两个char型数组的字典序大小的，
strcmp(str1，str2)；
（1）当str1字典序小于str2时返回一个负数
(2)当str1字典序等于str2时返回一个0
（3）当str1字典序大于str2时返回一个正数
strcpy(字符数组1，字符数组2)； 把字符数组2复制给字符数组1，包括结束符
#include <cstdio>
#include <cstring>
#include <algorithm>
const int max =100010;
using namespace std;
struct Student {
char id[15]; //准考证号
int score; //分数
int location_number; // 考场号
int local_rank; //考场内排名
}stu[1000010];
bool cmp(Student a, Student b){
if(a.score != b.score)
return a.score>b.score;
else
return a.id<b.id;
}
//这个考场的考生所对应的数组下标便为区间【num-k,num)
int main(){
int n,k,num =0; //num为考生人数 ，从0开始
scanf("%d",&n);
for(int i=1;i<=n;i++){ // 有两个考场
scanf("%d",&k); //考场内人数
for(int j=0;j<k;j++){
scanf("%s %d",stu[num].id,&stu[num].score);
stu[num].location_number=i; // 该考生的考场号为i
num++; //总考生数+1
}
sort(stu+num-k,stu+num,cmp);
stu[num-k].local_rank=1; //该考场的第一名考生先排名记为1
for(int j=num-k;j<num;j++){ // 对该考场剩余的考生,从最后一名开始
if(stu[j].score == stu[j-1].score){
stu[j].local_rank=stu[j-1].local_rank;
} else{
stu[j].local_rank=j+1-(num-k);
}
}
}
printf("%d\n",num); // 输出所有的考生人数
sort(stu,stu+num,cmp);
int r=1; //当前的考生排名
for(int i=0;i<num;i++){
if(i>0 && stu[i].score !=stu[i-1].score){
r=i+1; //当前考生与上一个考生分属不同时，让r更新为人数+1
}
printf("%s ",stu[i].id);
printf("%d %d %d\n",stu[i].location_number,stu[i].local_rank) ;
}
return 0;
}
|