链表排序的最大问题是, 不能像数组那样简单的交换节点, 要操作一个节点, 很多时候需要知道这个节点之前的节点.
因此像选择排序这种直接通过索引交换位置的方法, 操作链表就变得非常麻烦. 但是插入排序就提供了一个崭新的思路.
插入排序的一大特点之前已经了解了, 就是某个元素的左侧是已经排序的, 右侧(包括其自己)是尚未排序的, 等于就将整组数据分成了两部分, 一部分已排序, 一部分未排序.
排序的过程也就是将所有未排序部分中的数据一个一个的插入到已排序部分中. 这就比较符合链表的思想, 一起来看看.
- 链表排序的核心思想与准备工作
- 核心排序方法编写
- 改进一下链表数据结构
链表排序的核心思想与准备工作
真的佩服前人想出来的算法, 链表排序的核心思想就是使用插入排序, 将链表一分为二, 一部分是已经排序好的, 另外一部分是尚未排序的. 然后不断的将没有排序的部分插入到已经排序的链表的正确位置.
这里的细节就是如果要将一个节点插入到链表中, 必须获得其前一个节点的引用.
还一个不同点是, 数组是Java提供的基本类型, 可以方便快捷的在外部进行操作, 但是链表结构我们使用了内部类Node, 因此我们考虑创建一个包含实现了Comparable接口的元素的链表类型, 然后将排序方法作为这个链表对象的方法.
所以首先来编写一个使用Comparable接口的链表类:
public class LinkedList<T extends Comparable<? super T>> {
private class Node {
private T data;
private Node next;
public Node(T data) {
this(data, null);
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
private Node firstNode;
private int numberOfEntries;
public LinkedList() {
this.firstNode = null;
numberOfEntries = 0;
}
public boolean add(T entry) {
Node newNode = new Node(entry, firstNode);
firstNode = newNode;
numberOfEntries++;
return true;
}
public boolean isEmpty() {
return numberOfEntries == 0;
}
public boolean remove() {
if (!isEmpty()) {
firstNode = firstNode.next;
numberOfEntries--;
return true;
} else {
return false;
}
}
public void showAllEntries() {
Node currentNode = firstNode;
while (currentNode != null) {
System.out.print(currentNode.data+" ");
currentNode = currentNode.next;
}
System.out.println();
}
}
这个链表仅仅只保留了计数, 从链表首位置添加元素, 从链表首位置删除元素的功能.
我们的排序方法将作为这个类的方法存在, 给这个链表进行就地排序.
核心排序方法编写
按照之前的思路, 我们核心的排序方法的工作思路如下:
- 将链表从头开始一分为二, 一个链表是已经排序的链表, 一个是尚未排序的部分.
- 具体如何拆分呢? 由于我们最后的链表依然是要以firstNode变量为开头, 并且在排序方法启动的时候, 所有的元素都是尚未排序的, 因此开始的时候直接新创建一个变量比如叫做notSortedNode指向firstNode指向的节点, 然后直接将firstNode设置为null.
这样操作之后, firstNode相当于已排序部分, 为空. notSortedNode中为原来链表的所有元素, 全部都没排序.
- 只要notSortedNode中还有元素, 将元素插入到firstNode节点链表的适当位置.
- notSortedNode中没有元素的时候, 停止操作, 此时得到的firstNode就是已经排序的链表.
依据这个思路, 我们将元素插入到firstNode节点链表的适当位置抽取成一个方法, 用来辅助核心排序方法. 来用代码实现:
/**
* 将一个节点插入到一个已经排序的链表的方法. 核心原理是将被插入的节点的数据与被插入的链表中每个节点进行比较, 根据是否降序找到大于/小于被插入的节点的数据的那一项, 然后将节点插入至那一项之前
* 如果遍历都没能够找到插入位置, 说明需要将被插入的节点插入到节点末尾
* @param insertedNode 要插入的节点
* @param reverse 升序还是降序, true表示降序, false表示升序
*/
private void insertIntoNodes(Node insertedNode, boolean reverse) {
//如果已排序链表中没有元素, 直接将其插入第一个节点,
if (firstNode == null) {
insertedNode.next = null;
firstNode = insertedNode;
} else {
//获取要插入的节点的数据
T data = insertedNode.data;
//开始遍历已排序链表, 先弄出两个引用, 一个指向遍历到的节点, 一个指向上一个节点, 对于第一个节点, 前一个节点为空
Node previousNode = null;
Node currentNode = firstNode;
boolean inserted = false;
//对于链表中每一个节点来判断是否可以插入
while (currentNode != null && !inserted) {
//如果某个节点的数据大于/小于要插入的节点, 说明要插入到这个节点之前.
//根据是否降序来选择比较的结果, 降序则是遍历到的节点的数据大于要插入的节点的数据
if (!reverse) {
//判断到大于0的时候说明发现了正确位置
if (currentNode.data.compareTo(data) > 0) {
//如果上一个节点为空, 说明是首节点, 就跟往链表中插入一个新元素一样
if (previousNode == null) {
insertedNode.next = firstNode;
firstNode = insertedNode;
//如果不为空, 将其插入到上一个和当前节点之间
} else {
insertedNode.next = currentNode;
previousNode.next = insertedNode;
}
//只要执行到这里, 就说明已经插入完了, 将已经插入变量设置为true
inserted = true;
//如果要某个节点的数据没有大于要插入的节点, 更新当前节点和上一个节点, 然后继续遍历链表
} else {
previousNode = currentNode;
currentNode = currentNode.next;
}
//升序的逻辑和降序完全一样, 只是比较大小的逻辑不同
} else {
if (currentNode.data.compareTo(data) < 0) {
//如果上一个节点为空, 说明是首节点, 就跟往链表中插入一个新元素一样
if (previousNode == null) {
insertedNode.next = firstNode;
firstNode = insertedNode;
//如果不为空, 将其插入到上一个和当前节点之间
} else {
insertedNode.next = currentNode;
previousNode.next = insertedNode;
}
//只要找到了大于的部分, 就说明已经插入完了, break循环
inserted = true;
//如果要某个节点的数据没有大于要插入的节点, 继续寻找下一个节点
} else {
previousNode = currentNode;
currentNode = currentNode.next;
}
}
}
//执行到此处说明while循环结束, currentNode是null, previousNode是最后一个节点. 此时需要再判断一下是否插入成功. 如果一直到末尾现在都没有插入成功, 说明当前元素比起已经排序的所有元素, 是其中最小/最大的, 则需要将其插入到末尾
if (!inserted) {
//末尾节点是previousNode, 直接将其设置为previousNode.next. 这里还要记住, 一定要将insertedNode的next设置为null, 因为插入的实际上是未排序的链表的首节点, 如果不设置成null, 实际上是把整条链表都插入过来了.
previousNode.next = insertedNode;
insertedNode.next = null;
}
}
}
有了插入方法的辅助, 核心排序方法就简单多了:
public void sort() {
//将链表拆分成两个, unsortedNode是未排序链表, 就是原来的整条链表
Node unsortedNode = firstNode;
//firstNode是未排序的链表, 一开始为空
firstNode = null;
//只要未排序链表中还有元素
while (unsortedNode != null) {
//保存对未排序链表第一个节点的引用
Node currentNode = unsortedNode;
//将未排序链表的首部指向下一个元素
unsortedNode = unsortedNode.next;
//对未排序链表的第一个节点进行排序
insertIntoNodes(currentNode, false);
}
}
关于核心排序方法, 要解释一下的是while循环中三个语句的顺序. 为什么不是先插入, 再移动到下一个节点, 是因为我们的插入方法, 必定会修改其传入的参数的next节点, 不是修改成null, 就是修改成某一个节点.
因此在插入之后, insertIntoNodes()方法的第一个参数的next会发生变化, 如果核心排序方法写成这样:
//只要未排序链表中还有元素
while (unsortedNode != null)
//对未排序链表的第一个节点进行排序
insertIntoNodes(unsortedNode, false);
//这句会有问题(实际上unsortedNode.next已经不是原来的未排序链表的下一个元素了)
unsortedNode = unsortedNode.next;
}
此时的unsortedNode.next已经被修改, 所以红色语句实际没有把unsortedNode指向下一个正确的位置.
既然有了sort(), 也再来一个sortDesc():
public void sortDesc() {
Node unsortedNode = firstNode;
firstNode = null;
while (unsortedNode != null) {
Node currentNode = unsortedNode;
unsortedNode = unsortedNode.next;
insertIntoNodes(currentNode, true);
}
}
可以发现, 插入排序的时间复杂度依然是n的平方级别, 但是插入排序的这种思想, 特别适合链表. 如果使用选择排序, 由于链表的控制比较麻烦, 在交换元素的时候就会非常麻烦.
改进一下链表数据结构
由于插入排序的时间复杂度是n平方级别, 如果没事就排一次, 似乎没有必要. 我们可以在链表数据结构中加上一个私有布尔变量, 用于表示当前的链表是否已经排过序. 如果已经排序了, 就无须再傻傻的再拆分然后执行一次了.
那么很显然, 这个变量初始应该是false, 在每次执行完排序方法之后, 都应该将其设置成为true. 那么什么时候应该设置成false呢, add()方法执行之后, 可以将其设置为false, 因为无法保证插入的元素究竟是不是有序.
如果删除一个元素, 由于是从链表的头部进行删除, 此时可以检测是否排序, 如果已经排序, 从链表头部删除一个节点, 并不会影响链表的有序性. 如果未排序, 删掉一个依然是未排序. 所以remove方法不会影响有序性, 也就无需操作这个变量.
其他的打印内容和是否为空的判断都不影响有序性.
所以修改后的类如下:
public class LinkedList<T extends Comparable<? super T>> {
......
//是否已经升序排序
private boolean isSorted = false;
//是否已经降序排序
private boolean isSortedDesc = false;
//排序方法只有在当前链表未排序的时候才会工作
public void sort() {
if (!isSorted) {
Node unsortedNode = firstNode;
firstNode = null;
while (unsortedNode != null) {
Node currentNode = unsortedNode;
unsortedNode = unsortedNode.next;
insertIntoNodes(currentNode, false);
}
//将升序排序设置成true, 将降序排序设置成false
isSorted = true;
isSortedDesc = false;
}
}
public void sortDesc() {
if (!isSorted) {
Node unsortedNode = firstNode;
firstNode = null;
while (unsortedNode != null) {
Node currentNode = unsortedNode;
unsortedNode = unsortedNode.next;
insertIntoNodes(currentNode, true);
}
//将降序排序设置成true, 将升序排序设置成false
isSorted = false;
isSortedDesc = true;
}
}
//插入新元素之后就将两种排序都设置为false
public boolean add(T entry) {
Node newNode = new Node(entry, firstNode);
firstNode = newNode;
numberOfEntries++;
isSorted = false;
isSortedDesc = false;
return true;
}
......
}
这样能排序的链表也搞定了, 爽多了. 下边继续看希尔排序.
