排序
稳定排序
排序后相对位置不发生变化
- 归并
不稳定
- 快排
- 堆排序
排序函数
加上头文件#include <algorithm>和using namespace std;
在c++里，sort是不稳定的，stable_sort是稳定的（内部是归并）
使用方式
sort(首元素地址(必填),尾元素地址的下一个地址(必填),比较函数(非必填));
注意
尾元素地址的下一个地址
如果不写比较函数,则默认对前面给出的区间进行递增排序
如果需要对序列进行排序,那么序列中的元素一定要有可比性,因此需要制订排序规则来建立这种可比性。特别是像结构体,本身并没有大小关系,需要人为制订比较的规则。sort 的第三个可选参数就是compare 函数(一般写作cmp 函数),用来实现这个规则。
如何实现cmp函数
(1)基本数据类型数组的排序
默认情况下是升序排序的
#include "iostream"
#include "algorithm"
using namespace std;
int main() {
int arr[] = {3, 1, 4, 2};
sort(arr, arr + 4);
for (int i = 0; i < 4; ++i) {
cout << arr[i] << " ";
}
return 0;
};
1 2 3 4
#include "iostream"
#include "algorithm"
using namespace std;
bool cmp(int a, int b) {
return a > b;
}
int main() {
int arr[] = {3, 1, 4, 2};
sort(arr, arr + 4, cmp);
for (int i = 0; i < 4; ++i) {
cout << arr[i] << " ";
}
return 0;
};
4 3 2 1
提示
本题中cmp函数可以理解为如果 a > b 那么 a 就排在 b 前面，最终排序结果就是降序了
(2)结构体数组的排序
定义cmp函数
结构体中x属性大的排在前面
#include "iostream"
#include "algorithm"
using namespace std;
struct node {
int x, y;
} ssd[4];
bool cmp(node a, node b) {
return a.x > b.x;
}
int main() {
ssd[0].x = 1;
ssd[0].y = 2;
ssd[1].x = 4;
ssd[1].y = 3;
ssd[2].x = 2;
ssd[2].y = 4;
ssd[3].x = 9;
ssd[3].y = 0;
for (int i = 0; i < 4; ++i) {
cout << "x = " << ssd[i].x << ", " << "y = " << ssd[i].y << endl;
}
cout << "-------" << endl;
sort(ssd, ssd + 4, cmp);
for (int i = 0; i < 4; ++i) {
cout << "x = " << ssd[i].x << ", " << "y = " << ssd[i].y << endl;
}
return 0;
};
x = 1, y = 2
x = 4, y = 3
x = 2, y = 4
x = 9, y = 0
-------
x = 9, y = 0
x = 4, y = 3
x = 2, y = 4
x = 1, y = 2
重载运算符
bool operator<(const node &t) const {
return x < t.x;
}
相关信息
这是一个C++中的运算符重载函数，它重载了小于号运算符
<。它的作用是比较两个node类型的对象的x成员变量的大小，并返回一个布尔值。这个函数的参数是一个
node类型的常量引用t，表示要比较的另一个对象。这个函数的返回值是一个布尔值，表示当前对象的
x成员变量是否小于另一个对象的x成员变量。如果是，则返回true，否则返回false。这个函数通常用于排序算法中，例如使用
std::sort()函数对一个node类型的数组进行排序。在排序过程中，std::sort()函数会多次调用这个函数来比较数组中的元素，以确定它们的相对顺序。
const关键字
在C++中，函数结尾的const关键字表示该函数是一个常量成员函数。这意味着该函数不会修改对象的状态，即它不会修改对象的成员变量。这个关键字可以用于类的成员函数中，例如：
class MyClass {
public:
int getValue() const {
return value;
}
private:
int value;
};
在这个例子中，getValue()函数是一个常量成员函数，它返回对象的value成员变量的值。由于这个函数不会修改对象的状态，因此它被声明为常量成员函数，并在函数结尾处加上了const关键字。
常量成员函数可以被常量对象调用，例如：
const MyClass obj;
int val = obj.getValue(); // 可以调用常量成员函数
但是，常量成员函数不能修改对象的状态，例如：
const MyClass obj;
obj.value = 10; // 错误：常量对象不能修改成员变量
因此，常量成员函数可以提高代码的安全性和可读性，因为它们不会意外地修改对象的状态。
functional提供了一堆基于模板的比较函数对象,对于这个问题来说，greater和less就足够了，直接拿过来用：
升序：sort(begin,end,less<data-type>());
降序：sort(begin,end,greater<data-type>()。
这里less对应的是结构体中重载的<运算符，greater对应重载的>运算符
#include "iostream"
#include "algorithm"
using namespace std;
struct node {
int x, y;
bool operator<(const node &t) const {
return x < t.x;
}
bool operator>(const node &t) const {
return x > t.x;
}
} ssd[4];
int main() {
ssd[0].x = 1;
ssd[0].y = 2;
ssd[1].x = 4;
ssd[1].y = 3;
ssd[2].x = 2;
ssd[2].y = 4;
ssd[3].x = 9;
ssd[3].y = 0;
for (int i = 0; i < 4; ++i) {
cout << "x = " << ssd[i].x << ", " << "y = " << ssd[i].y << endl;
}
cout << "-------" << endl;
sort(ssd, ssd + 4, less<node>());
for (int i = 0; i < 4; ++i) {
cout << "x = " << ssd[i].x << ", " << "y = " << ssd[i].y << endl;
}
sort(ssd, ssd + 4, greater<node>());
cout << "-------" << endl;
for (int i = 0; i < 4; ++i) {
cout << "x = " << ssd[i].x << ", " << "y = " << ssd[i].y << endl;
}
return 0;
};
x = 1, y = 2
x = 4, y = 3
x = 2, y = 4
x = 9, y = 0
-------
x = 1, y = 2
x = 2, y = 4
x = 4, y = 3
x = 9, y = 0
-------
x = 9, y = 0
x = 4, y = 3
x = 2, y = 4
x = 1, y = 2