typedef int datatype; typedef struct link_node { datatype info; struct link_node *next; } node; typedef node *linklist; void sort(linklist head) {

### C语言实现单链表排序算法 在C语言中，可以通过多种方法对单链表进行排序。以下是基于冒泡排序和快速排序两种常见方式的实现。 #### 冒泡排序实现 冒泡排序的核心思想是比较相邻两个节点的数据值并交换它们的位置。对于单链表而言，由于其结构特点，需要调整指针来完成节点位置的交换。 ```c typedef struct link_node { int data; struct link_node *next; } ListNode; void swapNodes(ListNode **head_ref, ListNode *node1, ListNode *node2) { if (node1->data != node2->data) { // 如果两者的数据不同，则执行交换逻辑 int temp = node1->data; node1->data = node2->data; node2->data = temp; } } void bubbleSortList(ListNode **head_ref) { bool swapped; ListNode *ptr1; ListNode *lptr = NULL; if (*head_ref == NULL || (*head_ref)->next == NULL) return; // 判断列表是否为空或者只有一个节点 do { swapped = false; ptr1 = *head_ref; while (ptr1->next != lptr) { // 遍历直到最后一个已排序部分之前 if (ptr1->data > ptr1->next->data) { // 比较当前节点与其下一个节点的数据 swapNodes(head_ref, ptr1, ptr1->next); // 调整节点数据 swapped = true; } ptr1 = ptr1->next; } lptr = ptr1; // 更新最后比较的部分 } while (swapped); } ``` 上述代码实现了单链表的冒泡排序[^5]。它通过不断遍历整个链表并将较大的元素逐步移动到最后面的方式完成排序过程。 --- #### 快速排序实现 快速排序是一种分治策略的应用，在数组上的表现非常高效。然而将其应用到单链表时需要注意递归调用以及子链表之间的连接处理。 ```c ListNode* partition(ListNode *low, ListNode *high) { int pivot = high->data; ListNode *i = low->prev; // 定义前驱节点用于后续插入操作 ListNode *j = low; while (j != high) { if (j->data <= pivot) { // 小于等于枢轴值则向前推进 i = (i == NULL)? low : i->next; swap(&i->data, &j->data); // 交换两者数据域的内容 } j = j->next; } i = (i == NULL)? low : i->next; swap(&i->data, &high->data); return i; } void quickSortRecursion(ListNode *low, ListNode *high) { if (!low || !high || low == high || low == high->next) return; ListNode *pi = partition(low, high); quickSortRecursion(low, pi ? pi->prev : NULL); quickSortRecursion(pi->next, high); } void quickSortList(ListNode **head_ref) { ListNode *end = getTail(*head_ref); // 获取尾部节点作为初始高点 quickSortRecursion(*head_ref, end); } ``` 此段代码展示了如何利用快速排序的思想对单链表进行排序[^6]。其中`partition()`函数负责划分工作；而`quickSortRecursion()`则是递归地对左右两侧分别继续排序的过程。 --- ### 总结 无论是采用哪种具体的排序算法，都需要特别注意单向链表的特点——即无法像访问数组那样随机定位任意索引处的元素，因此所有的查找、替换动作都必须依赖前后相继的关系来进行迭代或递归操作。