试以单链表为存储结构,实现简单选择排序算法
时间: 2023-04-23 12:00:16 浏览: 182
单链表是一种常用的存储结构,可以很方便地实现简单选择排序算法。简单选择排序是一种基本的排序算法,其思想是在未排序的元素中找到最小的元素,将其放到已排序的元素末尾,直到所有元素都排好序为止。
具体实现步骤如下:
1. 定义一个链表结构体,包括数据域和指针域;
2. 定义一个函数,用于实现简单选择排序算法;
3. 在函数中,使用两个指针,一个指向当前未排序部分的头结点,另一个指向当前未排序部分的最小节点;
4. 遍历链表,找到未排序部分的最小节点,并将其与未排序部分的头结点交换数据;
5. 将当前头结点指向下一个节点,继续遍历链表,直到所有节点都排序完成。
以下是示例代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode;
void selectionSort(ListNode* head) {
if (head == NULL) return;
ListNode* cur = head;
while (cur) {
ListNode* minNode = cur;
ListNode* p = cur->next;
while (p) {
if (p->data < minNode->data) {
minNode = p;
}
p = p->next;
}
int tmp = cur->data;
cur->data = minNode->data;
minNode->data = tmp;
cur = cur->next;
}
}
int main() {
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->data = 5;
ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
node1->data = 3;
head->next = node1;
ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
node2->data = 4;
node1->next = node2;
ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
node3->data = 1;
node2->next = node3;
node3->next = NULL;
selectionSort(head);
ListNode* p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
return 0;
}
```
运行结果为:1 3 4 5
阅读全文