有n个记录存储在带头结点的单链表中,设计算法实现简单选择排序。 要求:(1)给出算法的基本设计思想;(2)根据设计思想,采用C语言描述算法。(3)说明算法的平均时间复杂度。若将链式存储更换为顺序存储,说明其时间复杂度。
时间: 2023-12-27 08:05:33 浏览: 63
3-2 试编写一个算法,在带表头结点的单链表中寻找第i个结点.doc
1.算法基本设计思想:
对于给定的单链表,每次找到剩余部分中最小的元素,将其交换到剩余部分的最前面,直到整个单链表有序。
2.C语言描述算法:
```
void selectSort(LinkList L) {
if(L == NULL || L->next == NULL) {
return;
}
LNode *p, *q, *min;
for(p = L->next; p->next != 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 = p->data;
p->data = min->data;
min->data = temp;
}
}
}
```
3.算法的平均时间复杂度为O(n^2)。
4.如果将链式存储更换为顺序存储,则算法的时间复杂度仍然是O(n^2),但是由于顺序存储具有连续性,所以空间复杂度可能会降低,但需要注意的是,元素的插入和删除操作效率会降低。
阅读全文