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

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

思想

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

代码

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

// struct ListNode {
//     int data;
//     ListNode* next;
//     ListNode(int data, ListNode* next) : data(data), next(next) {}
// };

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

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

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

1.未进入小循环

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

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

其中 L 是头结点指针，此时 r 和 L 指向的都是第一个结点（data = 1） 。

2.进入小循环体内

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

执行以下代码：

• 将 r、q 后移。

// 如果待排序 p 的值 > 有序部分的第一个节点的值
// 从 有序部分的第一个节点 开始 往后遍历。找到合适的插入位置。
r = q;
q = q->next;

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

3.跳出小循环体后

因为 p 值（2）< q值（4），不满足循环条件，所以退出小循环。

并执行以下代码：

• p 插入 r 和 q 之间。
• p 指向 u 所指的位置。

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

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

得到下图：

4.第二次进入大循环

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

主要执行的以下代码：

• r、q 从头开始。

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

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

5.进入小循环体内

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

进入小循环，执行以下代码：

• r、q 后移。

// 如果待排序 p 的值 > 有序部分的第一个节点的值
// 从 有序部分的第一个节点 开始 往后遍历。找到合适的插入位置。
r = q;
q = q->next;

得到下图：

6.跳出小循环体后

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

将待排序节点 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;

整理之后，得到下图：

7.第三次进入大循环

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

主要执行的以下代码：

• r、q 从头开始。

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

分析

这样不知不觉，我就已经排好前三个元素了，依次类推，重复上述操作，就可以全部排序完成。

其实我们一直在做两件事：

• 【找位置】找到 待排序元素 合适插入的位置。
• 【插入】将待排序元素 插入 合适的位置。

时间复杂度

最坏时间复杂度、平均时间复杂度：O(n²)

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

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

空间复杂度

O(1)

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

稳定排序

相等的两个元素，未发生交换。

相似问题

147. 对链表进行插入排序