本文讲解如何在双向链表中实现两级排序：先按电影上映年份升序排列，年份相同时再按片名字母序升序排列；核心是将比较逻辑封装进 Movie 类的 compareTo 方法，并重写插入排序逻辑以统一、健壮地处理所有情况。
本文讲解如何在双向链表中实现两级排序：先按电影上映年份升序排列，年份相同时再按片名字母序升序排列；核心是将比较逻辑封装进 `movie` 类的 `compareto` 方法，并重写插入排序逻辑以统一、健壮地处理所有情况。
在实现双向链表的复合排序时，关键挑战在于避免分散、重复且易错的比较逻辑。原代码中，年份比较与片名比较被拆散在多个分支（如 else if (releaseDate == ...) 单独处理），不仅导致逻辑冗余，还引发严重缺陷：部分节点丢失、相同年份影片未正确按字母序插入——这正是因 final else 分支仅依赖 releaseDate 判断位置，完全忽略了相同年份下的字典序要求。
✅ 正确做法：用 Comparable 统一比较契约
推荐让 Movie 类实现 Comparable<Movie> 接口，将“先比年份、再比片名”的业务规则集中定义在 compareTo() 方法中：
class Movie implements Comparable<Movie> {
int releaseDate;
String movieName;
// 构造函数等略...
@Override
public int compareTo(Movie o) {
// 第一级：按 releaseDate 升序
if (this.releaseDate != o.releaseDate) {
return Integer.compare(this.releaseDate, o.releaseDate);
}
// 第二级：年份相同时，按 movieName 字典序升序（忽略大小写可加 .toLowerCase()）
return this.movieName.compareTo(o.movieName);
}
}✅ 优势：Integer.compare() 安全处理整数溢出；String.compareTo() 已内置 Unicode 字典序，无需手动遍历字符；逻辑清晰、可复用、易测试。
✅ 重构 sortedInsert：单一分支，语义明确
基于 compareTo()，sortedInsert 可大幅简化，消除冗余条件与潜在 bug：
public static Node sortedInsert(Node headRef, Node newNode) {
// 空链表：直接设为头结点
if (headRef == null) {
return newNode;
}
// 新节点应插在头部？（即 headRef.movie > newNode.movie）
if (headRef.movie.compareTo(newNode.movie) > 0) {
newNode.next = headRef;
headRef.prev = newNode;
return newNode; // 新头节点
}
// 向后查找插入位置：找到第一个 movie.compareTo(newNode.movie) > 0 的节点
Node current = headRef;
while (current.next != null && current.next.movie.compareTo(newNode.movie) < 0) {
current = current.next;
}
// 在 current 之后插入 newNode
newNode.next = current.next;
newNode.prev = current;
if (current.next != null) {
current.next.prev = newNode;
}
current.next = newNode;
return headRef;
}⚠️ 注意事项：
- 双向链接必须完整维护：插入时需同时更新 prev 和 next，尤其注意 current.next == null（尾部插入）时避免空指针。
- insertionSort 主方法无需修改，它仅负责逐个提取节点并调用 sortedInsert，已具备通用性。
- 若需降序，只需翻转 compareTo 返回值符号（如 return -this.releaseDate + ...），但不推荐硬编码，应通过策略模式或参数化设计扩展。
✅ 验证结果示例
输入节点（含重复年份）：
Movie("Titanic", 1997), Movie("Fast & Furious", 1997),
Movie("The Matrix", 1999), Movie("Interstellar", 2014),
Movie("The Hobbit...", 2014)排序后输出（严格满足：年份升序 → 同年份片名字典升序）：
1997 Fast & Furious 1997 Titanic 1999 The Matrix 2014 Interstellar 2014 The Hobbit: The Battle of the Five Armies
总结
- ❌ 避免在多处重复编写字段比较逻辑（如手动 charAt() 循环），极易出错且不可维护；
- ✅ 将排序规则下沉至数据模型（Movie），符合单一职责原则；
- ✅ 利用 Comparable + compareTo() 实现声明式、可读性强的比较契约；
- ✅ sortedInsert 应聚焦“定位插入点”，所有比较委托给 movie.compareTo()，逻辑扁平、边界清晰；
- 最终得到稳定、可扩展、易于单元测试的双向链表排序实现。
