一、sort算法原理
std::sort 是 C++ 标准库中提供的排序算法，它使用的是一种经典的排序算法——快速排序（Quicksort）或者是其变种。
快速排序是一种基于比较的排序算法，通过不断地选择一个基准值（pivot），将待排序序列分割为两个子序列，其中一个子序列的所有元素小于等于基准值，另一个子序列的所有元素大于基准值。然后递归地对两个子序列进行排序，最终得到有序序列。
std::sort 在实现快速排序时，通常会结合其他优化技巧，如插入排序或堆排序，以提高算法的性能和效率。
快速排序的基本步骤：
快速排序是一种原地排序算法，它的平均时间复杂度为 O(nlogn)，其中 n 是待排序序列的大小。在最坏情况下，快速排序的时间复杂度为 O(n^2)，但通过合理选择基准值可以减少最坏情况的发生概率。
std::sort 的实现会考虑到不同情况下的性能和效率，并且在不同的编译器和库实现中可能有所不同。它通常会根据序列的大小、数据类型以及其他因素来选择合适的排序算法，以获得更好的性能。对于小型序列，std::sort 可能会使用插入排序或者其他简单的排序算法，而对于大型序列，它通常会采用快速排序或者其变种。此外，std::sort 还可以接受自定义的比较函数或谓词，以满足不同的排序需求。
二、sort算法使用
功能： 对容器内元素进行排列（默认升序排列）
sort()属于质变算法| 函数原型： | sort(iterator beg, iterator end, pred) | 解释 |
|---|---|---|
| 参数1 | iterator beg | 开始迭代器 |
| 参数2 | iterator end | 结束迭代器 |
| 参数3 | pred | 谓词 |
详细信息：
当调用 std::sort 进行排序时，它采用的是一种分治策略的快速排序算法，这意味着它将待排序的元素分割成较小的子集，然后对这些子集进行排序并逐步合并，最终得到完全排序的结果。
std::sort 排序的是一个范围，由两个迭代器 first 和 last 指定，表示排序的起始位置和结束位置。排序将应用于 [first, last) 区间内的元素。std::sort 使用 < 运算符进行比较来确定元素的顺序。如果要按照其他准则进行排序，可以提供自定义的比较函数或函数对象作为可选的第三个参数。这个比较函数或函数对象应接受两个参数，并返回一个布尔值，指示第一个参数是否在排序中应排在第二个参数之前。std::sort 使用快速排序算法，其平均时间复杂度为 O(n log n)，其中 n 是要排序的元素的数量。在最坏情况下，快速排序的时间复杂度为 O(n^2)，但这种情况很少发生。std::sort 可以用于标准容器（如 std::vector、std::deque、std::list 等）以及普通的数组。排序会就地进行，即直接修改容器中的元素顺序，而不会创建新的容器。std::sort 不仅可以对基本类型（如整数、浮点数）进行排序，还可以对自定义类型进行排序，只要自定义类型支持比较操作符 < 或提供自定义的比较函数。std::sort 不会使迭代器失效，这意味着在排序后仍然可以使用原始容器的迭代器。std::sort 不保证排序的稳定性，即相等元素的顺序可能在排序后发生改变。如果需要保持相等元素的顺序不变，可以使用 std::stable_sort 算法。示例1： 默认情况下为升序排列
#include <iostream>
#include <algorithm> //必须包含该头文件
#include <vector>
using namespace std;
//函数对象(仿函数)
class print
{
public:
void operator()(int value)
{
cout << value << " ";
}
};
void test01()
{
vector<int> vec = {6, 9, 3, 4, 2, 7, 1, 5, 8};
//排序前
cout << "排序前：";
for_each(vec.begin(), vec.end(), print());
cout << endl;
//排序后-升序
cout << "排序后：";
sort(vec.begin(), vec.end()); //默认升序
for_each(vec.begin(), vec.end(), print());
cout << endl;
}
int main()
{
test01();
system("pause");
return 0;
}
//result
排序前：6 9 3 4 2 7 1 5 8
排序后：1 2 3 4 5 6 7 8 9
示例2： 使用谓词std::greater<>
greater<> 是一个模板类，它是一个二元谓词（binary predicate），用于比较两个值的大小关系。#include <iostream>
#include <algorithm> //必须包含该头文件
#include <vector>
using namespace std;
//函数对象(仿函数)
class print
{
public:
void operator()(int value)
{
cout << value << " ";
}
};
void test01()
{
vector<int> vec = {6, 9, 3, 4, 2, 7, 1, 5, 8};
//排序前
cout << "排序前：";
for_each(vec.begin(), vec.end(), print());
cout << endl;
//排序后-降序-添加谓词greater
cout << "排序后：";
sort(vec.begin(), vec.end(), greater<int>());
for_each(vec.begin(), vec.end(), print());
cout << endl;
}
int main()
{
test01();
system("pause");
return 0;
}
//result
排序前：6 9 3 4 2 7 1 5 8
排序后：9 8 7 6 5 4 3 2 1
示例3： 自定义类型排序
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class goods
{
public:
goods(string name, int price)
{
m_name = name;
m_price = price;
}
public:
string m_name;
int m_price;
};
// 自定义排序-根据商品价格升序
struct arrange
{
bool operator()(const goods& value1, const goods& value2)
{
return value1.m_price < value2.m_price;
}
};
class print
{
public:
void operator()(const goods& value)
{
cout << "名称：" << value.m_name << "\t价格：" << value.m_price << endl;
}
};
void test01()
{
goods goods1("可乐", 3);
goods goods2("红牛", 5);
goods goods3("脉动", 4);
goods goods4("外星人", 6);
goods goods5("雪碧", 3);
goods goods6("哇哈哈", 2);
vector<goods> vec;
vec.push_back(goods1);
vec.push_back(goods2);
vec.push_back(goods3);
vec.push_back(goods4);
vec.push_back(goods5);
vec.push_back(goods6);
// 排序前
cout << "排序前：" << endl;
for_each(vec.begin(), vec.end(), print());
cout << endl;
// 排序后-升序-添加谓词arrange
cout << "排序后：" << endl;
sort(vec.begin(), vec.end(), arrange());
for_each(vec.begin(), vec.end(), print());
cout << endl;
}
int main()
{
test01();
system("pause");
return 0;
}
//result
排序前：
名称：可乐 价格：3
名称：红牛 价格：5
名称：脉动 价格：4
名称：外星人 价格：6
名称：雪碧 价格：3
名称：哇哈哈 价格：2
排序后：
名称：哇哈哈 价格：2
名称：可乐 价格：3
名称：雪碧 价格：3
名称：脉动 价格：4
名称：红牛 价格：5
名称：外星人 价格：6
总结：std::sort 是一个高效、通用且灵活的排序算法。它在大多数情况下都能提供良好的性能，并且可以应用于不同类型的容器和自定义类型。然而，对于一些特殊需求，例如需要稳定排序或对大型容器进行排序，可能需要选择其他排序算法或使用自定义的排序实现。
