std::list::sort()最省事且稳定高效，但自定义类型排序时比较函数必须接受const引用参数并返回bool；手写双向链表宜用归并排序而非快排，注意指针安全与迭代器失效规则。
用 std::list 自带的 sort() 最省事，但得注意比较函数签名
如果你只是需要一个可排序的双向链表，std::list 就是标准答案——它底层就是双向链表，且 sort() 是稳定排序、时间复杂度 O(n log n)，不依赖随机访问。但容易踩的坑是：自定义类型排序时，传入的比较函数必须接受两个 const 引用参数，返回 bool。
比如对 std::list<int></int> 排序，直接调用即可：
std::list<int> lst = {3, 1, 4, 1, 5};
lst.sort(); // 升序
</int>
对自定义结构体，要写对签名：
struct Node { int val; std::string name; };
std::list<node> lst = {{3,"a"}, {1,"b"}, {2,"c"}};
lst.sort([](const Node& a, const Node& b) { return a.val
<ul>
<li>错写成 <code>(Node a, Node b)</code>（值传递）会编译失败或效率低下</li>
<li>返回非 <code>bool</code>（如 <code>int</code>）会导致未定义行为</li>
<li>
<code>std::list::sort()</code> 不接受仿函数对象以外的任何迭代器范围，不能像 <code>std::sort</code> 那样传 begin/end</li>
</ul>
<h3>手写双向链表排序时，别硬刚快排，归并更合适</h3>
<p>手写双向链表（含 <code>prev</code>/<code>next</code> 指针）时，常见误区是照搬数组快排逻辑——找 pivot、交换节点、维护边界。但链表没有 O(1) 下标访问，swap 操作成本高，且分区过程极易断链。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>真正适合链表的排序是自底向上的归并排序：利用链表天然的“拆分-合并”能力，无需额外空间（除递归栈），稳定，且避免深递归导致的栈溢出。</p>
<ul>
<li>核心操作是 <code>split()</code>（找中点并断开）和 <code>merge()</code>（合并两个有序链表）</li>
<li>找中点推荐快慢指针法，比计数再遍历更安全（避免长度误判）</li>
<li>归并时务必统一使用带头结点（dummy node）写法，大幅降低空指针判断复杂度</li>
<li>递归实现要注意尾递归优化不可用，数据量大时建议改用迭代版归并</li>
</ul>
<h3>
<code>std::list::sort()</code> 和手写归并性能差异不大，但兼容性差很多</h3>
<p>实测在万级元素下，<code>std::list::sort()</code> 和手写迭代归并耗时相差通常在 10% 以内。真正差距在工程层面：</p>
<ul>
<li>
<code>std::list::sort()</code> 依赖编译器实现（GCC 用迭代归并，MSVC 也是），行为一致、无内存泄漏风险</li>
<li>手写链表若没做移动语义支持（<code>Node(Node&&)</code>），<code>std::move</code> 失效，字符串等成员会反复拷贝</li>
<li>手写版本很难自然支持 allocator（如内存池），而 <code>std::list</code> 可直接传入</li>
<li>调试时，<code>std::list</code> 的迭代器失效规则明确；手写链表一旦 <code>prev</code>/<code>next</code> 错位，<code>gdb</code> 里几乎无法追踪</li>
</ul>
<h3>排序后遍历出错？大概率是忘了 <code>std::list</code> 迭代器不支持 <code>+</code> 运算</h3>
<p>排序完想取第 k 个元素，写 <code>std::next(lst.begin(), k)</code> 是对的，但有人会误写成 <code>lst.begin() + k</code>——这会编译失败，因为 <code>std::list::iterator</code> 是 BidirectionalIterator，不支持随机访问运算符。</p>
<ul>
<li>正确方式只有 <code>std::advance(it, k)</code> 或循环 <code>k</code> 次 <code>++it</code>
</li>
<li>如果频繁按索引访问，说明数据结构选错了——该用 <code>std::vector</code> 而不是链表</li>
<li>排序后插入新元素不会影响已有迭代器有效性（这是 <code>std::list</code> 的优势），但删除节点会使对应迭代器立即失效</li>
</ul>
<p>链表排序真正的复杂点不在算法本身，而在指针操作的边界条件和迭代器生命周期管理。哪怕只多一个 <code>nullptr</code> 检查遗漏，整个链就可能崩在运行时。</p></node>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
