图解链表的插入排序
本文最后更新于:4 个月前
今天有个同学问我一个考研题,链表的插入排序。
之前写的都删了,一切从简,不探讨过多非主流插入排序的写法。
在文末,再简要对比 稳定 插入排序和 不稳定 插入排序的区别。
一、题目
二、思想
先抛开题目不谈,先说常见的插入排序代码。
- 无序部分的待排序元素,依次与有序部分的每个元素进行比较,找到合适的插入位置。
- 将待排序元素,插入该位置。
- 重复上述两步操作,直到无序部分的待排序元素为 nullptr。
三、图解
0.代码
【为表述方便,我将外层的 while 循环(第 11 行的 while )称为大循环,内层的 while 循环(第 16 层的 while )称为小循环。】
先贴代码,根据后面解释,对照着看。
1 |
|
【为表述方便,我将外层的 while 循环(第 11 行的 while )称为大循环,内层的 while 循环(第 16 行的 while )称为小循环。】
1.第一次进入大循环
在已进入 while 大循环,未进入小 while 循环之前,也就是只执行了以下代码:
1 |
|
其中 L 是头结点指针,此时 r 和 L 指向的都是头结点,q 指向第一个有序结点(data = 1)。
2.进入小循环体内
小循环的 while 循环判断中,因为满足 q值(1)<= p值(4),进入小循环体内部;
执行以小循环内代码:
- 将 r、q 后移。
1 |
|
后移 r、q 后,如下图所示:
3.跳出小循环体后
因为 q == nullptr
,不满足循环条件,所以退出小循环。
并执行以下代码:
- p 插入 r 和 q 之间。
1 |
|
得到下图:
执行以下代码:
- p 指向 u 所指的位置。
1 |
|
整理得到下图:
4.第二次进入大循环
进入第二次 大while 循环,r、q 归位。
主要执行的以下代码:
- r、q 从头开始。
1 |
|
为什么 r、q 要回到最开始的位置? 因为 r、q 要从头开始,找到合适的待插入的位置。
5.进入小循环体内
因为 q值(1)<= p值(2),满足小循环体的判断条件。
进入小循环,执行小循环体内代码:
- r、q 后移。
1 |
|
得到下图:
6.跳出小循环体后
因为 q值(4)> p值(2),不满足小循环的判断条件,跳出小循环体;
将待排序节点 p 插入 r、q 之间。
执行以下代码:
- p 插入 r 和 q 之间。
1 |
|
得到下图:
再执行以下代码:
- p 指向 u 所指的位置。
1 |
|
整理之后,得到下图:
7.第三次进入大循环
进入第二次 大while 循环,r、q 归位。
主要执行的以下代码:
- r、q 从头开始。
1 |
|
8.进入小循环体内
因为 q值(1)<= p值(4),所以 r、q 后移。
并将小循环体内的代码,循环执行三次。当 q 指向 nullptr 时,跳出小循环体内。
9.跳出小循环体后
此时,将 p 插入到 r、q 之间。
分析
这样不知不觉,全部排序完成。其实我们一直在做两件事:
- 【找位置】找到 待排序元素p 合适插入的位置。
- 【插入】将待排序元素p 插入 合适的位置(r、q 之间)。
四、扩展
稳定的和不稳定的插入排序
在排序过程中,如果两个相同数据的前后顺序不发生改变,则为稳定排序。
按以前学过的知识来讲,插入排序、冒泡排序、归并排序都是稳定排序,为什么自己写的插入排序不稳定呢?
因为「小循环的判断条件内没有 等号」。也就是以下代码:
1 |
|
当判断条件没有 等号时,就会变成不稳定的排序。具体就不论证了,大家演示一下便知。
复杂度分析
时间:O(n2)
最坏的情况,完全逆序的链表,两个 while 循环,要循环 1+2+3+…+n-2+n-1 次,也就是 n2 / 2 次。
最好的情况,不用插入,遍历一次。O(n)。
空间:O(1)
因为临时占用的空间为 0。
LeetCode 相似题目
本博客所有文章均个人原创,除特别声明外均采用 CC BY-SA 4.0协议,转载请注明出处!