算法-查找排序-之成绩排序

 

 分析和思路：

把成绩保存到map或者vector中，然后进行排序。这道题关键是处理那个成绩相等时，排序后依然保持相对顺序不变的问题，费了好大的心思，发现效果依然不是自己想要的，写出的代码如下：

 1 #include "iostream"
 2 #include 
 3 #include 
 4 #include "algorithm"
 5 #include 
 6 using namespace std;
 7 int main()
 8 {
 9     
10     int number=0;
11     int mode=0;
12     //cin>>number;
13     //cin>>mode;
14     string name;int score;
15    
16    
17     while(cin>>number>>mode)
18     {
19          vector<int> vector_score;
20         //std::unordered_map mymap={"key",111};
21          unordered_map<string,int> m;
22          int i=0;//注意细节
23         while(i<number)
24         {
25             cin>>name;
26             cin>>score;
27             vector_score.push_back(score);
28             m[name]=score;
29             i++;
30         }
31     sort(vector_score.begin(),vector_score.end());
32   //     printf("v size%d",vector_score.size());
33    //     printf("m size%d",m.size());
34     if(mode==1)
35     {
36          for(int i=0;i)
37         {
38             for(auto iter=m.begin();iter!=m.end();iter++)
39             {
40                 if(iter->second==vector_score[i])
41                 {
42                     cout<first<<" "<endl;
43                     m.erase(iter->first);
44                     iter=m.begin();
45                     break;
46                 }
47             }
48        }
49         m.clear();
50         vector_score.clear();
51     }
52     else if(mode==0)
53     {
54         for(int i=vector_score.size()-1;i>=0;i--)
55         {
56             for(auto iter=m.begin();iter!=m.end();iter++)
57             {
58                 if(iter->second==vector_score[i])
59                 {
60                     cout<first<<" "<endl;
61                     m.erase(iter->first);
62                     iter=m.begin();
63                     break;
64                 }
65             }
66        }
67          m.clear();
68         vector_score.clear();
69     }
70    }
71     
72   return 0;
73     
74 }

想通过vector元素的顺序来确定map中元素的顺序，但是依然是map自动排序了。

解决办法：使用稳定排序stable_sort，改进后的代码如下：

 1 #include 
 2 #include <string>
 3 #include 
 4 #include 
 5 //#include 
 6 using namespace std;
 7  
 8 bool cmp0(const pair<string,int> &a,const pair<string,int> &b)
 9 {
10     return a.second>b.second;
11 }
12  
13 bool cmp1(const pair<string,int> &a,const pair<string,int> &b)
14 {
15     return a.second<b.second;
16 }
17  
18 void mysort(int n,int flag)
19 {
20     //unordered_map res;
21     vectorstring,int>> res(n);
22     for(int i=0;i)
23     {
24         cin>>res[i].first>>res[i].second;
25     }
26     if(flag==0)
27     {
28         stable_sort(res.begin(),res.end(),cmp0);
29     }
30     else if(flag==1)
31     {
32         stable_sort(res.begin(),res.end(),cmp1);
33     }
34  
35     for(int i=0;i)
36     {
37         cout<" "<endl;
38     }
39 }
40  
41 int main()
42 {
43     int n,flag;
44     while(cin>>n>>flag)
45     {
46         mysort(n,flag);
47     }
48     return 0;
49 }

总结：这个程序言简意赅，非常高效，值得借鉴和学习。pair这个结构作用挺好，对vector和map都适用，注意它的用法。

算法

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

标签