2.2 链表排序

ITCharge大约 5 分钟

1. 链表排序简介

在数组排序中，常见的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。

而对于链表排序而言，因为链表不支持随机访问，访问链表后面的节点只能依靠 next 指针从头部顺序遍历，所以相对于数组排序问题来说，链表排序问题会更加复杂一点。

下面先来总结一下适合链表排序与不适合链表排序的算法：

适合链表的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。
不适合链表的排序算法：希尔排序。
可以用于链表排序但不建议使用的排序算法：堆排序。

希尔排序为什么不适合链表排序？

希尔排序：希尔排序中经常涉及到对序列中第 $i + gap$ 的元素进行操作，其中 $gap$ 是希尔排序中当前的步长。而链表不支持随机访问的特性，导致这种操作不适合链表，因而希尔排序算法不适合进行链表排序。

为什么不建议使用堆排序？

堆排序：堆排序所使用的最大堆 / 最小堆结构本质上是一棵完全二叉树。而完全二叉树适合采用顺序存储结构（数组）。因为数组存储的完全二叉树可以很方便的通过下标序号来确定父亲节点和孩子节点，并且可以极大限度的节省存储空间。

而链表用在存储完全二叉树的时候，因为不支持随机访问的特性，导致其寻找子节点和父亲节点会比较耗时，如果增加指向父亲节点的变量，又会浪费大量存储空间。所以堆排序算法不适合进行链表排序。

如果一定要对链表进行堆排序，则可以使用额外的数组空间表示堆结构。然后将链表中各个节点的值依次添加入堆结构中，对数组进行堆排序。排序后，再按照堆中元素顺序，依次建立链表节点，构建新的链表并返回新链表头节点。

需要用到额外的辅助空间进行排序的算法

刚才我们说到如果一定要对链表进行堆排序，则需要使用额外的数组空间。除此之外，计数排序、桶排序、基数排序都需要用到额外的数组空间。

接下来，我们将对适合链表排序的 8 种算法进行一一讲解。当然，这些排序算法不用完全掌握，重点是掌握 「链表插入排序」、「链表归并排序」 这两种排序算法。

链表排序常用的方法有冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。

链表冒泡排序：每次比较相邻两个节点的值，大的往后移。重复多次，直到链表有序。时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$ 。
链表选择排序：每次从未排序部分找到最小的节点，和当前节点交换。重复操作，直到链表有序。时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$ 。
链表插入排序：每次取一个节点，插入到已排序部分的合适位置。不断重复，直到全部节点有序。时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$ 。
链表归并排序：把链表分成两半，递归排序，再合并。适合链表，时间复杂度 O $(n \log n)$ ，空间复杂度 $O(1)$ 。
链表快速排序：选一个基准值，把小于基准的放左边，大于的放右边。对两边递归排序。时间复杂度 $O(n \log n)$ ，空间复杂度 $O(1)$ 。
链表计数排序：先找最大最小值，用数组统计每个值出现次数，再按顺序重建链表。适合值域不大时用。时间复杂度 $O(n + k)$ ，空间复杂度 $O(k)$ 。
链表桶排序：把节点分到不同的桶里，每个桶内单独排序，再合并所有桶。适合数据分布均匀时用。时间复杂度 $O(n)$ ，空间复杂度 $O(n + m)$ 。
链表基数排序：按个位、十位、百位等分多轮，把节点分到不同的桶里，再合并。适合数字位数不多时用。时间复杂度 $O(n \times k)$ ，空间复杂度 $O(n + k)$ 。