设待排序的记录序列用单链表作存储结构，试写出直接插入排序算法。

好的，以下是单链表直接插入排序算法的实现过程：

1. 首先从第二个节点开始遍历整个链表。

2. 对于每一个节点，将其与前面的已排序序列进行比较，找到其插入位置。

3. 插入节点到正确的位置。

4. 重复以上步骤，直到整个链表有序。

算法的代码实现如下（假设链表头指针为head）：

void InsertSort(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    ListNode* p = head->next; // 指向第2个节点
    head->next = NULL; // 把第1个节点作为有序序列
    while (p != NULL) {
        ListNode* q = head;
        ListNode* temp = p->next; // 保存p的下一个节点
        while (q->next != NULL && q->next->val < p->val) {
            q = q->next;
        }
        p->next = q->next;
        q->next = p;
        p = temp; // 处理下一个节点
    }
}

以上是单链表直接插入排序的实现方法，希望能够帮到你。

相关问题

设待排序的记录序列用单链表作存储结构，试写出简单选择排序算法。

好的，以下是单链表简单选择排序算法的实现过程：

1. 首先从头节点开始，将其作为当前无序序列的最小值。

2. 遍历整个链表，查找当前无序序列中的最小值，并记录其位置。

3. 将最小值节点从无序序列中删除，并插入到有序序列的尾部。

4. 重复以上步骤，直到整个链表有序。

算法的代码实现如下（假设链表头指针为head）：

void SelectSort(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    ListNode* p = head;
    while (p->next != NULL) {
        ListNode* minNode = p; // 记录当前无序序列的最小值节点
        ListNode* q = p->next;
        while (q != NULL) {
            if (q->val < minNode->val) {
                minNode = q;
            }
            q = q->next;
        }
        // 将最小值节点从无序序列中删除
        if (minNode != p) {
            int temp = p->val;
            p->val = minNode->val;
            minNode->val = temp;
        }
        p = p->next; // 处理下一个无序序列
    }
}

以上是单链表简单选择排序的实现方法，希望能够帮到你。

设待排序的记录序列用单链表作存储结构，编写直接插入排序

算法的代码。

好的，以下是单链表直接插入排序算法的代码：

# 定义链表节点类
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def insertionSortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    dummy = ListNode(0)     # 定义新的链表节点
    dummy.next = head       # 新链表的头结点是原链表的第一个节点
    lastSorted = head       # 上一个已排序的节点
    curr = head.next        # 当前待排序节点
    while curr:
        # 单链表中删除待排序的节点
        if lastSorted.val <= curr.val:
            lastSorted = lastSorted.next
        else:
            prev = dummy
            while prev.next.val <= curr.val:
                prev = prev.next
            lastSorted.next = curr.next
            curr.next = prev.next
            prev.next = curr
        curr = lastSorted.next
    return dummy.next

该算法的时间复杂度为 O(n^2)，空间复杂度为 O(1)。