有n个记录存储在带头结点的单链表中,设计算法实现简单选择排序。 要求:(1)给出算法的基本设计思想;(2)根据设计思想,采用C或者C++语言描述算法。(3)说明算法的平均时间复杂度。若将链式存储更换为顺序存储,说明其时间复杂度。
时间: 2023-12-27 14:05:33 浏览: 675
算法基本设计思想:
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),因为需要遍历所有元素来找到最小值,并进行交换操作。但是在实现上会更加简单,因为可以使用下标来访问数组元素。
阅读全文