前置知识
- 数据结构-链表
- 数组排序算法：选择排序[解法1], 归并排序递归版[解法2]，归并排序迭代法[解法3最优解]
- [归并部分基础]合并两个有序链表
- 如果您不满足于此， 笔者也提供冒泡排序，插入排序，快速排序的链表写法。以及，我们会在下文讨论为什么不说明希尔排序，堆排序， 因为两者不适合链表的特性。笔者不打算提供借助容器（数组）的写法， 以及衍生的3种非比较排序写法（计数排序，基数排序，桶排序的写法）
其实笔者也不太了解本篇由于时间原因， 因此鸽了部分篇幅
本篇是对链表的排序， 笔者认为读者阅读此篇理应掌握至少一个数组的排序算法。
测试链接力扣：排序链表
测试链接力扣补充:链表的插入排序
本篇重点：
- 熟悉选择排序的写法， 主要是讲处理数组的选择排序的思想应用于链表。主要是熟悉一下coding。
- 熟悉自上到底的归并排序链表写法， 采取的分治递归， 不过不是最优解，因为系统栈占据一定空间。
- 完全掌握迭代版本的归并排序写法。
原因: 它实现了数组不存在的排序性能。在比较排序中同时拥有时间复杂度O ( n l o g n ) O(nlogn) O(nlogn),空间复杂度:O ( 1 ) O(1) O(1),还具有稳定性。ps:数组迭代版本的快速排序是不具有稳定性的。迭代版本的归并排序的篇幅作者未更，可以自行查视频学习一下。 - 拓展性内容， 链表中的冒泡，插入，快速排序写法。算是数组排序算法对应应用到链表的实践吧。
链表快速排序的内容未更... - 拓展性内容， 为什么希尔排序，堆排序不适合链表？ 这些排序没有对应的实现代码， 因为性能太低了没有价值。
选择排序
要求：
时间复杂度:
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度:
O
(
1
)
O(1)
O(1)
- 选择排序是什么？
- 请看VCR
// 数组中交换i和j位置的数
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// 选择排序
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int minIndex, i = 0; i < arr.length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
数组版本的选择排序思想是什么？
假设数组有n个元素，只需要对前面n-1个元素排序。
[0,i-1]是已排序部分，[i,n-1]是未排序部分。每次从未排序部分选出最小值，记录最小值的下标并与i位置数组元素交换。
那么改成链表版本的怎么做？
- 开局初始认为排序链表是空表， 整个链表是未排序部分。
- 第一次，从未排序部分链表找出最小节点。将其设置新头节点（搞一个新链表）。
- 接下来每次从未排序部分找出最小节点，并其从原链表中删除，并且尾插到排序部分链表。
- 遍历完原链表都会执行上述3的操作，这个时候返回新头节点就是排序链表的下标。
class Solution {
// 获取未排序链表中值最小的节点的前驱节点
public ListNode getSmallestNode(ListNode head) {
ListNode smallNode = head; // 记录当前最小节点
ListNode smallPrev = null; // 记录当前最小节点的前驱节点
ListNode prev = head, cur = head.next; // 初始化前驱节点和当前节点
// 遍历链表寻找最小值
while (cur != null) {
if (cur.val < smallNode.val) {
// 更新最小节点和它的前驱
smallPrev = prev;
smallNode = cur;
}
// 前驱和当前节点指针都向前移动
prev = cur;
cur = cur.next;
}
// 返回最小节点的前驱节点（如果存在）
return smallPrev;
}
// 对链表进行选择排序
public ListNode sortList(ListNode head) {
// 如果链表为空或者只有一个节点，直接返回
if (head == null || head.next == null) {
return head;
}
ListNode tail = null; // tail用于记录已排序部分链表的尾节点
ListNode cur = head; // cur用于遍历未排序部分链表
ListNode smallPrev = null; // 用于记录最小节点的前驱节点
ListNode smallNode = null; // 用于记录最小节点
// 直到原链表处理完毕
while (cur != null) {
smallNode = cur; // 假设当前节点是最小节点
// 寻找从cur开始的未排序部分的最小节点的前驱节点
smallPrev = getSmallestNode(cur);
// 如果smallPrev存在，说明找到的最小节点不是cur
if (smallPrev != null) {
smallNode = smallPrev.next; // 获取最小节点
smallPrev.next = smallNode.next; // 从链表中删除该最小节点
}
// 更新cur位置，如果最小节点是当前cur，则移动cur指针
cur = cur == smallNode ? cur.next : cur;
// 如果排序链表为空，将最小节点作为新链表的头节点
if (tail == null) {
head = smallNode;
} else {
// 否则将最小节点接到排序链表的尾部
tail.next = smallNode;
}
// 更新tail为新的排序链表的尾节点
tail = smallNode;
}
return head; // 返回排序后的链表的头节点
}
}
-
getSmallestNode方法：- 遍历链表，从头开始寻找值最小的节点，同时记录该节点的前驱节点。
- 返回链表中值最小的节点的前驱节点。如果最小节点是头节点，则返回
null。
-
sortList方法：- 实现链表的选择排序算法，逐步找到未排序部分链表中值最小的节点并将其移到新链表的末尾。
- 首先检查输入链表是否为空或只有一个节点，直接返回，因为不需要排序。
- 用
tail指针记录已排序链表的最后一个节点，cur用于遍历原链表。 - 使用
getSmallestNode查找未排序链表中最小节点的前驱节点，并将最小节点移除。 - 如果
tail为空，说明排序链表为空，则将第一个最小节点作为排序链表的头节点。 - 更新
tail和cur，并继续处理未排序部分。
归并排序:递归版本
对比数组中的归并排序， 尝试写出链表的归并排序吧
- 当链表为空表时或者单节点不需要处理， 直接返回head。
- 数组中需要通过
mid划分数组区间， 链表也要找到中点。怎么找？快慢指针！
找到中点后划分链表区间， 然后递归式调用，不断划分链表。 这里还需要一步，定义一个变量在中点前面。断开连接，使得两个链表为独立的链表。 - 将分离的两部分有序链表合并起来。由于合并的时候设计换头， 需要返回合并后新链表的头节点。
这个版本用递归方式实现了对链表的排序。
具体是下面代码各部分的文字陈述：
如果您完成链表中点,合并两个有序链表，那么下面其实就是这两种技巧的运用。
- 递归终止条件：当链表为空或只有一个节点时，直接返回链表头。
- 快慢指针找中点：快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针处于链表的中点。用
prevSlow记录慢指针前面的节点，方便后续断开链表。 - 断开链表：在找到中点后，使用
prevSlow.next = null将链表断开为两部分，分别递归调用sortList进行排序。 - 合并有序链表：通过
mergeTwoLists方法合并两个有序的子链表，使用虚拟头节点来简化处理。
// 提交记得修改类名为Solution
public class MergeSortRecList {
public static ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 快慢指针找终点。
//注意初始化的细节
ListNode fast = head.next.next;
ListNode slow = head.next;
ListNode prevSlow = head;
while (fast != null && fast.next != null) {
prevSlow = slow;
slow = slow.next;
fast = fast.next.next;
}
// 断开链表
prevSlow.next = null;
// 递归式地链式归并排序
head = sortList(head);
slow = sortList(slow);
// 合并两个有序链表
head = mergeTwoLists(head, slow);
return head;
}
public static ListNode mergeTwoLists(ListNode headA, ListNode headB) {
// 借助虚拟头节点，避免讨论
ListNode dummy = new ListNode(Integer.MIN_VALUE);
ListNode tail = dummy;
// 和数组归并排序相同的思路。
while (headA != null && headB != null) {
if (headA.val <= headB.val) {
tail.next = headA;
headA = headA.next;
} else {
tail.next = headB;
headB = headB.next;
}
tail = tail.next;
}
if (headA != null) {
tail.next = headA;
} else {
tail.next = headB;
}
// 虚拟头节点的后继即真实合并链表的头节点。
return dummy.next;
}
}
时间复杂度:
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
空间复杂度:
(
l
o
g
n
)
(logn)
(logn)
排序具有稳定性， 适合排序较大的链表。
由于链表不支持随机访问， 可以采取快慢指针法找中点， 这一步是
O
(
n
)
O(n)
O(n)，比数组找中点慢。
【补充：插入排序】
插入排序：
- 将链表分为有序部分和无序部分。定义cur引用变量遍历原链表，p引用从头节点开始，cur 每次到达一个节点，p就开始遍历当前有序部分， 找到cur节点的合适位置。
- 还需定义变量prev,next。prev始终记录cur节点的前驱节点。当执行插入操作时，需要将cur挪出出去，
prev.next = next,next记录的是cur的后继节点（它可能为null）。然后，将独立出来的cur节点插入到p与p.next之间。 - 由于链表的内存跳跃性，和单链表的单向性。数组中取出元素只是把对象拿出来了，链表需要删除消除其对前后的链接。插入部分，数组需要整体挪动元素，链表只需要修改指针插入即可。另外，单向性，导致链表找位置只能从头开始找。而数组可以从后开始，数组的连续性还可以分出直接插入排序和折半插入排序等等。
- 头节点的特殊处理。链表插入过程中cur有可能是当前节点最小值，需要分类讨论头插的情况，和一般情况。采取虚拟头节点可以简化处理， 本文提供了采用和不采用的写法。
代码如下：
两道题均可以通过， 至少截至现在如此。
插入排序这道题高效的解法其实是别人用归并排序写的，无需叹息100%的写法。
// 提交时注意修改类名为 Solution
// 链表的插入排序这道题记得修改方法名， 与力扣提供函数名一致。
public class InsertionSortList {
// 使用插入排序对链表进行排序
public static ListNode sortList1(ListNode head) {
// 处理特殊情况：链表为空或者只有一个节点时直接返回
if (head == null || head.next == null) {
return head;
}
// 初始化指针：cur指向当前要处理的节点，prev指向cur之前的节点
ListNode cur = head.next, prev = head;
ListNode p = null; // p用于在已排序部分中寻找插入点
ListNode next = null; // next暂存cur的下一个节点
// 虚拟头节点，避免插入头节点时需要特殊处理
ListNode dummy = new ListNode(Integer.MAX_VALUE);
ListNode tail = head;
dummy.next = head;
// 遍历未排序的链表
while (cur != null) {
// 如果当前节点cur的值大于等于前一个节点prev的值，则继续遍历，不需要调整
if (prev.val <= cur.val) {
prev = cur;
cur = cur.next;
} else {
// 当前节点cur的值小于前一个节点prev的值，需要插入到有序部分中
next = cur.next; // 记录下一个节点
// 从头节点（dummy）开始，找到插入位置p
p = dummy;
while (p.next != null && p.next.val <= cur.val) {
p = p.next;
}
// 调整prev的next指针，将cur从链表中移出
prev.next = next;
// 将cur插入到p和p.next之间
cur.next = p.next;
p.next = cur;
// 更新cur为next，继续处理下一个节点
cur = next;
}
}
return dummy.next; // 返回排序后的链表头节点
}
// 另一种插入排序实现，不使用虚拟头节点
public static ListNode sortList(ListNode head) {
// 处理特殊情况：链表为空或者只有一个节点时直接返回
if (head == null || head.next == null) {
return head;
}
// 初始化指针：cur指向当前要处理的节点，prev指向cur之前的节点
ListNode cur = head.next, prev = head;
ListNode p = null; // p用于在已排序部分中寻找插入点
// 遍历未排序的链表
while (cur != null) {
// 先检查链表是否是有序的，如果cur的值大于等于prev的值，则继续遍历
if (cur.val >= prev.val) {
// prev 和 cur 向右移动
prev = cur;
cur = cur.next;
} else {
// 如果cur的值小于prev的值，需要将cur插入到已排序部分
ListNode next = cur.next; // 记录下一个节点
// 如果cur的值小于头节点的值，需要将cur插入到链表头部
if (cur.val < head.val) {
prev.next = next; // 将cur从链表中移出
cur.next = head; // cur插入到头部
head = cur; // 更新头节点为cur
cur = next; // 继续处理下一个节点
} else {
// 在已排序部分中寻找插入点p
p = head;
while (p.next != null && p.next.val <= cur.val) {
p = p.next;
}
// 循环结束时：p.val < cur.val < p.next.val
prev.next = next; // 将cur从链表中移出
// 将cur插入到p和p.next之间
cur.next = p.next;
p.next = cur;
// 更新cur为next，继续处理下一个节点
cur = next;
}
}
}
return head; // 返回排序后的链表头节点
}
}
【补充：冒泡排序】
我愿意称链表冒泡排序拷打了所有背数组模板的冒泡排序选手
数组的冒泡排序很好记忆， 这就导致了很多人也不怎么理解冒泡这一排序。只知道两两交换，迁移到链表版本的冒泡排序就不会了。
先前看过一种统计长度的写法， 让我觉得自己在披着数组写链表的冒泡排序。
所幸， 在询问了朋友之后终于找到了一种比较满意的写法。
回忆，冒泡排序有一种优化方案， 即加了一个标志记录当前循环是否交换了。
可以用这个标志作为链表冒泡排序循环结束条件。
public class BubbleSortList {
// 冒泡排序对链表进行排序
public ListNode bubbleSortList(ListNode head) {
// 特殊情况处理：空链表或者单节点链表
if (head == null || head.next == null) {
return head;
}
boolean isSwap; // 标志是否发生过交换
do {
isSwap = false; // 每轮遍历开始时重置为false
ListNode cur = head;
ListNode prev = null; // 前一个节点指针
ListNode next = head.next; // 下一个节点指针
// 遍历链表，进行相邻节点的比较和交换
while (next != null) {
if (cur.val > next.val) {
// 如果当前节点值大于下一个节点值，交换它们
isSwap = true; // 发生交换，标志设为true
if (prev == null) {
// 处理头节点的情况，直接交换头节点和它的后继节点
head = next;
cur.next = next.next;
next.next = cur;
} else {
// 对于中间节点的交换
prev.next = next;
cur.next = next.next;
next.next = cur;
}
// 更新prev和next指针
prev = next;
next = cur.next;
} else {
// 如果不需要交换，移动到下一个节点
prev = cur;
cur = next;
next = next.next;
}
}
} while (isSwap); // 只要发生交换，继续遍历直到没有交换
return head; // 返回排序后的链表头节点
}
}
1. 希尔排序不适合链表
希尔排序的核心是分组插入排序，它是通过逐步减小的步长（gap）对数组进行分组排序，最终收敛为插入排序。 本身是跳跃性插入排序=>普通插入排序。
这就导致希尔排序依赖数组的结构特性：随机访问。
- 无法像数组那样高效访问间隔元素
- 在数组中，访问第
i
+
g
a
p
i + gap
i+gap 个元素只需要
O
(
1
)
O(1)
O(1) 的时间,
随机访问魅力时刻 - 链表， 天哪， 它只能通过遍历的方式找到第 i + g a p i + gap i+gap 个元素。时间复杂度是 O ( g a p ) O(gap) O(gap)。
- 丧失插入排序的优势
- 链表天然支持高效频繁地插入删除。 链表做不到快速索引进行间隔插入排序， 反而浪费时间去回找间隔元素， 本身就是链表插入排序干的事情啊。 因此， 希尔排序无法做到数组版本的良好时间复杂度。
- 在链表中希尔排序时间复杂度是 0 ( n 2 ) 0(n^2) 0(n2), 甚至不如链表插入排序…
结论就是： 你可以视为链表不存在希尔排序
2. 堆排序不适合链表
堆排序依赖于完全二叉树的特性，完全二叉树又是完美地契合数组实现对堆的存储和api实现。
越是偏向数组的特性，那么越是不适合链表。
数组强查询， 链表强增删
(1) 堆依赖数组索引
- 堆排序的核心是通过数组表示完全二叉树；如果你了解过二叉堆，实际上堆结构依赖数组中父节点索引 i i i,左孩子下标 2 × i + 1 2 \times i+1 2×i+1, 右孩子下标 2 × i + 2 2 \times i + 2 2×i+2； 三者是通过下标建立联系的。
- 链表无法直接通过索引访问元素。数组中的堆孩子找父亲，父亲找左右孩子是 O ( 1 ) O(1) O(1), 链表呢？难道学着数组一样建立编号，然后遍历找孩子吗， 这也太低效了。
(2) 上浮下沉操作的效率低
- 堆排序中，交换元素的位置是关键操作。两个链表中交换节点且保持原结构不变有点复杂且正如第一条所说找节点维护指针时间成本太高了。
总结
请记住链表只有两个排序插入排序和归并排序， 其中迭代版归并排序是链表最强排序。
依赖遍历和频繁插入删除的数组排序算法->那么一定有链表版本。
依赖数组随机访问的排序算法可以视为不存在这些排序的链表版本（性能太低效了…）。