一.废话不多说,直接上代码。如果想看双向循环链表的朋友,可以在我的博客里找。
你好
#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *next; }node; //生成一个节点 node *initList(void) { node *new = malloc(sizeof(node)); if(!new) { printf("malloc fail!\n"); return NULL; } new->data = 0; new->next = NULL; return new; } //头插法 void head_insert(node *head, node *new) { new->next = head->next; head->next = new; } //遍历 node *traverse(node *head) { for(node *p = head->next; p; p = p->next) { printf("%d ", p->data); } printf("\n"); } //冒泡排序,最优版本 void bubble_sort(node *head) { int flag; node *p, *prev, *tail; tail = NULL; //tail以及tail后面的是排好序的元素,第一次还没有排好,所以为NULL while(1) { flag = 1; //flag用来标志是否已经排好序 //每次从head->next开始遍历,直到tail结束, prev是p的前驱节点 for(prev = head, p = head->next; p && p->next != tail; prev = prev->next) { //交换后,p已经移动到后面,不需要再遍历下一个 if(p->data > p->next->data) { flag = 0; //修改flag=0,标志本轮循环交换过 prev->next = p->next; //弹出p节点 p->next = p->next->next; //插入p节点 prev->next->next = p; //原来的p->next已经修改,需要用prev->next代替 } else //没有交换就继续遍历下一个 { p = p->next; } } printf("本轮排序移动出的最大值:%d\n", p->data); traverse(head); 显示每一轮排序结果 if(flag) //如果内层循环中都没有交换过,则所有节点都已经是排好序的 { printf("冒泡排序结束!\n"); break; } tail = p; //tail向前移一个,tail以及tail后面的是排好序的元素 } } //选择排序,初级版本 void choose_sort1(node *head) { node *p, *q, *max, *prior; p = malloc(sizeof(node)); //生成一个p节点 p->next = head->next; //p取代head head->next = NULL; //head是空链表 while(p->next) { prior = p; max = prior->next; for(q = max; q->next; q = q->next) { if(max->data < q->next->data) { max = q->next; prior = q; } } //从p链表中弹出一个最大的节点,用头插法插入到head链表中 prior->next = max->next; max->next = head->next; head->next = max; } free(p); } //选择排序,最优版本 void choose_sort(node *head) { node *q, *min, *prev, *tail; //tail及tail前面是排好序的,每次从tail后面选出一个最小值,插入到tail前面,直到等于NULL结束 //要额外保证p->next!=NULL,因为内层循环q=p->next; 用q->next来判断是否为空,可能会越界 for(tail = head; tail && tail->next; tail = tail->next) { //prev是min的前驱节点,q用来遍历,从min->next直到head链表最后一个 for(prev = tail, min = tail->next, q = tail->next; q->next; q = q->next) { if(min->data > q->next->data) //找到一个更小的节点,就记录 { min = q->next; prev = q; //单链表要额外记录min的前驱节点 } } printf("本轮排序选择出的最小值:%d\n", min->data); if(min != tail->next) //如果找到比min更小的节点,就插入到p后面 { prev->next = min->next; min->next = tail->next; tail->next = min; } traverse(head); //显示每一轮排序结果 } } //插入排序,最优版本 void insert_sort(node *head) { //头结点是空的或者表是空的或者表只有一个节点时候不用排 if(!head || !head->next||!head->next->next) { return; } node *p, *q, *tail; //head->next->next开始遍历,tail及tail前面的是排好序的,p是本轮待插入值, p是NULl时结束 for(tail = head->next, p = tail->next; p; p = tail->next) { //从head->next开始遍历,直到tail结束 for(q = head; q != tail; q = q->next) { if(p->data < q->next->data) //把插入后结束本次遍历 { tail->next = p->next; p->next = q->next; q->next = p; break; } } printf("本轮排序插入值:%d, ", p->data); if(tail == q) //在tail前面没有插入,就下移 { printf("已处于插入位置\n"); tail = tail->next; } else { //p已经处于插入位置,显示时需要用p->next->data printf("插入到%d的前面\n", p->next->data); } traverse(head); //显示每一轮排序结果 } } //快速排序的每一次划分 node *partition(node *head, node *tail) { //头结点是空的或者表是空的或者表只有一个节点时候不用排 //已经在调用函数前判断好了,进来的链表都是至少有两个元素的 node *p, *prev, *basic; basic = head->next; //basic是基准点 //从baisc后面开始遍历,找到比baisc小的就插入到head后面,直到tail结束,prev是p的前驱节点 //这里head可以理解为本次待划分的链表的头结点,tail是链表的最后一个节点的下一个可以理解为NULL for(prev = basic, p = basic->next; p && p != tail; p = prev->next) { if(basic->data > p->data) //用头插入法把所有比baisc小插入到head后面 { prev->next = p->next; p->next = head->next; head->next = p; } else //没有找到比basic小的就一直后移,prev与p同时后移 { prev = prev->next; } } return basic; } //快速排序 void quick_sort(node *head, node *tail) { //头结点是空的或者表是空的或者表只有一个节点时候不用排 //tail是链表的结束点,一开始等于NULL,后面等于basic if(!head || head->next == tail || head->next->next == tail) { return ; } //baisc前的节点都比basic小,baisc后的节点都比baisc大 node *basic = partition(head, tail); printf("本次划分节点:%d\n", basic->data); quick_sort(head, basic); //把head->next到basic前一个进行递归排序 quick_sort(basic, tail); //从basic->next到tail前一个进行递归排序 } int main(void) { int i, len; node *head, *new, *p, *q; printf("请输入单链表的长度: "); scanf("%d", &len); head = initList(); head->data = len; printf("请输入元素:"); for(int i = 0; i<len; i++) { new = initList(); scanf("%d", &new->data); head_insert(head, new); } printf("请选择排序方式,1.选择排序 2.冒泡排序 3.插入排序 4.快速排序: "); scanf("%d", &i); printf("排序前:\n"); traverse(head); switch(i) { case 1: choose_sort(head); break; case 2: bubble_sort(head); break; case 3: insert_sort(head); break; case 4: quick_sort(head, NULL); break; } printf("由小到大排序后:\n"); traverse(head); return 0; }
温馨提示:
如果复制时发现有缩进报错,后者空格报错等问题,以VScode为例,可以按Ctrl+F,复制一个报错的空格,然后替换成一个手打的空格键,具体操作可以搜搜,可以看我的博客。
具体截图:以 12 34 78 56 23 99 34 12 45 76为例,其他朋友可以自己举
选择排序
冒泡排序
插入排序
快速排序
二.代码分析
如果你认真看完上述的代码和注释,那么,我可以大概率保证你基本可以看懂了单链表的排序,其实也不难,就是在关键步骤和控制条件。下面来仔细分析每个排序的关键步骤和控制条件。
冒泡排序
思路:冒泡排序就是从首元结点开始,左右两两比较大小,以从小到大排序为例,如果比后面一个的节点大,就交换,然后继续往后比较,直到到达已经排好的元素为止。
特点:每一轮冒泡排序结束后,总会把最大的节点放到最后面,不断的往前移,直到头结点,就结束了。
注意的地方:单链表的交换,不同于数组的交换,单链表的交换后,以p和q为例,p在q的前面,如果p->data > q->data,就交换p和q节点,交换后p已经处于下一次待交换的位置,所以不需要在p = p->next了,否则会漏了一个没排,出错,需要特别注意!
优化地方:1.设置flag,来标志链表中的元素是否已经是排好序的,因为这里做可以用一次循环判断出链表中的元素是否已经排好,而不用进行无用的多层循环。2.设置一个tail,来指明后面的节点是排好的,当遍历到tail时,就结束本轮循环,同时tail前移一个。
选择排序
思路:选择排序就是每次从未排好的节点中,通过遍历比较大小的方法,选择出一个最小的(以从小到大排为例),然后插入到排好的后面,这样,每轮循环就可以选出一个最小的,直到全部插入完为止。
特点:跟插入排序很像,但两者略有不同,选择排序先选出最小的,然后直接插入到排好元素的后面,而插入排序是直接选出一个节点,然后通过和排好的元素进行比较大小来插入到合适的位置。
注意的地方:以从小到大排为例,采用尾插法应该是每次选取最小的,如果采用头插法应该是每次选取最大的。
优化地方:如果这个节点本来就处于待插入地方,即当前最小的,就不需要交换了,直接进行下一轮。写了两版本的一个是生成一个p节点来取代head头结点, 然后直接把每次选择出的节点直接插入到后面,然后再重新让head取代p指向排好序的节点。另外一个版本的是设置一个tail标志,之所以说有点像插入排序,就是体现在这里了。
插入排序
思路:插入排序就是每次直接从未排好序的节点中拿一个出来,一般是下一个;然后在排好序的节点中通过遍历的方法来比较应该插入到的位置,直到插完为止。
特点:直接选一个插入,不像选择排序那样,先选了,再插入。
注意的地方:需要设置标志tail来指明已经排好的节点的界限,遍历查找插入位置时,遇到tail,说明待插入节点是已经排好的节点中最大的,不需要插入,同时tail要后移一个。
优化地方:tail标志和直接插入。
快速排序
思路:每次选中一个基准点,然后从基准点后面开始遍历,如果找到比基准点小节点(以从小到大排为例),就插入到基准点前面,直到链表的尾部,结束。这样每一次划分后,处于基准点前面的节点都比基准点小,处于基准点后面的节点都比基准点大。然后分别递归划分基准点前的节点和后的节点。
特点:每次划分结束后能找到一个基准点,可以看成是中位数,然后递归。有点像二分查找,跟一颗二叉树差不多。
注意的地方:第一次传参数时,传head(头节点)和NULL。而且需要严格控制退出条件,头结点为空,或者没有节点,或者只有一个节点时,不用排,直接返回。
优化的地方:没啥好讲的,还有另外一种划分方法,就是数组常用的,就是往中间靠的方法,一个head和tail,如果head<tail,tail就一直往前移,然后如果head<tail,head就一直往后移,直到head == tail是就是本次划分的基准点。详情可以看我的博客里的双向循环链表排序。由于这里是单链表,tail往前移后花费很大的代价,所以不采用,双向循环链表有前指针prev,可以采用。
三.总结
单链表的排序相比数组的排序来说,是相对困难的,主要是在元素方面,数组不用考虑什么,直接交换元素,而链表相对灵活,一般是交换节点。如果你写的链表是用交换元素的方式的,我只能说,你写了假的的链表排序,因为你抛弃了链表的灵魂。链表的交换节点一般是插入的方法,头插后者尾插,同时还得记录一下前驱节点的位置,笔者为了优化算法,下了很大功夫,在排序中尽量在记录前驱节点的同时,尽量少记录待交换节点(前驱节点的下一个节点)。
如果你会写单链表的排序,那么我可以说,你一定会写双向循环链表的排序,因为基本可以直接复制过来,只是把判断链表最后一个节点的条件由NULL改成head而已,因为循环嘛,最后一个节点的下一个就是头结点了,而单链表的最后一个节点的下一个就是NULL了。文章来源:https://www.toymoban.com/news/detail-770041.html
想看双向循环链表的朋友可以去我的博客里看。最后希望朋友你可以给我一个点赞,收藏,评论和转发,你们的支持是我最大的动力。如果有讲错的地方,请朋友大胆指出,谢谢!毕竟刚开始写博客。绝对原创!文章来源地址https://www.toymoban.com/news/detail-770041.html
到了这里,关于C语言版--单链表排序,冒泡排序,选择排序,插入排序,快速排序,应有尽有,保证看懂,没有bug!交换节点版本!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!