写出以单链表为存储结构的一组数 据的简单选择排序算法。
时间: 2024-02-17 12:05:14 浏览: 105
一种最简单的选择排序算法
好的,以下是以单链表为存储结构的简单选择排序算法的实现过程:
1. 定义一个链表节点结构体,包含数据域和指向下一节点的指针域。
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
2. 定义一个选择排序函数,输入参数为链表头指针,返回值为排序后的链表头指针。具体实现过程如下:
```
ListNode* selectionSortList(ListNode* head) {
if (!head || !head->next) return head; // 特判链表为空或只有一个节点的情况
ListNode *dummy = new ListNode(0); // 定义一个虚拟头节点
dummy->next = head;
ListNode *cur = head;
while (cur->next) { // 循环遍历链表
ListNode *minNode = cur, *pre = dummy;
while (cur->next) { // 找到当前未排序部分的最小值节点以及其前一个节点
if (cur->next->val < minNode->val) {
minNode = cur->next;
pre = cur;
}
cur = cur->next;
}
if (minNode != cur) { // 如果最小值节点不是当前节点,交换它们的位置
pre->next = minNode->next;
minNode->next = cur->next;
cur->next = minNode;
}
cur = pre->next;
}
return dummy->next;
}
```
3. 调用选择排序函数进行排序,示例代码如下:
```
ListNode* head = new ListNode(3);
head->next = new ListNode(1);
head->next->next = new ListNode(4);
head->next->next->next = new ListNode(2);
head = selectionSortList(head);
while (head) {
cout << head->val << " ";
head = head->next;
}
```
输出结果为:1 2 3 4。
以上就是以单链表为存储结构的简单选择排序算法的实现过程。
阅读全文