1)假设待排序记录存储在一个单链表中，写出基于单链表存储结构的选择排序算法。

在单链表中实现选择排序不同于数组操作，因为链表访问不是随机的，而是线性的。以下是基于单链表的选择排序算法：

1. 初始化：找到链表中的最小元素（即头结点），并将其设为新的临时头结点，同时更新指向最小元素的指针。

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

def find_min(head):
    min_val = head.val
    min_node = head
    while head.next:
        if head.next.val < min_val:
            min_val = head.next.val
            min_node = head.next
        head = head.next
    return min_node

2. 分配记录：遍历剩余链表，将当前最小元素与当前节点连接，形成一个新的有序区段。每次循环找到下一个最小值，并与当前节点之后的所有节点进行比较。

def selection_sort_linked_list(head):
    if not head or not head.next:
        return head
    
    # 将最小值节点添加到新链表头部
    min_head = find_min(head)
    
    # 更新原链表的头指针
    head.next.next = selection_sort_linked_list(min_head.next)
    
    # 返回排序后的新链表头
    return min_head

3. 结束条件：当链表只剩下一个节点或者为空时，排序结束，返回头节点作为已排序链表。

注意，这种方法实际上并不是真正的选择排序，因为它在链表上移动节点的方式并不像数组那样简单，而且它也不能保证链表顺序不变（因为它没有使用临时数组）。这更类似于链表版的冒泡排序或者插入排序。