姓名： 尹思源
赛道： 基础组
类型： 算法技能
【排序】
关键词：1
sort函数
前置知识：并查集，贪心
\color{green}课前预习环节awa
点赞的每人奖励114514*0*42626246246*21421413525*1351525235元
#include<bits/stdc++.h>
using namespace std;
int main()
{
1 冒泡 ： 相邻两元素作比较，不满足条件交换
2 选择 ： 未排序序列选最值，放在已排序序列尾部
3 插入 ： 未排序序列中插入到已排序序列
4 桶排序：桶数组来存放排序数字
return 0;
}
\color{green}上课了
sort 函数
代码实现
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
int main()
{
int a[10] = {34,13,98,55,67};
sort(a+0,a+4+1);
for(int i = 0 ; i <= 4; i++)
{
cout << a[i] << " ";
}
return 0;
}
damn是这个代码是有问题的，所以我们写一个cmp(从大到小
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
bool cmp(int a , int b)
{
return a > b;
}
int main()
{
int a[10] = {34,13,98,55,67};
sort(a+0,a+4+1,cmp);
for(int i = 0 ; i <= 4; i++)
{
cout << a[i] << " ";
}
return 0;
}
cmp函数从小到大
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
bool cmp(int a , int b)
{
return a < b;
}
int main()
{
int a[10] = {34,13,98,55,67};
sort(a+0,a+4+1,cmp);
for(int i = 0 ; i <= 4; i++)
{
cout << a[i] << " ";
}
return 0;
}
将a数组从第5号元素到第9号元素做一个降序从大到小
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
bool cmp(int a , int b)
{
return a > b;
}
int main()
{
int a[10] = {34,13,98,55,67,234,996,6,1098,3};
sort(a+4,a+8,cmp);
for(int i = 5 ; i <= 9; i++)
{
cout << a[i] << " ";
}
return 0;
}
正经一点开始真正的知识点
课堂知识点
学习重点
一、各种排序算法的回顾以及综合应用
二、sort函数的使用介绍
思考题
前两节课的排序算法过程自己是否清楚？
写下你的思考：
你觉得这四种排序算法当中哪种思维比较符合你在现实生活当中的排序方式？ 写下你的思考：
排序综合问题
对于不同的排序相关问题，我们需要选择合适的排序算法去解决，特别是一些问题的解决需要涉及到排序过程的题目，这个时候就需要我们非常熟悉各种排序算法的过程了，建议同学们对冒泡、插入、选择、桶四种排序算法的过程再去好好的复习一下，本节课的题目涉及的基本上都是这些排序算法过程的题目。
sort函数的介绍与使用
在C++中，可以使用标准库中的sort函数进行排序。sort函数定义在头文件中，它可以对数组、向量、列表等STL容器中的元素进行排序。
sort函数的使用规则如下：
sort(first,last,cmp)
其中，first和last分别表示排序范围的首地址和尾地址+1，cmp是一个函数，它的作用是用于定义比较规则，我们可以对其进行重写，sort函数默认使用小于运算符进行排序，也可以通过自定义cmp函数来指定排序规则。
注意：当cmp函数省略时，默认是从小到大进行排序
关于first和last传入参数的问题：
有两种传入参数的方式：
sort(&a[0], &a[6]); 或者 sort(a, a+6);
一般来说都是使用后者，同学们传入的first和last一定要结合自己输入数据来判断
例如：
for(int i=1;i<=n;i++){
cin>>a[i]
}
sort(a+1,a+n+1);
当你使用数组的位置是从下标为1的位置时，使用sort排序的位置也要做出相应的修改
sort函数具体的使用方法如下：
下面的代码演示了如何使用sort函数对数组进行排序：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = { 5, 3, 1, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
输出结果为：1 2 3 4 5。
如果要按照自定义规则进行排序，可以提供一个比较函数作为sort函数的第三个参数。比较函数接受两个参数，返回一个bool值，表示两个参数的大小关系。如果第一个参数小于第二个参数，返回true，否则返回false。
例如，下面的代码演示了如何按照字符串长度进行排序：
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
bool cmp(string a, string b)
{
return a.size() < b.size();
}
int main()
{
string arr[] = { "hello", "world", "welcome", "to", "c++" };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n, cmp);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
输出结果为：to c++ hello world welcome。
注意：不使用万能头的同学一定要加上算法头文件#include
algorithm 单词的意思就是算法
题目环节
- 数组重排
题目ID：3304必做题100分
最新提交：
0 分
历史最高：
0 分
时间限制: 200ms
空间限制: 32768kB
题目描述
时间：0.2s 空间：32M
描述
给定n个数，请你将它们重新排列为x1, x2, x3, xn-1,xn, 来最大化 (x1-x2)+(x2-x3)+…+(xn-1-xn)。
输入格式
第一行一个整数 n。
第二行n个整数ai。2<=n<=100, |ai|<=1000
输出格式
重排过后的数列，请将第二个数至倒数第二个数进行升序排序。
样例输入
5
100 -100 50 0 -50
样例输出
100 -50 0 50 -100
####AC代码
\color{green}{蒟蒻又菜又爱玩 先给一个Wonderful Answer0}
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
int n;
int a[105];
bool cmp114514(int a , int b)//降序排序
{
return a > b;
}
bool cmpAkA(int m ,int n)//升序排序
{
return a < b;
}
int main()
{
cin >> n;
for(int i = 1; i <= n ; i++)
{
cin << a[i];
sort(a , a + n );//注意下标是1
cout << a[n] << " ";
}
for(int i = 2; i <= n-1; i++)
{
cout << a[i];
}
return 0;
}
\color{red}{错因很简单，下标是1，}
\color{blue}这个code也有肥肠大的问题
\color{red}{WA10分}
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
int n;
int a[105];
bool cmp114514(int a , int b)//降序排序
{
return a > b;
}
bool cmpAkA(int m ,int n)//升序排序
{
return a < b;
}
int main() {
cin >> n;
for(int i = 1; i <= n ; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);//注意下标是1
cout << a[1] << " ";
cout << a[n] << " ";
for(int i = 2; i <= n-1; i++) {
cout << a[i] << " ";
}
return 0;
}
\color{yellow}CE代码
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
int n;
int a[105];
bool cmp114514(int a , int b)//降序排序
{
return a > b;
}
bool cmpAkA(int m ,int n)//升序排序
{
return a < b;
}
int main() {
cin >> n;
for(int i = 1; i <= n ; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);//注意下标是1
cout << a[1] << " ";
cout << a[n] << " ";
for(int i = 2; i <= n-1; i++) {
cout << a[i] << " ";
}
cout << a[1] << " ";
return 0;
}
\color{green}改正原因：cmp函数有问题
\color{green}AC100分代码
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
int n;
int a[105];
int main() {
cin >> n;
for(int i = 1; i <= n ; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);//注意下标是1
cout << a[n] << " ";
for(int i = 2; i <= n-1; i++) {
cout << a[i] << " ";
}
cout << a[1] << " ";
return 0;
}
第2题
2. 中位数
题目ID：9157必做题100分
最新提交：0 分
历史最高：0 分
时间限制: 1000ms
空间限制: 256000kB
题目描述
时间：1 空间：256M
题目描述：
给出n个数，求他们的中位数。保证n是奇数。
输入格式：
第一行一个整数n，表示数字个数。
第二行n个整数。
输出格式：
一行一个数，中位数。
样例输入：
3 2 3 1
样例输出：
2
约定：
n≤1000
\color{red}{AC100}
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int n;
int a[1005];
int main() {
cin >> n;
for(int i = 1; i <= n ; i++)
{
cin >> a[i];
}
sort(a + 1 , a + n + 1);
cout << a[n/2+1] ;
return 0;
}
第三道
3. 字符串排序
题目ID：1161必做题100分
最新提交：
Running
0 分
历史最高：
Running
0 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
时间限制：1s 空间限制：64M
输入Ｎ（N<=1000）个学生的姓名，按英文字典的顺序排序输出。
输入格式：
第一行是整数N
接下来N行，每行包括一个名字
输出格式：
N行排序后的名字
样例输入：
3
abd
abc
bcd
样例输出：
abc
abd
bcd
ACcode
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int n;
string a[1005];
int main() {
cin >> n;
for(int i = 1; i <= n ; i++)
{
cin >> a[i];
}
sort(a + 1 , a + n + 1);
for(int i = 1 ; i <= n ; i++)
{
cout << a[i ] << endl;
}
return 0;
}
4. 双调序列
题目ID：9550必做题100分
最新提交：
Compile Error
0 分
历史最高：
Compile Error
0 分
时间限制: 100ms
空间限制: 131072kB
题目描述
题目描述：
XJ编程小组的童鞋们经常玩一些智力小游戏，某月某日，小朋友们又发明了一种新的序列：双调序列，所谓的双调呢主要是满足如下条件描述：
假定有n(n<=1000)个整数，双调序列的第一个数是n个整数中的最大数，第二个数是n个整数中的最小数，第三个数是n个数中的第二大数，第四个数是n个数中的第二小数……取过的数不能再取，依次类推，直到结束。
请你用程序正确的帮他找出这n个数的双调序列。
输入格式：
第1行为一个整数n。
接下来n行给出了题目中所述的n个整数，每行包含一个整数。
输出格式：
有n行，每行为一个整数，是满足条件的双调序列
样例输入 ：
5 10 -1 3 3 -9
样例输出 ：
10 -9 3 -1 3
约定：
1<=n<=1000
damn码提示：
\color{yellow}CE代码
#include <bits/stdc++.h>
//码风差 勿喷
#include <algorithm>
using namespace std;
int n;
int a[1005];
bool cmp(int a, int b) {
return a > b;
}
int main() {
cin >> n;
for(int i = 1; i <= n ; i++) {
cin >> a[i];
}
sort(a + 1 , a + n + 1 , cmp);
//输出双指针
if(n % 2 == 1) {
for(int i = 1 , j = n ;i < j; i++ ; j--) {
cout << a[i] << endl;
cout << a[j] << endl;
cout << a[n / 2 + 1];
}
}
else
{
for(int i = 1,j = n; i < j; i++ ; j--)
{
cout << a[i] << endl;
cout << a[j] << endl;
}
}
return 0;
}
\color{Green}AC Code
#include <bits/stdc++.h>
//码风差 勿喷
#include <algorithm>
using namespace std;
int n;
int a[1005];
bool cmp(int a, int b) {
return a > b;
}
int main() {
cin >> n;
for(int i = 1; i <= n ; i++) {
cin >> a[i];
}
sort(a + 1 , a + n + 1 , cmp);
//输出双指针
if(n % 2 == 1) {
for(int i = 1 , j = n ;i < j; i++ , j--) {
cout << a[i] << endl<< a[j] << endl;
}
cout << a[n / 2 + 1];
}
else
{
for(int i = 1,j = n; i < j; i++ , j--)
{
cout << a[i] << endl<< a[j] << endl;
}
}
return 0;
}