算法笔记 第4章 入门篇(2) --算法初步 学习笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记 第4章 入门篇(2) --算法初步 学习笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4142字，纯文字阅读大概需要6分钟。

内容图文

4.1 排序

4.1.1 选择排序

简单选择排序是指，对一个序列A中的元素A[1] ~ A[n],令i从1到n枚举，进行n趟操作，每趟从待排序部分[i,n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]。

4.1.2 插入排序

直接插入排序是指，对序列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后，范围[1,i]有序。

4.1.3 排序题与sort函数的应用

直接使用C++中的sort()函数，效率较高

1.如何使用sort()排序

sort函数的使用必须加上头文件#include<algorithm>和using namespace std;

使用方式如下:

sort(首元素地址(必填),尾元素地址的下一个地址(必填),比较函数(非必填))

示例：

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int a[6] = {9,4,2,5,6,-1};
    sort(a,a+4);
    for(int i=0;i<6;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    sort(a,a+6);
    for(int i=0;i<6;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

 

sort的第三个可选参数是compare函数，一般写作cmp函数，用来制定排序规则来建立可比性

2.如何实现比较函数cmp

(1)基本数据类型数组的排序

若比较函数不填，则默认按照从小到大的顺序排序。如果想要从大到小来排序，则要使用比较函数cmp来“告诉”sort何时要交换元素。

#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){
    return a > b;
}
int main(){
    int a[] = {3,1,4,2};
    sort(a,a+4,cmp);
    for(int i=0;i<4;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

PAT A1025 PAT Ranking (25分)

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (≤), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (≤), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:

registration_number final_rank location_number local_rank

The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

Sample Input:

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85

Sample Output:

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct student{
    char id[20];
    int final_rank; //最终排名 
    int location_number; //考场号 
    int local_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;
    scanf("%d",&n);
    int count = 0;
    for(int i=1;i<=n;i++){
        int num;
        scanf("%d",&num);
        for(int j=0;j<num;j++){
            scanf("%s %d",stu[count].id,&stu[count].score);
            stu[count].location_number = i;
            count++;
        } 
        sort(stu+count-num,stu+count,cmp);
        int r=1;
        stu[count-num].local_rank = r;
        for(int j=count-num+1;j<count;j++){
            if(stu[j].score == stu[j-1].score){
                stu[j].local_rank = stu[j-1].local_rank;
                r++;
            }else{
                r++;
                stu[j].local_rank = r;
            }
        }
    }
    sort(stu,stu+count,cmp);
    int rank = 1;
    stu[0].final_rank = 1;
    for(int i=1;i<count;i++){
        if(stu[i].score == stu[i-1].score){
            stu[i].final_rank = stu[i-1].final_rank;
            rank++;
        }else{
            rank++;
            stu[i].final_rank = rank;
        }
    }
    printf("%d\n",count);
    for(int i=0;i<count;i++){
        printf("%s %d %d %d\n",stu[i].id,stu[i].final_rank,stu[i].location_number,stu[i].local_rank);
    }
    return 0;
}

 

?

内容总结

以上是互联网集市为您收集整理的算法笔记 第4章 入门篇(2) --算法初步 学习笔记全部内容，希望文章能够帮你解决算法笔记 第4章 入门篇(2) --算法初步 学习笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---