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

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

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

1.题目

2.思想

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

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

3.图解

3.0 代码

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

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

// 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;
}

3.1 第一次进入大循环

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

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）。

3.2 进入小循环体内

小循环的 while 循环判断中，因为满足 q值（1）<= p值（4），进入小循环体内部；

执行以小循环内代码：

• 将 r、q 后移。

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

后移 r、q 后，如下图所示：

3.3 跳出小循环体后

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

并执行以下代码：

• p 插入 r 和 q 之间。

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

得到下图：

执行以下代码：

• p 指向 u 所指的位置。

// 3.让 p 指向 u 所指的位置（下一个待排序节点的位置）。
p = u;

整理得到下图：

3.4 第二次进入大循环

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

主要执行的以下代码：

• r、q 从头开始。

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

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

3.5 进入小循环体内

因为 q值（1）<= p值（2），满足小循环体的判断条件。

进入小循环，执行小循环体内代码：

• r、q 后移。

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

得到下图：

3.6 跳出小循环体后

因为 q值（4）> p值（2），不满足小循环的判断条件，跳出小循环体；

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

执行以下代码：

• p 插入 r 和 q 之间。

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

得到下图：

再执行以下代码：

• p 指向 u 所指的位置。

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

整理之后，得到下图：

3.7 第三次进入大循环

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

主要执行的以下代码：

• r、q 从头开始。

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

3.8 进入小循环体内

因为 q值（1）<= p值（4），所以 r、q 后移。

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

3.9 跳出小循环体后

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

3.10 分析

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

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

4.扩展

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

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

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

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

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

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

4.2 复杂度分析

时间：O(n²)

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

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

空间：O(1)

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

4.3 LeetCode 相似题目

147. 对链表进行插入排序