一、关于排序
1.什么是排序
排序就是将一个数组中的元素按规定顺序排序,比如:从小到大,从大到小等。而sort排序会比一些排序速度要快,也就是冒泡,选择等。
2.怎么排序
选择排序的使用
这里为什么要提选择排序呢?因为这里需要稍稍引入一下,不想看可以跳过。
下图是一个数组,他是完全乱的:
9 2 8 4 3 6 |
我们可以记一个公式,左大右小交换,看上图,因为9>2,所以交换,也就是说变成了:
2 9 8 4 3 6 |
以此类推,直到变成:
2 3 4 6 8 9 |
根据这个公式可以写出以下程序:
#include<iostream>
using namespace std;
int a[100];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]; //输入
for(int i=1;i<=n;i++){ //i从一遍历到n
for(int j=i+1;j<=n;j++){ //j从i+1遍历到n
if(a[i]>a[j]) swap(a[i],a[j]); //左小右大,交换
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<" "; //输出
return 0;
}
运行后就是这样的:
"5"表示了数组中有多少元素,"9 3 2 7 5"是这个数组,"2 3 5 7 9"是从小到大排序后的数组。
#include<algorithm>
在这当中,我运用了一个函数,就是swap函数,他是用来交换两个数的位置,就像这样:
swap(第一个数,第二个数);
在文中就是交换a[i]和a[j]的位置。
至此,选择排序就告一段落了。
sort排序的使用
我相信能来到这里的人对排序都有基本的了解了,我就不再多说了,直接开始讲解程序。
首先,我们需要动用sort就需要一个头文件:
#include<algorithm>
sort是这样使用的:
sort(起始位置,结束位置,排序方式);
注:排序方式常用cmp表示,cmp默认为从小到大,如果你想从小到大排序,可以不写cmp。如果你用其他方式,就要手写cmp。如果还不懂,就去看代码。
接下来来看下cmp的写法:
bool cmp(int a,int b){ //cmp是布尔类型的
return a>b; //这里想按什么顺序排序就retun什么
}
现在已经全部学完,我们来看下完整代码:
#include<iostream>
#include<algorithm>
using namespace std;
int a[100];
bool cmp(int a,int b){ //cmp是布尔类型的
return a>b; //这里想按什么顺序排序就return什么
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n); //从小到大
for(int i=0;i<n;i++) cout<<a[i]<<" ";
cout<<endl;
sort(a,a+n,cmp); //从大到小
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}
运行后是这样的:
"5"表示了数组中有多少元素,"9 4 3 8 6"是这个数组,"3 4 6 8 9"是从小到大排序后的数组,"9 8 6 4 3"是从大到小排序后的数组。
二、例题展示
上题目:
我们就直接上代码:
#include<iostream>
#include<algorithm>
using namespace std;
int a[5000005];
int main(){
int n,k;
scanf("%d %d",&n,&k); 要用scanf和printf不然会超时
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n); //因为是第k"小"的数所以要从小到大
printf("%d",a[k]); //最后输出a数组中第k
return 0;
}
下期想看什么,记得说