首页 > 代码库 > 单向链表排序
单向链表排序
一、冒泡排序简述
1、概念
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。
2、实例分析
以数组为例进行说明：
数组a[4] = {4,3,2,1}
从前向后依次比较两个元素的大小，如果顺序错误就交换它们。经过这样一轮，最大的元素就被交换到了数组的顶端，好像是最大的元素“浮”上去一样。经过这样一轮，最后的一个元素的已经确定。a[4] = {3,2,1,4}
再次重复上边的操作，只不过因为上一轮最后一个元素已经确定，所以这一次比较的终点（以此为界，不能超过此界）就是上一轮的最后一个元素。也就是，第二轮的比较中，数组最后一个元素没有参与比较。第二轮比较中的最后一个元素是倒数第二个元素。经过这样一轮比较，倒数第二个元素也被确定。a[4] = {2,1,3,4}
重复这样的操作，直到数组的第二个元素被确定。因为除了第一个元素外，所有的元素都被锁定，所以第一个元素实际上也被确定。到此为止，排序完成。a[4] = {1,2,3,4}
3、冒泡排序的关键
<1> 每经过一轮的排序，一个最大的元素被“浮”到对应的位置。随之，下一次比较的终点也需要向前移一个元素。
<2> 当正数第二个元素被确定的时候，冒泡排序完成。
二、冒泡法应用于单向链表排序
1、实例展示
① 初始链表
② 第一轮排序
③ 第二轮排序
④ 第三轮排序
2、算法流程图
3、源码以及测试
1 #include <stdio.h> 2 #include <malloc.h> 3 4 /* 排序状态取值表 */ 5 typedef enum 6 { 7 SORT_OK, /* 排序成功标志 */ 8 SORT_ERR /* 排序失败标志 */ 9 }SORTSTATE; 10 11 /* 接点结构体 */ 12 struct node{ 13 struct node * pnext; 14 unsigned int value; 15 }; 16 17 typedef struct node Node; 18 19 SORTSTATE sort(Node * * chainhead); 20 21 /** @函数功能：测试单向链表排序功能 22 * @输入参数：无 23 * @输出参数：无用 24 */ 25 int main(void) 26 { 27 Node * head,* p; 28 SORTSTATE status; 29 30 /* 构建单向链表 */ 31 p = (Node *)malloc(sizeof(Node)); 32 head = p; /* 保存链表头部 */ 33 p->value = http://www.mamicode.com/5; 34 p->pnext = (Node *)malloc(sizeof(Node)); 35 36 p = p->pnext; 37 p->value = http://www.mamicode.com/97; 38 p->pnext = (Node *)malloc(sizeof(Node)); 39 40 p = p->pnext; 41 p->value = http://www.mamicode.com/7; 42 p->pnext = (Node *)malloc(sizeof(Node)); 43 44 p = p->pnext; 45 p->value = http://www.mamicode.com/65; 46 p->pnext = (Node *)malloc(sizeof(Node)); 47 48 p = p->pnext; 49 p->value = http://www.mamicode.com/12; 50 p->pnext = (Node *)malloc(sizeof(Node)); 51 52 p = p->pnext; 53 p->value = http://www.mamicode.com/1; 54 p->pnext = NULL; /* 链尾初始化为空 */ 55 56 /* 打印链表的内容 */ 57 p = head; 58 while(p != NULL){ 59 printf("%4d",p->value); 60 p = p->pnext; 61 } 62 printf("\n"); 63 64 /* 链表排序 */ 65 status = sort(&head); 66 if(status == SORT_ERR){ 67 printf("Chain is wrong!\n"); 68 } 69 70 /* 打印链表的内容 */ 71 p = head; 72 while(p != NULL){ 73 printf("%4d",p->value); 74 p = p->pnext; 75 } 76 printf("\n"); 77 78 return 0; 79 } 80 81 82 /** @函数功能：单向链表排序 83 * @输入参数：指向链表头部的指针 84 * 注意：指向指针的指针可以修改指针的指向 85 * @输出参数：SORTSTATE 排序成功与否状态 86 */ 87 SORTSTATE sort(Node * * chainhead) 88 { 89 Node * head, /* 当前比较接点的上一个接点 */ 90 * first, /* 当前比较接点 */ 91 * second, /* 当前参与比较的另一个接点 */ 92 * end; /* 当前比较接点的终点 93 * 终点意味着从终点开始往后的 94 * 链表排序已经确定，只需要将 95 * 终点前的所有接点按照冒泡法 96 * 排序，排序就将完成。 97 */ 98 99 if(*chainhead == NULL) /* 链表是否为空 */ 100 return SORT_ERR; 101 if((*chainhead)->pnext == NULL) /* 链表是否就只有一个接点 */ 102 return SORT_OK; 103 104 end = NULL; /* 第一轮冒泡排序的终点接点值为NULL */ 105 106 /* 冒泡法排序,可能有很多轮次 */ 107 while(end != (*chainhead)->pnext){ /* 如果排序的终点等于接点的第二个地址， 108 * 也就是说从第二个接点开始所有的接点 109 * 都已经按照从小到大的顺序确定了位置。 110 * 显然，剩下的唯一一个“第一接点”位置 111 * 也就确定了。所有排序全部完成。 112 */ 113 114 /* 首先比较位于头部的两个接点，由于位于头部， 115 * 与其他接点不一样,需要放在循环外边，单独处理。 116 */ 117 first = *chainhead; /* 第一个比较接点是链表头部指向的接点 */ 118 second = first->pnext; /* 第二个比较接点是紧邻的第二个接点 */ 119 120 /* 是否需要更改链表的连接顺序 */ 121 if(first->value > second->value){ 122 *chainhead = second; /* 更改链表头部的指向 */ 123 /* 重新连接链表，就相当于对链表排序 */ 124 first->pnext = second->pnext; 125 second->pnext = first; 126 } 127 128 /* 移动比较接点到下两个接点 */ 129 head = *chainhead; /* 当前比较接点的上一个接点则是头部接点 */ 130 first = head->pnext; /* 当前比较接点 */ 131 second = first->pnext; /* 当前参与比较的另一个接点 */ 132 133 while(second != end) /* 此轮的比较是否结束 */ 134 { 135 /* 是否需要更改链表的连接顺序 */ 136 if(first->value > second->value){ 137 /* 重新连接链表，就相当于对链表排序 */ 138 head->pnext = second; 139 first->pnext = second->pnext; 140 second->pnext = first; 141 142 } 143 /* 移动比较接点到下两个接点 */ 144 head = head->pnext; 145 first = head->pnext; 146 second = first->pnext; 147 } 148 149 end = first; /* 一轮排序完成，结束接点位置上移一个 */ 150 } 151 152 return SORT_OK; /* 排序成功 */
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。