图解链表的插入排序

本文最后更新于:10 个月前

今天有个同学问我一个考研题,链表的插入排序。

之前写的都删了,一切从简,不探讨过多非主流插入排序的写法。

在文末,再简要对比 稳定 插入排序和 不稳定 插入排序的区别。

一、题目

二、思想

先抛开题目不谈,先说常见的插入排序代码。

  • 无序部分的待排序元素,依次与有序部分的每个元素进行比较,找到合适的插入位置。
  • 将待排序元素,插入该位置。
  • 重复上述两步操作,直到无序部分的待排序元素为 nullptr。

InsertSort.gif

三、图解

0.代码

【为表述方便,我将外层的 while 循环(第 11 行的 while )称为大循环,内层的 while 循环(第 16 层的 while )称为小循环。】

先贴代码,根据后面解释,对照着看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// typedef struct node {
// int data;
// node* next;
// }linknode, *link;

ListNode* InsertSort(link L) {
link p, q, r, u;
p = L->next->next; // 第一个待排序的节点
L->next->next = nullptr;
// 以上两行代码等同于以下两行代码:因为第1个元素永远有序,第0个元素也永远有序。
// p = L->next;
// L->next = nullptr;

while (p) {
r = L; // r 指向 q 的前驱节点
q = L->next; // q 指向有序部分的第一个节点

// 1.寻找 待排序的节点p 合适的插入位置
while (q != nullptr && q->data <= p->data) {
// 如果 有序部分的第一个节点的值 <= 待排序 p 的值,
// 从 有序部分的第一个节点 开始 往后遍历。找到合适的插入位置。
r = q;
q = q->next;
}

// 2.将 待排序的节点p 插入 r 和 q 之间。
u = p->next; // u 指向待排序节点 p 的后继【临时变量】
r->next = p;
p->next = q;

// 3.让 p 指向 u 所指的位置(下一个待排序节点的位置)。
p = u;
}
return L;
}

【为表述方便,我将外层的 while 循环(第 11 行的 while )称为大循环,内层的 while 循环(第 16 行的 while )称为小循环。】

1.第一次进入大循环

在已进入 while 大循环,未进入小 while 循环之前,也就是只执行了以下代码:

1
2
3
4
5
6
7
8
9
10
link p, q, r, u;
p = L->next->next; // 第一个待排序的节点
L->next->next = nullptr;
// 以上两行代码等同于以下两行代码:因为第1个元素永远有序,第0个元素也永远有序。
// p = L->next;
// L->next = nullptr;

while (p) {
r = L; // r 指向 q 的前驱节点
q = L->next; // q 指向有序部分的第一个节点

其中 L 是头结点指针,此时 r 和 L 指向的都是头结点,q 指向第一个有序结点(data = 1)。

2.进入小循环体内

小循环的 while 循环判断中,因为满足 q值(1)<= p值(4),进入小循环体内部;

执行以小循环内代码:

  • 将 r、q 后移。
1
2
3
4
5
6
while (q != nullptr && q->data <= p->data) {
// 如果 有序部分的第一个节点的值 <= 待排序 p 的值,
// 从 有序部分的第一个节点 开始 往后遍历。找到合适的插入位置。
r = q;
q = q->next;
}

后移 r、q 后,如下图所示:

3.跳出小循环体后

因为 q == nullptr,不满足循环条件,所以退出小循环。

并执行以下代码:

  • p 插入 r 和 q 之间。
1
2
3
4
// 2.将 待排序的节点p 插入 r 和 q 之间。
u = p->next; // u 指向待排序节点 p 的后继【临时变量】
r->next = p;
p->next = q;

得到下图:

执行以下代码:

  • p 指向 u 所指的位置。
1
2
// 3.让 p 指向 u 所指的位置(下一个待排序节点的位置)。
p = u;

整理得到下图:

4.第二次进入大循环

进入第二次 大while 循环,r、q 归位。

主要执行的以下代码:

  • r、q 从头开始。
1
2
r = L;      // r 指向 q 的前驱节点
q = L->next; // q 有序部分的第一个节点

为什么 r、q 要回到最开始的位置? 因为 r、q 要从头开始,找到合适的待插入的位置。

5.进入小循环体内

因为 q值(1)<= p值(2),满足小循环体的判断条件。

进入小循环,执行小循环体内代码:

  • r、q 后移。
1
2
3
4
5
6
while (q != nullptr && q->data <= p->data) {
// 如果 有序部分的第一个节点的值 <= 待排序 p 的值,
// 从 有序部分的第一个节点 开始 往后遍历。找到合适的插入位置。
r = q;
q = q->next;
}

得到下图:

6.跳出小循环体后

因为 q值(4)> p值(2),不满足小循环的判断条件,跳出小循环体;

将待排序节点 p 插入 r、q 之间。

执行以下代码:

  • p 插入 r 和 q 之间。
1
2
3
4
// 找到位置,将 待排序的节点 p 插入 r 和 q 之间。
u = p->next; // u 指向待排序节点 p 的后继【临时变量】
r->next = p;
p->next = q;

得到下图:

再执行以下代码:

  • p 指向 u 所指的位置。
1
2
// 让 p 指向 u 所指的位置。
p = u;

整理之后,得到下图:

7.第三次进入大循环

进入第二次 大while 循环,r、q 归位。

主要执行的以下代码:

  • r、q 从头开始。
1
2
r = L;      // r 指向 q 的前驱节点
q = L->next; // q 有序部分的第一个节点

8.进入小循环体内

因为 q值(1)<= p值(4),所以 r、q 后移。

并将小循环体内的代码,循环执行三次。当 q 指向 nullptr 时,跳出小循环体内。

9.跳出小循环体后

此时,将 p 插入到 r、q 之间。

分析

这样不知不觉,全部排序完成。其实我们一直在做两件事:

  • 【找位置】找到 待排序元素p 合适插入的位置。
  • 【插入】将待排序元素p 插入 合适的位置(r、q 之间)。

四、扩展

稳定的和不稳定的插入排序

在排序过程中,如果两个相同数据的前后顺序不发生改变,则为稳定排序。

按以前学过的知识来讲,插入排序、冒泡排序、归并排序都是稳定排序,为什么自己写的插入排序不稳定呢?

因为「小循环的判断条件内没有 等号」。也就是以下代码:

1
2
3
4
while (q != nullptr && q->data < p->data) {
r = q;
q = q->next;
}

当判断条件没有 等号时,就会变成不稳定的排序。具体就不论证了,大家演示一下便知。

复杂度分析

时间:O(n2)

最坏的情况,完全逆序的链表,两个 while 循环,要循环 1+2+3+…+n-2+n-1 次,也就是 n2 / 2 次。

最好的情况,不用插入,遍历一次。O(n)。

空间:O(1)

因为临时占用的空间为 0。

LeetCode 相似题目

147. 对链表进行插入排序


本博客所有文章均个人原创,除特别声明外均采用 CC BY-SA 4.0协议,转载请注明出处!