sort详解

sort类函数

  • sort()函数是c++中的一种排序方法，实现的方法类似于快速排序的方法，时间复杂度为 n*log2(n)。
  • sort 类函数总结
函数名 功能描述
sort 对给定区间进行排序
stable_sort 对给定所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断区间是否有序
partition 将符合某个条件的元素放在前面
stable_partition 相对稳定的将符合某个条件的元素放在前面

sort()

  • 头文件：#include

  • 语法：sort(begin,end,cmp)

    begin: 待排序数组内存的起始地址

    end: 待排序数组结束地址的下一位

    cmp: 此参数可以不写，此时默认非降序排序（简单一点升序）

int 型排序

示例一：没有cmp参数

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
#include <algorithm>
using namespace std;
int main() {
	int arr[5] = {3,1,5,2,6};
	sort(arr, arr + 5);
	for (int i = 0;i < 5;i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

运行结果：

1
1 2 3 5 6

示例二：利用cmp 参数实现降序排序，当cmp函数返回值为true时，表示cmp 函数的参数将会按照自定义的规则排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include <algorithm>
using namespace std;
bool cmp(int x, int y) {
	return x > y;//第一个参数比第二个参数大，则排在前面
}
int main() {
	int arr[5] = {3,1,5,2,6};
	sort(arr, arr + 5, cmp);//使用重载函数形式，表明将要使用自定义的排序规则
	for (int i = 0;i < 5;i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

运行结果：

1
6 5 3 2 1

示例三：利用 functional 提供的一堆基于模板的比较函数对象:equal_to<类型>、not_equal_to<类型>、

greater<类型>、greater_equal<类型>、less<类型>、less_equal<类型>。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	int arr[5] = {3,1,5,2,6};
	sort(arr, arr + 5, greater<int>());
	for (int i = 0;i < 5;i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	sort(arr, arr + 5, less<int>());
	for (int i = 0;i < 5;i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

运行结果：

1
2
6 5 3 2 1
1 2 3 5 6

string 类排序

  • 一个字符串间字符的排序
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	string str = "hello";
	sort(str.begin(), str.end());//顺序排序
	cout << str << endl;
	sort(str.rbegin(), str.rend());//逆序排序 
	cout << str << endl;
	cout << endl;
	return 0;
}

运行结果：

1
2
ehllo
ollhe
  • 字符串间的排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <string>
#include<iostream> 
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	string str[4];
	for (int i = 0;i < 4;i++) {
		getline(cin,str[i]);
	}
	sort(str, str+4,less<string>());
	for (int i = 0;i < 4;i++) {
		cout << str[i] << endl;
	}
	return 0;
}
  • 结构体类型的排序：先按照a降序，如果a相同在按照b降序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream> 
#include <algorithm>
struct test {
	int a, b;
};
bool cmp(test& t1, test& t2) {
	if (t1.a != t2.a)
		return t1.a > t2.a;
	return t1.b > t2.b;
}
using namespace std;
int main() {
	test t[4];
	for (int i = 0;i < 4;i++) {
		cin >> t[i].a >> t[i].b;
	}
	sort(t, t + 4, cmp);
	for (int i = 0;i < 4;i++) {
		cout << t[i].a << " " << t[i].b << endl;
	}
	return 0;
}