冒泡排序的链表实现

冒泡排序大家应该都很熟悉，不过平常都是用数组实现的，前几天参加了深信服的笔试，其中编程题第一个就是用链表实现冒泡排序，当时有点懵逼，所以我也不知道自己写的对不对，所以笔试后就认真看了一下这个。 用链表实现冒泡排序有两种方法：一种是交换节点，另一种就是只交换节点的值。 代码如下（交换节点）： Code：

#include <stdio.h> #include <stdlib.h> typedef struct tagNode{ int value; struct tagNode *next; }Node, *pNode; void BubbleSort(pNode head) { pNode tail = NULL; while(head->next != tail) { pNode pre = head; pNode cur = pre->next; while(pre->next != tail && cur->next != tail) { if(pre->next->value > cur->next->value) { pre->next = cur->next; cur->next = cur->next->next; pre->next->next = cur; } pre = pre->next; cur = pre->next; } tail = cur; } } void Print(pNode head) { while(head->next != NULL) { printf("%d ",head->next->value); head=head->next; } puts(""); } int main() { int n; pNode list = malloc(sizeof(Node)); list->next = NULL; scanf("%d",&n); for (int i = 0; i < n; i++) { pNode node = malloc(sizeof(Node)); scanf("%d",&node->value); node->next = list->next; list->next = node; } BubbleSort(list); Print(list); return 0; }

交换值的话其实和这个基本一样，只要把循环里的交换节点的内容改成交换值就好了。 int temp=pre->next->value; pre->next->value=cur->next->value; cur->next->value=temp;