C++ 排序算法-Toy模板网

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

🤔排序算法：

📖1.sort 对容器内元素进行排序

📖2.random_shuffle 洗牌指定范围内的元素随机调整次序

📖3.merge 容器元素合并，并整合到另一个容器中

📖4.reverse 反转指定容器元素

🤔逐一介绍：

🙂1.sort 排序

📖在C++语言中，sort（排序）函数是STL（标准库）中的一个函数，它用于将一个数组或vector等STL容器中的元素进行排序。sort函数可以将元素以升序或降序的方式排序。sort函数的使用需要包含头文件<algorithm>。

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

📖sort函数可以接受三个参数，第一个参数是排序的数组或STL容器的首地址，第二个参数是指定排序数据的大小，通常可以使用sizeof运算符来计算，第三个参数是一个函数指针，用于指定排序的规则，默认情况下，sort函数按照升序进行排序，而我们可以通过在第三个函数位引入不同的规则函数来确定排序条件。

📖第三个参数可以用我们之前介绍的关系仿函数代替，下面这个链接中介绍了仿函数

C++ 函数对象详解_我是一盘牛肉的博客-CSDN博客

🔍代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(vector<int>d)
{
	for (auto a = d.begin(); a != d.end(); a++)
	{
		cout << *a<<"  ";
	}
	cout << endl;
}
int main()
{
	vector<int>d1;
	d1.push_back(20);
	d1.push_back(23);
	d1.push_back(10);
	d1.push_back(22);
	d1.push_back(34);
	d1.push_back(28);
	cout << "反转前";
	print(d1);
	cout << "反转后";
	sort(d1.begin(), d1.end(), less<int>());
	print(d1);

	
}

🔍运行结果：

🙂 2.random_shuffle 随机排序

📖在C++中，random_shuffle 是STL提供的一个函数，用于对一个序列或容器中的元素进行乱序排列，即将其中的元素随机打乱。它头文件为<algorithm>。

📖random_shuffle 函数不需要我们自己编写乱序算法，只需要将待打乱的序列或容器的首地址和尾地址传入函数即可。它的函数原型如下：

template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

📖其中，first和last分别为待打乱的序列（或容器）的首尾元素的迭代器。

📖需要注意的是它也是伪随机，需要利用时间戳改变随机规则。

include<ctime>
strand((unsigned int)time(NULL));

关于时间戳的介绍，我们放在了这篇文章里：

C语言 rand函数_我是一盘牛肉的博客-CSDN博客

我们这里利用随机排序的特点实现一个比较好玩的排序：猴子排序

猴子排序（也常被称为猴子补丁或瞎子排序）是一种思路简单但并不实用的乱序算法。它没有太大的用处，仅仅作为一种娱乐性质的算法而被提及。

猴子排序的思路是，根据“猴子定理”来猜测正确的排序位置。该定理指出，如果无限次地随机打乱一个序列，那么该序列最终也会被排成有序列。

具体来说，猴子排序的流程如下 :

1. 随机打乱待排序的序列。
2. 判断序列是否已经排好序，如果是，算法结束；否则，继续第3步。
3. 再次随机打乱序列并回到第2步。

需要注意的是，猴子排序的时间复杂度是非常高的，尤其是在待排序的序列长度较长的情况下，它的时间复杂度接近于无穷大，因此在实际应用中不宜使用。

🔍代码运行：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void print(vector<int> d)
{
    for (auto a = d.begin(); a != d.end(); a++)
    {
        cout << *a << "  ";
    }
    cout << endl;
}

bool operator==(vector<int> d1, vector<int> d2)
{
    auto a1 = d1.begin();
    auto a2 = d2.begin();
    int count = 0;
    int size = d1.size();
    while (a1 != d1.end())
    {
        if (*a1 != *a2)
        {
            return false;
        }
        a1++;
        a2++;
        count++;
    }
    return count == size;
}

int main()
{
    vector<int> d1;
    d1.push_back(20);
    d1.push_back(23);
    d1.push_back(10);
    d1.push_back(22);
    d1.push_back(34);
    d1.push_back(28);
    vector<int> d2;
    d2 = d1;
    sort(d2.begin(), d2.end());
    for (int i = 0; i < 1000; i++)
    {
        random_shuffle(d1.begin(), d1.end());
        print(d1);

        if (d1 == d2)
        {
            print(d1);
            return 0;
        }
    }
    return 0;
}

🔍运行结果：

C++ 排序算法

我们通过不断的随机排序最终找到了符合要求的排序。

🙂3.merge 合并排序

📖在 C++ 的 STL 库中，merge 是一个用于让两个已经排好序的数组合并成一个有序数组的算法，它支持常规数组和 STL 容器。

📖merge 的函数原型为：

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first);

📖其中，参数 first1 和 last1 是第一个已排序区间的首迭代器和尾部后继迭代器，first2 和 last2 是第二个已排序区间的首迭代器和尾部后继迭代器，d_first 是新的有序序列起始位置的迭代器。

📖merge() 函数从两个已排序序列中取出较小的值并放入目标序列中，直到其中一个序列已经没有元素为止。如果两个序列中有相等的元素，则将第一个序列的元素放在前面。最后，merge() 返回值为新序列的最后一个后置迭代器。

🔍代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void ptint(int val)
{
	cout << val<<" ";
}
int main()
{
	vector<int>d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	vector<int>d2;
	for (int i = 0; i < 10; i++)
	{
		d2.push_back(i);
	}
	cout << "合并前" << endl;
	cout << "d1   ";
	for_each(d1.begin(), d1.end(), ptint);
	cout << endl;
	cout << "d2   ";
	for_each(d2.begin(), d2.end(), ptint);
	vector<int>d3;
	//创建自定义变量并不会自动分配内存，需要我们自己主动分配
	d3.resize(20);
	cout << endl;
	cout << "合并到d3后";
	merge(d1.begin(), d1.end(), d2.begin(), d2.end(), d3.begin());
	for_each(d3.begin(), d3.end(), ptint);
}

🔍运行结果：

C++ 排序算法

🙂 4.reverse 反转排序

📖在 C++ STL 中，reverse()是一种简单且常用的算法，用于将数组或容器中所有元素顺序颠倒，即实现序列的翻转。

📖reverse()的函数原型为：

template<class BidirIt>
void reverse(BidirIt first, BidirIt last);

📖 其中，first 和 last 分别表示需要翻转的区间的首迭代器和尾部后继迭代器。

reverse进行的是原地反转，不需要占用多余的空间。

🔍代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void ptint(int val)
{
	cout << val<<" ";
}
int main()
{
	vector<int>d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	vector<int>d2;
	for (int i = 0; i < 10; i++)
	{
		d2.push_back(i);
	}
	cout << "合并前" << endl;
	cout << "d1   ";
	for_each(d1.begin(), d1.end(), ptint);
	cout << endl;
	cout << "d2   ";
	for_each(d2.begin(), d2.end(), ptint);
	vector<int>d3;
	//创建自定义变量并不会自动分配内存，需要我们自己主动分配
	d3.resize(20);
	cout << endl;
	cout << "合并到d3后";
	merge(d1.begin(), d1.end(), d2.begin(), d2.end(), d3.begin());
	for_each(d3.begin(), d3.end(), ptint);
}