| 接口 |
说明 |
| sort |
对给定区间所有元素进行排序 |
| stable_sort |
对给定区间所有元素进行稳定排序 |
| partial_sort |
对给定区间所有元素部分排序 |
| partial_sort_copy |
对给定区间复制并排序 |
| nth_element |
找出给定区间的某个位置对应的元素 |
| is_sorted |
判断一个区间是否已经排好序 |
| partition |
使得符合某个条件的元素放在前面 |
| stable_partition |
相对稳定的使得符合某个条件的元素放在前面 |
需要头文件
语法描述：sort（begin，end，cmp），cmp参数可以没有，如果没有默认非降序排序。
以int为例的基本数据类型的sort使用
1
2
3
4
5
6
7
8
9
10
11
12
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int a[5]={1,3,4,2,5};
sort(a,a+5);
for(int i=0;i<5;i++)
cout<<a[i]<<' ';
return 0;
}
|
因为没有cmp参数，默认为非降序排序，结果为：1 2 3 4 5
若设计为非升序排序，则cmp函数的编写：
1
2
3
4
| bool cmp（int a,int b）
{
return a>b;
}
|
对于简单的任务（类型支持“<”、“>”等比较运算符），完全没必要自己写function。标准库里已经有现成的了，就在functional里，include进来就行了。functional提供了一堆基于模板的比较函数对象。它们是（看名字就知道意思了）：equal_to、not_equal_to、greater、greater_equal、less、less_equal。对于这个问题来说，greater和less就足够了，直接拿过来用：
1
2
3
4
5
6
7
8
9
10
11
12
|
int main ( )
{
int a[20]={2,4,1,23,5,76,0,43,24,65},i;
for(i=0;i<20;i++)
cout<<a[i]<<endl;
sort(a,a+20,greater<int>());
for(i=0;i<20;i++)
cout<<a[i]<<endl;
return 0;
}
|
一个字符串内部字符排序, 使用迭代器可以完成顺序排序:
1
2
3
4
5
6
7
8
9
10
11
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
string str("hello world");
sort(str.begin(),str.end());
cout<<str;
return 0;
}
|
结果：空格dehllloorw
使用反向迭代器可以完成逆序排序:
1
2
3
4
5
6
7
8
9
10
11
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
string str("hello world");
sort(str.rbegin(),str.rend());
cout<<str;
return 0;
}
|
结果：wroolllhde空格
字符串间的比较排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<iostream>
#include<cstring >
#include<algorithm>
using namespace std;
int main()
{
string a[4];
for(int i=0;i<4;i++)
getline(cin,a[i]);
sort(a,a+4);
for(int i=0;i<4;i++)
cout<<a[i]<<endl;
return 0;
}
|
以结构体为例的二级排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct link
{
int a,b;
};
bool cmp(link x,link y)
{
if(x.a==y.a)
return x.b>y.b;
return x.a>y.a;
}
int main()
{
link x[4];
for(int i=0;i<4;i++)
cin>>x[i].a>>x[i].b;
sort(x,x+4,cmp);
for(int i=0;i<4;i++)
cout<<x[i].a<<' '<<x[i].b<<endl;
return 0;
}
|
qsort()与sort()
与sort相比,qsort是使用快速排序的算法,更底层一些,需要自己编写cmp函数(默认是升序排序).可以认为sort是改进版的qsort
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <stdlib.h>
#include <algorithm>
#define SIZE 100
int gArray[SIZE] = {……};
int cmp(const void * a, const void *b)
{
return (*(int *)a - *(int *)b);
}
qsort(gArray, SIZE, sizeof(gArray[0]), cmp);
|
C++自带的排序函数sort只能获得排好序的值，没办法像Matlab一样同时返回排序索引。下面使用c++11中的 lambda来为sort函数添加一个模式：
1
2
3
4
5
6
7
8
9
10
11
12
13
| template <typename T>
vector<size_t> sort_indexes(const vector<T> &v)
{
vector<size_t> idx(v.size());
iota(idx.begin(), idx.end(), 0);
sort( idx.begin(),
idx.end(),
[&v](size_t i1, size_t i2) {return v[i1] < v[i2];} );
return idx;
}
|
上面的是升序排列，如果想要降序排列，只需要更改为：
1
| [&v](size_t i1, size_t i2) {return v[i1] > v[i2];}
|
