帮我写一段直链式的straight insertion sort
时间: 2024-09-30 10:05:43 浏览: 6
直链表插入排序(Straight Insertion Sort for a linked list)是一种简单的排序算法,适用于已知元素顺序为链表形式的情况。这个过程涉及到遍历每个节点并将其插入到正确的位置,使其有序。
以下是一个基本的直链表插入排序的Java实现:
```java
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public void insertionSortLinkedList(ListNode head) {
if (head == null || head.next == null) {
return; // 如果链表为空或只有一个元素,直接返回
}
ListNode dummy = new ListNode(0); // 创建虚拟头结点,方便处理第一个元素
dummy.next = head;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next; // 保存下一个节点
// 插入操作
if (dummy.next.val <= current.val) {
current.next = nextTemp;
} else {
ListNode node = dummy.next;
while (node.next.val > current.val && node.next != nextTemp) {
node = node.next;
}
current.next = node.next;
node.next = current;
}
current = nextTemp; // 移动到下一个未排序的节点
}
dummy.next = null; // 最后,删除虚拟头结点,得到实际排序好的链表
}
```
在这个代码中,我们使用了一个"虚拟头结点"来简化操作,因为链表的头部不能被改变。然后遍历链表,比较当前节点的值和后面的节点值,根据需要调整它们的链接,直到所有节点都被正确地插入到有序序列中。