• 单链表的排序与顺序表的思想类似,如果对顺序表排序的思想及实现还不懂的小伙伴,戳我带你了解八大排序算法的实现。

#include <stdio.h> 
#include <stdlib.h>

typedef struct LNode {
	int data;
	struct LNode *next; 
}LNode,*ListLink;

// 初始化带头节点的单链表 
void initListLink(ListLink &L) {
	L = (LNode *)malloc(sizeof(LNode));
	L->next = NULL;
	return ;
}

// 尾插法建立单链表 
void tailCreateListLink(ListLink &L) {
	initListLink(L);
	
	LNode *p,*s,*r;
	r = L;
	int x;
	while(scanf("%d",&x) != EOF) {
		if(x == -1) break;
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next =s;
		r = s;
	}
	r->next = NULL;
	return ;
}

// 单链表的遍历输出 
void print(ListLink &L) {
	LNode *p = L->next;
	while(p != NULL) {
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
	return ;
}

void insertSort(ListLink &L) {
	/*
		p节点 : 代表每一个即将待插入的节点   
		temp节点 : 代表 p 节点的后继节点,因为我们在插入完当前节点后,
				   可能并不是插入到了最后一个节点,如果是插入到了当前
				   节点之前,则顺序发生改变, 所以我们就需要保留待插入
				   节点的下一个节点,以便于我们执行完插入操作后下一个
				   节点的插入。
		head 节点 : 用于去遍历已排好序的链表,寻找合适的位置进行插入 
	
	*/ 
	LNode *p,*temp,*head;
	
	p = L->next;
	temp = p->next;
	p->next = NULL;
	p = temp;
	
	// 此时 L 中只有一个元素  
	
	while(p != NULL) {
		// 暂存 p 节点的后继节点 
		temp = p->next;
		
		// 在已经排好序的链表中找到合适的位置 
		head = L;
		while(head->next != NULL && p->data > head->next->data) {
			head = head->next;
		}
		
		// 在合适的位置进行插入 
		p->next = head->next;
		head->next = p;
		
		// 接着对下一个进行排序 
		p = temp;
	}
	
	
	return ;
	
}

/*
   冒泡排序:
   因为我们只交换节点的数据,所以在函数
   传递参数时不再需要引用地址。		 
   
*/ 
void bubbleSort(LNode *head) {
	for(LNode *temp = head->next; temp->next != NULL; temp = temp->next) {
		for(LNode *p = head->next; p->next != NULL; p = p->next) {
			if(p->data > p->next->data) {
				int t = p->data;
				p->data = p->next->data;
				p->next->data = t;
			}
		}
	}
	
	return ;
} 

// 选择排序
void selectSort(ListLink &L) {
	for(LNode *p = L->next; p->next != NULL; p = p->next) {
		// 与顺序表排序类似,先找假定一个最小的,接着遍历,寻找一个最小的与之交换数据 
		LNode *minNode = p;
		for(LNode *q = p->next; q->next != NULL; q = q->next) {
			if(q->data < minNode->data) {
				minNode = q;
			}
		}
		int t = minNode->data;
		minNode->data = p->data;
		p->data = t; 
	}
	return ;
} 


int main() {
	ListLink L;
	printf("单链表的排序:\n");
	printf("尾插法建立单链表:") ;
	tailCreateListLink(L);
	printf("初始序列:");
	print(L);
	
	printf("直接插入排序:");
	insertSort(L);
	print(L);


	printf("尾插法建立单链表:") ;
	tailCreateListLink(L);
	printf("初始序列:");
	print(L);
	
	printf("冒泡排序:");
	bubbleSort(L);
	print(L);
	
	printf("尾插法建立单链表:") ;
	tailCreateListLink(L);
	printf("初始序列:");
	print(L);
	
	printf("选择排序:");
	selectSort(L);
	print(L);
	return 0;
}

// 5 6 3 1 9 8 2 4 -1

参考链接:https://blog.csdn.net/weixin_43054397/article/details/111415144