c++list.sort复杂度

### C++ 中 `list` 容器的 `sort` 方法

在 C++ STL 中，`list` 是一种双向链表容器。对于 `list::sort()` 函数而言，其实现方式不同于其他序列式容器（如 `vector` 或者数组）。由于 `list` 的内部实现特性，即节点之间的链接关系而非连续存储空间，因此其排序算法也有所区别。

#### 排序机制与时间复杂度分析

`list::sort()` 使用了一种基于归并排序的思想来完成排序工作[^2]。具体来说：

- **稳定性**：该函数保持稳定，意味着相等元素间的相对顺序不会改变。
- **时间复杂度**：理论上讲，`list::sort()` 的平均情况下的时间复杂度为 O(n log n)，其中 n 表示列表中元素的数量。这是因为每次分割操作大约花费线性时间遍历整个子列表，并且这样的划分过程重复约 log₂n 次直到达到单个元素为止；之后再逐步合并这些有序片段形成最终的结果集。

需要注意的是，在某些特殊情况下——比如当输入数据已经部分有序时——性能可能会优于理论上的最坏情形。然而，这并不影响上述给出的一般化结论。

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {5, 3, 7, 1, 9};
    
    // 对 list 进行排序前打印
    for (auto it : lst) 
        std::cout << it << " ";
    std::cout << "\n";

    lst.sort(); // 默认升序排列
    
    // 排序后再次打印
    for (auto it : lst) 
        std::cout << it << " ";

    return 0;
}

这段代码展示了如何创建一个整数类型的 `std::list` 并对其进行简单排序。通过调用成员函数 `lst.sort()` 实现默认从小到大排序功能。