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

算法基本设计思想：
1. 从头结点开始，依次遍历链表中的每个结点；
2. 在剩余未排序的结点中，找到最小的结点，将其与当前结点交换；
3. 继续从当前结点的下一个结点开始，重复上述步骤，直到所有结点都排序完成。

C++代码描述：

void selectSort(Node* head)
{
    Node *p, *q, *min; // p为当前结点，q为待排序结点，min为最小值结点
    for (p = head->next; p != NULL; p = p->next) // 从头结点的下一个结点开始遍历
    {
        min = p;
        for (q = p->next; q != NULL; q = q->next) // 在剩余未排序的结点中找到最小值结点
        {
            if (q->data < min->data)
                min = q;
        }
        if (min != p) // 将最小值结点与当前结点交换
        {
            int temp = min->data;
            min->data = p->data;
            p->data = temp;
        }
    }
}

算法的平均时间复杂度为O(n^2)。

若将链式存储更换为顺序存储，则选择排序的时间复杂度仍为O(n^2)，因为需要遍历所有元素来找到最小值，并进行交换操作。但是在实现上会更加简单，因为可以使用下标来访问数组元素。