【C++STL】快速排序算法(sort)的原理与使用-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++STL】快速排序算法(sort)的原理与使用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、sort算法原理

std::sort 是 C++ 标准库中提供的排序算法，它使用的是一种经典的排序算法——快速排序（Quicksort）或者是其变种。

快速排序是一种基于比较的排序算法，通过不断地选择一个基准值（pivot），将待排序序列分割为两个子序列，其中一个子序列的所有元素小于等于基准值，另一个子序列的所有元素大于基准值。然后递归地对两个子序列进行排序，最终得到有序序列。

std::sort 在实现快速排序时，通常会结合其他优化技巧，如插入排序或堆排序，以提高算法的性能和效率。

快速排序的基本步骤：

选择一个基准值（pivot）。可以选择序列的第一个元素、最后一个元素、中间元素或者随机选择一个元素作为基准值。
将序列分割为两个子序列，使得一个子序列的所有元素小于等于基准值，另一个子序列的所有元素大于基准值。
递归地对两个子序列进行排序，即对小于等于基准值的子序列和大于基准值的子序列进行排序。
合并两个排序好的子序列，得到最终的有序序列。

快速排序是一种原地排序算法，它的平均时间复杂度为 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 是一个高效、通用且灵活的排序算法。它在大多数情况下都能提供良好的性能，并且可以应用于不同类型的容器和自定义类型。然而，对于一些特殊需求，例如需要稳定排序或对大型容器进行排序，可能需要选择其他排序算法或使用自定义的排序实现。