C++之STL的algorithm（6）之排序算法（sort、merge）整理

C++之STL的algorithm（6）之排序算法（sort、merge）整理

注：整理一些突然学到的C++知识，随时mark一下
例如：忘记的关键字用法，新关键字，新数据结构

提示：本文为 C++ 中sort、reverse、merge 的写法和举例

一、排序算法

1、sort算法

std::sort 是对一个容器的给定范围内进行排序的算法。

语法：

template<class RandomIt>  
void sort(RandomIt first, RandomIt last);

参数：

first, last：要排序的序列的迭代器范围。

返回：

无返回值，直接修改输入的序列。

对vector 排序示例：

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::vector<int> v = {5, 2, 4, 1, 3};  
    std::sort(v.begin(), v.end());  
  
    for (int i : v) {  
        std::cout << i << ' ';  
    }  
    // 输出: 1 2 3 4 5  
    return 0;  
}

对于map/set ：
由于 std::map 和 std::set 内部的元素已经是排序的，所以通常不需要调用 std::sort。但如果你想要基于某个不同的标准来排序它们的元素，你需要复制元素到一个新的容器中（比如 std::vector），然后使用 std::sort。

2、random_shuffle 随机洗牌算法

std::random_shuffle 用于打乱给定序列中元素的顺序。

语法：

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

参数：
first, last：要打乱顺序的序列的迭代器范围。

返回：

无返回值，直接修改输入的序列。

vector 示例：

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <ctime>  
  
int main() {  
    std::vector<int> v = {1, 2, 3, 4, 5};  
    std::srand(std::time(0)); // 设置随机种子  
    std::random_shuffle(v.begin(), v.end());  
  
    for (int i : v) {  
        std::cout << i << ' ';  
    }  
    // 输出: 随机排列的1到5  
    return 0;  
}

注意：std::random_shuffle 在 C++17 中被弃用，推荐使用 <random> 库中的函数来生成随机数，从而进行洗牌。

3、reverse 反转算法

std::reverse 用于反转给定序列中元素的顺序。

语法：

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

参数：

first, last：要反转的序列的双向迭代器范围。

返回：

无返回值，直接修改输入的序列。

vector 示例：

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::vector<int> v = {1, 2, 3, 4, 5};  
    std::reverse(v.begin(), v.end());  
  
    for (int i : v) {  
        std::cout << i << ' ';  
    }  
    // 输出: 5 4 3 2 1  
    return 0;  
}

对map/set 示例：
std::map 和 std::set 是基于红黑树的关联容器，因此它们的元素始终是按键排序的。你不能直接反转 map 或 set 的元素顺序，因为它们不允许随机访问迭代器。但是可以复制它们的元素到一个可以反转的容器（比如 std::vector），然后反转那个容器。

这里是一个反转 map 中元素顺序的示例：

#include <iostream>  
#include <map>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};  
    std::vector<std::pair<int, std::string>> v(m.begin(), m.end());  
  
    std::reverse(v.begin(), v.end());  
  
    for (const auto& pair : v) {  
        std::cout << pair.second << ": " << pair.first << '\n';  
    }  
    // 输出: three: 3  
    //        two: 2  
    //        one: 1  
    return 0;  
}

在这个例子中，我们首先创建了一个 std::map，然后将它的元素复制到一个 std::vector 中。之后，我们使用 std::reverse 来反转 vector 中的元素顺序，并打印出反转后的结果。

4、 merge 合并算法

std::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：目标序列的起始迭代器。

返回：

返回指向目标序列中最后一个元素的下一个位置的迭代器。

vector 示例：

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::vector<int> v1 = {1, 3, 5};  
    std::vector<int> v2 = {2, 4, 6};  
    std::vector<int> v3(v1.size() + v2.size());  
  
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());  
  
    for (int i : v3) {  
        std::cout << i << ' ';  
    }  
    // 输出: 1 2 3 4 5 6  
    return 0;  
}

注意：std::merge 也不适用于 std::map 和 std::set，因为它们已经是排序好的容器，并且它们的元素不能直接合并到另一个 map 或 set 中。

总结：

std::sort 用于对序列进行排序。
std::random_shuffle（已弃用）用于打乱序列中元素的顺序。
std::reverse 则用于反转序列中元素的顺序。
std::merge 适用于合并两个已排序的序列。

对于 map 和 set 这样的关联容器，由于它们的元素是按键排序的，通常不直接在这些容器上进行排序或反转操作，而是将它们的元素复制到可以能够执行这些操作的vector容器中。