在具有领先节点的单链表中存储了n个记录，设计了一种实现简单选择排序的算法。 要求：(1)给出算法的基本设计思想；(2)根据设计思想，使用C或C++语言对算法进行描述。(3)解释该算法的平均时间复杂度。如果链式存储被顺序存储替换，请解释其时间复杂性。

(1) 该算法的基本设计思想为：每次从未排序的子序列中选择一个最小的元素，将其放在已排序子序列的末尾，直到所有元素都被排序。

(2) C++代码如下：

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        std::swap(arr[i], arr[minIndex]);
    }
}

(3) 该算法的平均时间复杂度为O(n^2)，因为每次需要遍历未排序子序列找到最小的元素。如果链式存储被顺序存储替换，则时间复杂度变为O(n^2)，因为在顺序存储中，每次需要遍历未排序子序列找到最小的元素，同时还需要进行元素的交换操作，这些操作的时间复杂度都是O(1)。