冒泡排序是我们学习编程语言的第一个排序，可以交换数据域或者交换指针域，交换数据域太简单了，不讲。我直接上手交换指针域
理解这个算法要用笔在草稿本画画它的流程。笔者对电脑的使用并不是很熟练，只好委屈各位了。
1 #include<stdio.h> 2 #include<malloc.h> 3 typedef struct Node{ 4 int data; 5 struct Node *pNext; 6 }NODE,*PNODE; 7 8 //函数声明 9 PNODE InitList(PNODE Head);//构造单链表 10 void TraverseList(PNODE Head);//遍历输出 11 int ListLength(PNODE Head);//链表长度判断 12 void BubbleSort(PNODE Head);//冒泡排序 13 14 int main(){ 15 PNODE Head; 16 Head=InitList(Head); 17 TraverseList(Head); 18 BubbleSort(Head); 19 TraverseList(Head); 20 return 0; 21 } 22 PNODE InitList(PNODE Head){ 23 PNODE Tail,Temp; 24 int i,val; 25 Head=Temp=Tail=(PNODE)malloc(sizeof(NODE)); 26 Head->pNext=NULL; 27 while(1){ 28 printf("请输入第%d个数据:",++i); 29 scanf("%d",&val); 30 if(val!=0){ 31 Temp=(PNODE)malloc(sizeof(NODE)); 32 Temp->data=val; 33 Tail->pNext=Temp; 34 Tail=Temp; 35 } 36 else 37 break; 38 } 39 Tail->pNext=NULL; 40 return Head; 41 } 42 void TraverseList(PNODE Head){ 43 PNODE p=Head->pNext; 44 while(p!=NULL){ 45 printf("%d ",p->data); 46 p=p->pNext; 47 } 48 printf("\n"); 49 } 50 int ListLength(PNODE Head){ 51 PNODE p=Head->pNext; 52 int len=0; 53 while(p!=NULL){ 54 ++len; 55 p=p->pNext; 56 } 57 return len; 58 } 59 void BubbleSort(PNODE Head){ 60 int len=ListLength(Head); 61 int i,j;//通过i,j来控制冒泡排序的次数 62 PNODE p,q; 63 PNODE Pre,Exchange,Tail; 64 for(i=0;i<len-1;i++) 65 for(j=i+1,Pre=Head,p=Head->pNext;j<len;j++) 66 { 67 q=p->pNext; 68 Tail=q->pNext; 69 if(p->data<q->data) 70 { 71 q->pNext=p;//改变p,q的指向 72 p->pNext=Tail; 73 74 Exchange=p;//交换p,q的指向 75 p=q; 76 q=Exchange; 77 78 Pre->pNext=p; 79 } 80 Pre=Pre->pNext; //Pre,p分别指向下一个节点，再循环一次，q和Tail的指向也随之改变 81 p=p->pNext; 82 } 83 }
可以看到，这个冒泡确实是交换了指针域，不过有i,j,len来控制它的循环
所以，我做了如下的优化
1 void BubbleSort(PNODE Head){ 2 PNODE Pre,p,Tail; 3 for(Tail=NULL;Head->pNext!=Tail;Tail=p) 4 { 5 for(Pre=Head,p=Head->pNext;p->pNext!=Tail;Pre=Pre->pNext) 6 { 7 if(p->data>p->pNext->data)//改变指向 8 { 9 Pre->pNext=p->pNext; 10 p->pNext=p->pNext->pNext; 11 Pre->pNext->pNext=p; 12 } 13 else 14 p=p->pNext;//右移 15 } 16 } 17 return; 18 }
这样子就不用知道链表的长度了
以下是整个程序
1 #include<stdio.h> 2 #include<malloc.h> 3 typedef struct Node{ 4 int data; 5 struct Node *pNext; 6 }NODE,*PNODE; 7 8 //函数声明 9 PNODE InitList(PNODE Head);//构造单链表 10 void TraverseList(PNODE Head);//遍历输出 11 int ListLength(PNODE Head);//链表长度判断 12 void BubbleSort(PNODE Head);//冒泡排序 13 14 int main(){ 15 PNODE Head; 16 Head=InitList(Head); 17 TraverseList(Head); 18 BubbleSort(Head); 19 TraverseList(Head); 20 return 0; 21 } 22 PNODE InitList(PNODE Head){ 23 PNODE Tail,Temp; 24 int i,val; 25 Head=Temp=Tail=(PNODE)malloc(sizeof(NODE)); 26 Head->pNext=NULL; 27 while(1){ 28 printf("请输入第%d个数据:",++i); 29 scanf("%d",&val); 30 if(val!=0){ 31 Temp=(PNODE)malloc(sizeof(NODE)); 32 Temp->data=val; 33 Tail->pNext=Temp; 34 Tail=Temp; 35 } 36 else 37 break; 38 } 39 Tail->pNext=NULL; 40 return Head; 41 } 42 void TraverseList(PNODE Head){ 43 PNODE p=Head->pNext; 44 while(p!=NULL){ 45 printf("%d ",p->data); 46 p=p->pNext; 47 } 48 printf("\n"); 49 } 50 int ListLength(PNODE Head){ 51 PNODE p=Head->pNext; 52 int len=0; 53 while(p!=NULL){ 54 ++len; 55 p=p->pNext; 56 } 57 return len; 58 } 59 void BubbleSort(PNODE Head){ 60 PNODE Pre,p,Tail; 61 for(Tail=NULL;Head->pNext!=Tail;Tail=p) 62 { 63 for(Pre=Head,p=Head->pNext;p->pNext!=Tail;Pre=Pre->pNext) 64 { 65 if(p->data>p->pNext->data)//改变指向 66 { 67 Pre->pNext=p->pNext; 68 p->pNext=p->pNext->pNext; 69 Pre->pNext->pNext=p; 70 } 71 else 72 p=p->pNext;//右移 73 } 74 } 75 return; 76 }
写完了，我感觉自己Low爆了。
原文：https://www.cnblogs.com/ice036/p/12909831.html