链表的插入排序详解

本文最后更新于:2 小时前

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

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

思想

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

InsertSort.gif

代码

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

// 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(n2)

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

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

空间复杂度

O(1)

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

稳定排序

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

相似问题

147. 对链表进行插入排序


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

 目录

致敬李文亮及各路英雄好汉!