如何在 Java 中对链表进行排序？

链表是一种线性数据结构，其中的元素并非存储在连续的内存位置中。
对单链表的节点进行升序排序：

!原始列表原始列表!排序列表排序列表

我们可以使用多种排序技术对链表进行排序：

• 选择排序
• 插入排序
• 快速排序
• 归并排序

方法 1：使用选择排序对链表进行排序

• 在选择排序中，我们维护两个指针：INLINECODEcc8382c8 和 INLINECODE5cdeaaad。
• 最初，INLINECODEa7d311bd 指向头节点，而 INLINECODEb8425bc9 将指向 current 的下一个节点。
• 我们遍历列表，直到 current 指向 null。
• 对于每个当前节点，index 从当前节点的下一个节点开始遍历，直到 null。
• 我们将当前节点的值与其后所有节点的值进行比较，直到列表末尾。
• 如果 INLINECODE9d8d7150 处的值小于 INLINECODEf73fbf92 处的值，我们就交换它们的值。
• 通过这种方式，最小的值会被交换到当前位置。

Java


CODEBLOCK_6514ad1e

Output

Original list:
8 3 7 4 
Sorted list:
3 4 7 8

时间复杂度： O(n ^ 2)
辅助空间： O(1)

方法 2：使用插入排序对链表进行排序

• 在插入排序技术中，我们假设列表中当前元素之前的所有元素都已经排好序了，然后我们从当前元素开始处理。
• 我们将当前元素与其之前的所有元素进行比较，如果顺序不对就进行交换。这个过程会对所有后续元素重复进行。
• 通常来说，插入排序技术会将每个元素与其之前的所有元素进行比较，并对该元素进行排序以将其放置在正确的位置上。

如前所述，对于较小的数据集，插入排序技术更为可行。