揭秘List排序：从入门到精通，高效算法大揭秘

概述
在C++中，
list
容器是一种双向链表，它提供了高效的元素插入和删除操作。然而，
list
容器不支持随机访问，这意味着我们无法直接通过索引来访问或修改元素。尽管如此，
list
容器内置了排序功能，这使得我们可以在不牺牲链表特性的情况下对数据进行排序。
本文将深入探讨
list
的排序机制，从基本概念到高级技巧，帮助读者从入门到精通。
基础概念
1.1 List的构造和插入删除
list
的构造与
vector
类似，可以直接使用
std::list
来创建一个
list
对象。插入和删除操作可以通过迭代器来完成。
#include #include

int main() {
std::list lst;
lst.push_back(3);
lst.push_back(1);
lst.push_back(4);
lst.push_back(1);

for (auto it = lst.begin(); it != lst.end(); ++it) {
std::cout << *it << " "; } std::cout << std::endl; lst.remove(1); // 删除值为1的元素 lst.push_front(2); // 在前面插入元素2 for (auto it = lst.begin(); it != lst.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; return 0; } 1.2 迭代器的分类 list 提供了不同类型的迭代器，包括正向迭代器、反向迭代器和常量迭代器。 正向迭代器 ：可以向前或向后遍历容器。 反向迭代器 ：只能向后遍历容器。 常量迭代器 ：不能修改容器中的元素。 排序算法 2.1 内置排序 list 容器提供了内置的排序功能，可以直接使用。 #include

int main() {
std::list lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

lst.sort(); // 升序排序

for (auto it = lst.begin(); it != lst.end(); ++it) {
std::cout << *it << " "; } std::cout << std::endl; return 0; } 2.2 自定义排序规则 如果需要自定义排序规则，可以使用 std::sort 函数，并传递自定义的比较函数。 #include
#include

int main() {
std::list lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

lst.sort([](int a, int b) { return a < b; }); // 升序排序 for (auto it = lst.begin(); it != lst.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; return 0; } 高级技巧 3.1 链表的合并 可以使用迭代器来合并两个 list 。 #include

int main() {
std::list lst1 = {1, 2, 3};
std::list lst2 = {4, 5, 6};

lst1.merge(lst2); // 合并lst2到lst1

for (auto it = lst1.begin(); it != lst1.end(); ++it) {
std::cout << *it << " "; } std::cout << std::endl; return 0; } 3.2 链表去重 可以通过迭代器遍历 list 并使用 erase 来删除重复的元素。 #include

int main() {
std::list lst = {1, 2, 2, 3, 4, 4, 4, 5};

lst.sort(); // 先排序

auto it = lst.begin();
while (next(it) != lst.end()) {
if (*it == *(next(it))) {
it = lst.erase(it); // 删除重复的元素
} else {
++it;
}
}

for (auto it = lst.begin(); it != lst.end(); ++it) {
std::cout << *it << " "; } std::cout << std::endl; return 0; } 3.3 链表的剪切 剪切操作可以将一个 list 的一部分剪切到另一个 list 中。 #include

int main() {
std::list lst1 = {1, 2, 3, 4, 5};
std::list lst2;

lst2.splice(lst2.end(), lst1, lst1.begin(), lst1.end()); // 将lst1的全部元素剪切到lst2的末尾

for (auto it = lst1.begin(); it != lst1.end(); ++it) {
std::cout << *it << " "; } std::cout << std::endl; for (auto it = lst2.begin(); it != lst2.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; return 0; } 总结 本文深入探讨了 list 的排序机制，从基本概念到高级技巧，旨在帮助读者全面理解和使用 list 容器。通过本文的讲解，读者应该能够轻松地在程序中使用 list 进行高效的排序和操作。