1.有n个记录存储在带头结点的单链表中，设计算法实现简单选择排序。 要求：（1）给出算法的基本设计思想；（2）根据设计思想，采用C或者C++语言描述算法。（3）说明算法的平均时间复杂度。若将链式存储更换为顺序存储，说明其时间复杂度。

1. 基本设计思想：
（1）从头节点开始，依次遍历链表中的每一个节点；
（2）每次找到未排序区间中最小的节点，将其与未排序区间的第一个节点进行交换；
（3）重复执行步骤（1）和（2），直到所有节点都被排序。

2. C++代码实现：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void selectionSortList(ListNode* head) {
    ListNode *p = head, *q = NULL;
    int tmp;
    while (p && p->next) {
        q = p->next;
        while (q) {
            if (p->val > q->val) {
                tmp = p->val;
                p->val = q->val;
                q->val = tmp;
            }
            q = q->next;
        }
        p = p->next;
    }
}

3. 算法的平均时间复杂度为 $O(n^2)$，其中 $n$ 表示链表中节点的个数。

4. 如果将链式存储更换为顺序存储，简单选择排序的时间复杂度仍然是 $O(n^2)$，因为每次寻找最小值需要遍历整个数组。但是，由于顺序存储的访问速度快于链式存储，实际运行效率可能会有所提高。